Negative results such as impossibility results are fundamental in Distributed Computing to establish what can and cannot be computed in a given setting, or permitting to assess optimality results through lower bounds for given problems. Two notorious examples are the impossibility of reaching consensus in an asynchronous setting when a single process may fail by stopping unexpectedly, and the impossibility of reliably exchanging information when more than one third of the processes can exhibit arbitrary behaviour. As noted by Lamport, Shostak and Pease, correctly proving results in the context of Byzantine (a.k.a. arbitrary behaviour capable) processes is a major challenge, as they knew of no area in computer science or mathematics in which informal reasoning is more likely to lead to errors than in the study of this type of algorithm.
展开▼
