On the Possibility of Consensus in Asynchronous Systems
The authors demonstrate that the leader election and consensus problems are solvable in a timed asynchronous distributed system provided a majority of processes are always eventually able to communicate in a timely manner for a sufficiently long time. Failures and recoveries affecting the other processes and the communications between them do not prevent consensus. The timed asynchronous system model describes with accuracy existing asynchronous distributed systems such as those based on networks of workstations. They describe two protocols that implement leadership and consensus services and prove the correctness.