This paper introduces and explores a new condition based approach to solve the consensus problem in asynchronous systems. The approach consists of identifying sets of input vectors, called conditions, for which it is possible to design a protocol solving consensus despite the occurrence of up to f process crashes. The rst main result is a generic consensus protocol for the shared memory model. It always guarantees agreement, and also termination (at least) when the inputs satisfy the condition with which the protocol has been instantiated, or when there are no crashes. Then, two particular realistic conditions are de ned, and proved to be maximal. The second main result is a characterization of the conditions that allow to solve consensus. The consensus protocol works for any s u c h condition. An e cient v ersion of the protocol is then designed for the message passing model that works when f < n = 2 , a n d i t i s s h o wn that no such protocol exists when f n=2. It is also shown how the protocol's safety can be traded for its liveness.
The condition based approach for solving consensus identifies various sets of input values that enable solving consensus fast REF .
Conditions on input vectors for consensus solvability in asynchronous distributed systems
STOC '01
Computer Science