Optimal early stopping uniform consensus in synchronous systems with process omission failures
Philippe Raïpin Parvédy, Michel Raynal · 2004
Consensus is a central problem of fault-tolerant distributed computing that, in the context of synchronous distributed systems, has received a lot of attention in the crash failure model and in the Byzantine failure model. This paper considers synchronous distributed systems made up of n processes, where up to t can commit failures by crashing or omitting to send or receive messages when they should ("process omission" failure model). It presents a protocol solving uniform consensus in such a context. This protocol has several noteworthy features. First, it is particularly simple. Then, it is optimal both in (1) the number of communication steps needed for processes to decide and stop, namely, min(f+2,t+1) where f is the actual number of faulty processes, and (2) the number of processes that can be faulty, namely t