Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Early Consensus in an Asynchronous System with a Weak Failure Detector
 
research article

Early Consensus in an Asynchronous System with a Weak Failure Detector

Schiper, A.  
1997
Distributed Computing

Consensus is one of the most fundamental problems in the context of fault-tolerant distributed computing. The problem consists, given a set P of processes having each an initial value vi, in deciding among P on a common value v. In 1985, Fischer, Lynch and Paterson proved that the consensus problem is not solvable in an asynchronous system subject to a single process crash. In 1991, Chandra and Toueg showed that, by augmenting the asynchronous system model with a well defined "unreliable" failure detector, consensus becomes solvable. They also give an algorithm that solves consensus using the <>S failure detector. In this paper we propose a new consensus algorithm, also using the <>S failure detector, that is more efficient than the Chandra-Toueg consensus algorithm. We measure efficiency by introducing the notion of "latency degree", which defines the minimal number of communication steps needed to solve consensus. The Chandra-Toueg algorithm has a latency degree of 3 (it requires at least three communication steps), whereas our early consensus algorithm requires only two communication steps (latency degree of 2). We believe that this is an interesting result, which adds to our current understanding of the cost of consensus algorithms based on <>S.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1007/s004460050032
Author(s)
Schiper, A.  
Date Issued

1997

Published in
Distributed Computing
Volume

10

Issue

3

Start page

149

End page

157

Note

ERRATUM Lines 34 and 46 of Figure 1 are incomplete. They should read: 34 upon reception of (p_j,r_i,suspicion) from p_j when phase_i=1: 46 r_i := r_i+1; estimate_i.first := i;

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LSR-IC  
Available on Infoscience
May 20, 2005
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/213807
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés