A simple proof of the necessity of the failure detector Sigma to implement an atomic register in asynchronous message-passing systems

作者：Bonnet Francois; Raynal Michel^*

来源：Information Processing Letters, 2010, 110(4): 153-157.

DOI：10.1016/j.ipl.2009.11.011

• Concurrency
• Distributed algorithms
• Fault-tolerance
• Theory of computation
• Asynchronous message-passing system
• Atomic register
• Weakest failure detector

This paper presents a simple proof that shows that the quorum failure detector class (denoted Sigma) is the weakest failure detector class required to implement all atomic read/write register in all asynchronous message-passing system prone to all arbitrary number of process crashes. This proof is based on a new reduction algorithm ill which all the variables are bounded.

• 出版日期2010-1-16