Randomization and Spontaneous Ordering. One possible way of circumventing the impossibility result is through the use of randomization. The algorithm of Xxxxxx and Xxxxx [Xxxxxx and Xxxxx, 1983], for example, rely on the fact that, if agents keep exchanging messages in rounds, then there is a non-zero probability that they will all eventually receive the same set of messages in some round. The authors have called this property fair scheduling. The algorithms of Xxxxx [Xxxxx, 1983] and Ben-Or [Ben-Or, 1983] employ ran- domization in a different way. In their algorithms, if agents have no reason to opt for some proposal or another in some round, then they use a random bit generator to chose one. Given that there is a non zero probability that all chose the same random bit, agreement is reached with probability 1. Xxxxxx et al. [Xxxxxx et al., 2002a] later replaced the selection based on the random bit generator used by Xxxxx [Xxxxx, 1983] and Ben-Or [Ben-Or, 1983] for a selection based on the order in which messages are received. This is possible if, for every round, there is a non zero probability that messages will be received in the same order. These properties, somehow related to fair scheduling, are abstracted by weak ordering oracles [Xxxxxx et al., 2002b]. In specific, the algorithms of Xxxxxx et al. [Xxxxxx et al., 2002a], namely B-Consensus and R-Consensus in reference to Ben-Or and Xxxxx, use the weak atomic broadcast (WAB) oracle, which ensures that if processes keep exchanging broadcast messages then, in some rounds, the first 2.1 Consensus and the FLP Impossibility Result 11 message received by all running agents is the same. In the same work, the authors show that, with high probability, Ethernet broadcast satisfies the WAB specification. WAB based protocols are interesting from a practical perspective since they do not make any synchrony assumption. Nonetheless, B-Consensus and R-Consensus are of more theoretical than practical interest for their assumed failure and com- munication models: crash-stop and reliable links. From a pragmatic perspective, agents should be capable of reintegrating the system after a crash and tolerate mes- sage losses, being able to can make better use of highly-efficient communication means (e.g., UDP messages). Crash-Recovery WAB-Based Consensus We have extended the protocols of Xxxxxx et al. [Xxxxxx et al., 2002a] to the crash- recovery model with fairly lossy channels. Moreover, we defined these extended protocols using roles and relaxed the constrai...
