Towards a Unified Comparison of Synchronous and Asynchronous Agreement Protocols
Alessandro Galleni, David Powell · 1995
. In a reliable computer system, correctly-functioning processors must be able to reach agreement despite the presence of malfunctioning components. This report discusses two such agreement problems. In the consensus problem, processors must reach a common decision despite failures. In the membership problem, agreement must be reached concerning the history of groups of correct processors that exist over time as well as on the membership of each group. A survey of some existing literature on consensus and membership protocols is carried out, pointing out the different assumptions about the properties of the system on which these protocols are based. Then, a unified validation framework is proposed in order to compare, in probabilistic terms, the properties of these different protocols, together with the problems involved with this validation. 1. Introduction The problem of reaching agreement among separate processors in the presence of faulty ones is a fundamental problem of both theo...