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. Conferences, Workshops, Symposiums, and Seminars
  4. On the Message Complexity of Indulgent Consensus
 
conference paper

On the Message Complexity of Indulgent Consensus

Gilbert, Seth  
•
Guerraoui, Rachid  
•
Kowalski, Dariusz R.
2007
Proceedings of the 21st International Symposium on Distributed Computing (DISC'07)
Symposium on Distributed Computing (DISC'07)

Many recommend planning for the worst and hoping for the best. In this paper we devise efficient indulgent consensus algorithms that can tolerate crash failures and arbitrarily long periods of asynchrony, and yet perform (asymptotically) optimally in well-behaved, synchronous executions with few failures. We present two such algorithms: In synchronous executions, the first has optimal message complexity, using only O(n) messages, but runs in superlinear time of O(n1+"). The second has a message complexity of O(n polylog(n)), but has an optimal running time, completing in O(f) rounds in synchronous executions with at most f failures. Both of these results improve significantly over the most message-efficient of previous indulgent consensus algorithms which have a message complexity of at least (n2) in well-behaved executions.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

cons-disc.pdf

Type

N/a

Access type

openaccess

License Condition

Copyright

Size

186.22 KB

Format

Adobe PDF

Checksum (MD5)

567ddc04070564c0f3c6f9a1057031dd

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