Easy impossibility proofs for distributed consensus problems

Easy proofs are given, of the impossibility of soh, ing several consensus problems (Byzantine agreement, weak agreement, Byzantine firing squad, approximate agreement and clock synchronization) in certain communication graphs. It is shown that, in the presence ofm faults, no solution to these problems exists for communication graphs with fewer than 3m + 1 nodcs or less than 2m + l connectivity. While some of these results had previously been proved, the new proofs are much simpler, provide considerably more insight, apply to more general models of computation, and (particularly in the case of clock synchronization) significantly strengthen the results. I. introtluction In this paper, we present easy proofs for the impossibility of solving several conscnsus problems in particular communication graphs. We prove results for Byzantine agreement, weak agrcemcnt, the Byzantine firing squad problem, approximate agreement and clock synchronization. The bounds are all the same: tolerating m faults requires at least 3m + 1 nodes, and requires at least 2m + 1 connectivity in the communication graph. (The connectivity of a graph is the minimum number of nodcs whose removal disconnects the graph.) The work of the first author was supported by th