HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Consensus Based on Strong Failure Detectors: Time and Message-Efficient Protocols

Fabiola Greve 1 Michel Hurfin 1 Raimundo Macêdo 2 Michel Raynal 1
1 ADP - Distributed Algorithms and Protocols
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : The class of strong failure detectors (denoted S) includes all failure detectors that suspect all crashed processes and that do not suspect some (a priori unknown) process that never crashes. So, a failure detector that belongs to S is intrinsically unreliable as it can arbitrarily suspect correct processes. Several S-based consensus protocols have been designed. Some of them systematically require n computation rounds (n being the number of processes), each round involving n2 or n messages. Others allow early decision (i.e., the number of rounds depends on the maximal number of crashes when there are no erroneous suspicions) but require each round to involve n2 messages. This paper presents an early deciding S-based consensus protocol each round of which involves 3(n-1) messages. So, the proposed protocol is particularly time and message-efficient. Moreover, it can easily be generalized to reduce the number of rounds at the price of an increase in the number of messages per round.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:58:40 AM
Last modification on : Friday, February 4, 2022 - 3:16:33 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:23:06 PM


  • HAL Id : inria-00072801, version 1


Fabiola Greve, Michel Hurfin, Raimundo Macêdo, Michel Raynal. Consensus Based on Strong Failure Detectors: Time and Message-Efficient Protocols. [Research Report] RR-3855, INRIA. 2000. ⟨inria-00072801⟩



Record views


Files downloads