On the nonexistence of resilient consensus protocols (Q756398)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the nonexistence of resilient consensus protocols
scientific article

    Statements

    On the nonexistence of resilient consensus protocols (English)
    0 references
    0 references
    1991
    0 references
    \textit{M. J. Fischer, N. A. Lynch} and \textit{M. S. Paterson} [J. Assoc. Comput. Mach. 32, 374-382 (1985; Zbl 0629.68027)] proved that in asynchronous message passing systems there cannot exist a consensus protocol that tolerates even a single undetectable crash failure. Their proof of this fundamental result relies on operational details such as sending and receiving messages, etc. \textit{M. Chandy} and \textit{J. Misra} [ACM Trans. Program. Lang. Syst. 8, 326-343 (1986; Zbl 0598.68031)] have taken an axiomatic nonoperational approach to the consensus problem. Their idea is to define asynchronous systems and consensus protocols by a set of axioms, making no mention of operational details. The result of Chandy and Misra is weaker than that of Fischer, Lynch and Paterson, since it is not assumed, that all messages sent are eventually delivered. We use the Chandy and Misra approach to prove a result that is similar to the one of Fischer, Lynch and Paterson. We present three axioms capturing the nature of asynchronous message passing systems and five axioms defining resilient consensus protocols. We then prove that there does not exist an asynchronous resilient consensus protocol by showing that the set of eight axioms is inconsistent.
    0 references
    fault tolerance
    0 references
    impossibility proof
    0 references
    crash failure
    0 references
    asynchronous message passing systems
    0 references
    resilient consensus protocol
    0 references

    Identifiers