The Inherent Cost of Achieving Causal Consistency

Abstract

We consider the problem of distinguishing causally-consistent global states in asynchronous distributed systems. Such states are fundamental to asynchronous systems, because they correspond to possible simultaneous global states; their detection arises in a variety of distributed applications, including global checkpointing, deadlock detection, termination detection and broadcasting. A consistent-cut protocol is a protocol which in every run will designate for each processor a state, in such a way that these states together form a consistent cut. We analyze the cost of achieving causal consistency in terms of the extent to which a consistent-cut protocol delays events of the underlying system, and the message-complexity required by any such protocol. We refer to the delaying action of a protocol as inhibition. We consider a spectrum of protocol capabilities based on the type of inhibition that occurs: we distinguish local versus global inhibition and prove fundamental relationships between these concepts and the ability to determine causally-consistent states. A protocol using local inhibition may cause the delay of some of a processor's events until that processor has performed some number of local actions; a protocol using global inhibition may force the delay of some of a processor's events until that procesor has received some communication from other processors. Based on a variety of system and protocol characteristics, including the ability to locally or globally inhibit particular types of events, we give several impossibility results and examine some existing protocols. We are then able to present a thirty-six-case summary of protocols and impossibility results for the determination of causally-consistent states as a function of those characteristics. In particular, we demonstrate that local inhibition is necessary and sufficient to solve this problem for general FIFO systems, while global send inhibition is necessary and sufficient for general non-FIFO systems. Regarding message complexity, we demonstrate that a globally inhibitory consistent-cut protocol requires $O (N)$ messages where $N$ is the number of processors in the system. This is true whether the protocol is designed to work for FIFO or non-FIFO systems; the exact lower bounds, however, differ in the two cases. We also prove that a consistent-cut protocol which uses local inhibition only requires $O$ ($N^{2}$) messages, or, more precisely, $O$ ($\vert \cal C \vert$), where $\cal C$ is the channel set of the system. This latter result illustrates a trade-off between the message complexity of a consistent-cut protocol and the degree of inhibition which it requires.