The Consensus Power of Shared-Memory Distributed Systems

Abstract

In many asynchronous distributed systems, processes communicate by accessing objects in a shared memory. The ability of systems to solve problems in a fault-tolerant manner depends on the types of objects provided. Here, the wait-free model of fault-tolerance is used: non-faulty processes must run correctly even if other processes experience halting failures. The consensus problem, where processes begin with private inputs and must agree on one of them, has played a central role in analysing the power of distributed systems. This thesis studies the ability of different types of objects to solve consensus.

An object type has consensus number n if it can be used (with read/write registers) to solve consensus among n processes but not among n+1 processes. Conditions are given that are necessary and sufficient for an object type to have consensus number n. This characterization applies to two large classes of objects: readable objects and read-modify-write (RMW) objects. An object is readable if processes can read its state without changing the state. For a RMW object, all operations update the state and then return the previous state of the object. When the type is of bounded size, the characterization may be used to decide the question ``Does the type T have consensus number n?'', which is undecidable for arbitrary types. The characterization is also used to show that different readable and RMW types with consensus number n cannot be used in combination to solve consensus for n+1 processes.

Ordinarily, processes may access only one object in shared memory at a time. This thesis also studies how much the consensus number of a type increases in the multi-object and transactional models, where processes can perform operations on up to m of the objects in a single atomic action. These models are much more convenient for programmers to use, since they guarantee that certain blocks of operations will be executed without interruptions from other processes. This thesis establishes bounds on the consensus numbers of multi-objects and transactional objects as a function of m and the consensus numbers of the corresponding single-access types.