Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper analyzes the communication costs of implementing linearizable atomic registers in asynchronous message passing systems. It proves that linearizability requires extensive message chains to maintain the real-time order of operations when processes lack precise timing information. The key result is that linearizable register implementations must create message chains among operations of all types, implying inherent cost and complexity in asynchronous systems.
Linearizability in asynchronous systems demands surprisingly intricate message chains, revealing a fundamental cost that challenges simple implementations of atomic registers.
While linearizability is a fundamental correctness condition for distributed systems, ensuring the linearizability of implementations can be quite complex. An essential aspect of linearizable implementations of concurrent objects is the need to preserve the real-time order of operations. In many settings, however, processes cannot determine the precise timing and relative real-time ordering of operations. Indeed, in an asynchronous system, the only ordering information available to them is based on the fact that sending a message precedes its delivery. We show that as a result, message chains must be used extensively to ensure linearizability. This paper studies the communication requirements of linearizable implementations of atomic registers in asynchronous message passing systems. We start by proving two general theorems that relate message chains to the ability to delay and reorder actions and operations in an execution of an asynchronous system, without the changes being noticeable to the processes. These are then used to prove that linearizable register implementations must create extensive message chains among operations of \emph{all} types. In particular, our results imply that linearizable implementations in asynchronous systems are necessarily costly and nontrivial, and provide insight into their structure.