24 April 2017 in IEEE Transactions on Parallel and Distributed Systems
Many applications model their data in a general-purpose storage format such as JSON. This data structure is modified by the application as a result of user input. Such modifications are well understood if performed sequentially on a single copy of the data, but if the data is replicated and modified concurrently on multiple devices, it is unclear what the semantics should be. In this paper we present an algorithm and formal semantics for a JSON data structure that automatically resolves concurrent modifications such that no updates are lost, and such that all replicas converge towards the same state (a conflict-free replicated datatype or CRDT). It supports arbitrarily nested list and map types, which can be modified by insertion, deletion and assignment. The algorithm performs all merging client-side and does not depend on ordering guarantees from the network, making it suitable for deployment on mobile devices with poor network connectivity, in peer-to-peer networks, and in messaging systems with end-to-end encryption.
7 August 2013 in Electronic Commerce Research
1 April 2023 in Proceedings on Privacy Enhancing Technologies
Novel attacks on dataset privacy are usually met with the same range of responses: surprise that a route to information gain exists from information previously thought to be safe; disputes around the viability or validity of the attack in real-world contexts; and, in the case of the computer science community, a drive to produce techniques that provably protect against the new class of attack. The result is a disjointed landscape with no shared approach to modelling threats to dataset privacy, and a toolbox of technically complex systems whose guarantees come with narrow assumptions and whose application in real-world contexts is hard to achieve. In this paper we aim to understand these issues by charting the history of dataset privacy attacks and systematising breaches through the lens of data linkage. We show how identification or information gain on a dataset's subjects can be expressed as data linkage, and use this to present a taxonomy of threat models which we apply to ninety-four attacks from across the literature. Our work demonstrates that dataset privacy must be approached first as a risk management problem, rather than one of strict guarantees, an approach which aligns well with law and practice. Our taxonomy of attacker intents provides a coherent language for expressing the wide variety of threat models in dataset privacy, and a framework for understanding how risks identified under one model can be understood within another. We also present insights around the factors that affect the feasibility and severity of attacks, and proposals for practical techniques that can be used for risk appraisal and management by practitioners, researchers, and regulators alike.
7 October 2021 in IEEE Transactions on Parallel and Distributed Systems
Replicated tree data structures are a fundamental building block of distributed filesystems, such as Google Drive and Dropbox, and collaborative applications with a JSON or XML data model. These systems need to support a move operation that allows a subtree to be moved to a new location within the tree. However, such a move operation is difficult to implement correctly if different replicas can concurrently perform arbitrary move operations, and we demonstrate bugs in Google Drive and Dropbox that arise with concurrent moves. In this article we present a CRDT algorithm that handles arbitrary concurrent modifications on trees, while ensuring that the tree structure remains valid (in particular, no cycles are introduced), and guaranteeing that all replicas converge towards the same consistent state. Our algorithm requires no synchronous coordination between replicas, making it highly available in the face of network partitions. We formally prove the correctness of our algorithm using the Isabelle/HOL proof assistant, and evaluate the performance of our formally verified implementation in a geo-replicated setting.
24 April 2019 in Communications of the ACM
Achieving consistency where distributed transactions have failed.