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
Loading...
Thumbnail Image
Name

Publisher's version.pdf

Type

Publisher's Version

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

Size

1.28 MB

Format

Adobe PDF

Checksum (MD5)

5d094a8eabf5e25b2541be311f03b9e1

Loading...
Thumbnail Image
Name

IC_TECH_REPORT_200231.pdf

Access type

openaccess

Size

296.34 KB

Format

Adobe PDF

Checksum (MD5)

677739b5f957b6c1727192b0da675df0

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