Time and Message-Efficient S-Based Consensus
Fabiola GREVE, Michel HURFIN, Raimundo MACEDO, Michel RAYNAL
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
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 n*n or n messages. Others allow early
decision (i.e., the number of rounds depends only on the maximal number
of crashes when there are no erroneous suspicions) but require each round
to involve n*n messages. This brief annoucement 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.