Wait-Free Consensus Using Asynchronous Hardware

Reviewer: Martti J. Tienari

Reaching consensus among different processors is one of the fundamental problems whenever any type of cooperation is to be achieved. In this paper, the problem is investigated in a totally asynchronous system, where communication is carried out by shared registers that are atomic with respect to read and write operations, and up to n-1 out of n processors may fail-stop (that is, crash). The authors look for solutions that satisfy the wait-free termination requirement. This means that every processor that is activated a sufficient number of times will decide and terminate. Such a requirement is in accordance with the complete asynchrony of the system: it does not make sense to force a fast processor to wait until a slow processor makes a move. Furthermore, wait-free termination implies resilience to any number of processor crashes. It is known that wait-free consensus cannot be achieved by deterministic protocols, even for systems with two processors. It is also a well-known fact that certain problems that cannot be solved by deterministic protocols admit randomized solutions. The authors present an efficient randomized protocol that operates with atomic single-writer multireader registers. The protocol is fairly simple and its expected runtime is O n 2 for systems of size n . This means that, for any adversary scheduler, the system reaches a decision, on average, after O n 2 steps by all processors. The protocol uses unbounded-size registers. Large values are actually written only with very low probability; for example, when the size of the shared registers is bounded by 128 bits per processor, the protocol still never errs and has a probability of nontermination of less than 2 -56 . The paper is clearly written. It is for specialists, and makes progress in a limited area of research.