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. The Inherent Price of Indulgence
 
research article

The Inherent Price of Indulgence

Dutta, Partha  
•
Guerraoui, Rachid  
2005
Distributed Computing

This paper presents a tight lower bound on the time complexity of indulgent consensus algorithms, i.e., consensus algorithms that use unreliable failure detectors. We state and prove our tight lower bound in the unifying framework of round-by-round fault detectors. We show that any P -based t-resilient consensus algorithm requires at least t+2 rounds for a global decision even in runs that are synchronous. We then prove the bound to be tight by exhibiting a new P-based t-resilient consensus algorithm that reaches a global decision at round t + 2 in every synchronous run. Our new algorithm is in this sense significantly faster than the most efficient indulgent algorithm we knew of (which requires 2t + 2 rounds). We contrast our lower bound with the well-known t + 1 round tight lower bound on consensus for the synchronous model, pointing out the price of indulgence.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1007/s00446-005-0124-9
Web of Science ID

WOS:000231518900007

Author(s)
Dutta, Partha  
Guerraoui, Rachid  
Date Issued

2005

Published in
Distributed Computing
Volume

18

Issue

1

Start page

85

End page

98

Note

National Licences

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Available on Infoscience
July 13, 2005
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/214529
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