Search

Matrix is a new kind of decentralized, topic-based publish-subscribe middleware for communication and data storage that is getting particularly popular as a basis for secure instant messaging. By comparison with traditional decentralized communication systems, Matrix replaces pure message passing with a replicated data structure. This data structure, which we extract and call the Matrix Event Graph (MEG), depicts the causal history of messages. We show that this MEG represents an interesting and important replicated data type for decentralized applications that are based on causal histories of publish-subscribe events: First, we prove that the MEG is a Conflict-Free Replicated Data Type for causal histories and, thus, provides Strong Eventual Consistency (SEC). With SEC being among the best known achievable trade-offs in the scope of the well-known CAP theorem, the MEG provides a powerful consistency guarantee while being available during network partition. Second, we discuss the implications of byzantine attackers on the data type's properties. We note that the MEG, as it does not strive for consensus or strong consistency, can cope with n > f environments with n participants, of which f are byzantine. Furthermore, we analyze scalability: Using Markov chains, we study the number of forward extremities of the MEG over time and observe an almost optimal evolution. We conjecture that this property is inherent to the underlying spatially inhomogeneous random walk. With the properties shown, a MEG represents a promising element in the set of data structures for decentralized applications, but with distinct trade-offs compared to traditional blockchains and distributed ledger technologies.

• New fault-tolerant communication abstraction. • Simple implementations of read/write implementable objects. • Efficient implementations of snapshots and lattice agreement. This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message m and later delivers a set of messages including a message m ′ , no process delivers first a set of messages including m ′ and later a set of message including m. After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the "power" side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data types), and distributed tasks. On the "computability limits" side it shows that SCD-broadcast and read/write registers are computationally equivalent. [ABSTRACT FROM AUTHOR]

In this paper, we describe our experiences extending a distributed data caching service in the mobile cloud to support active-active geo-replication. We show how our enhancements guarantee data consistency between regions after a network partition recovery. An approach is presented for keeping geo-distributed replicas synchronized despite the cache data operations replication not ensuring causal delivery in the presence of long network partitions. We use Redis, one of the most popular in-memory databases for the distributed data caching service in the mobile cloud, as a proof of concept to apply our approach in a plug-in way (minimizing the impact on both the server and client side of the cache service). Redis exposes a powerful extension API that allows new abstract data types to be associated with keys but does not provide direct support for adding and managing global dictionary metadata, which we added in our solution. That extension API is used to add the CRDT (Conflict-free Replicated Data Type) to resolve the writing conflicts from multiple regions. [ABSTRACT FROM AUTHOR]