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 Impossibility of Boosting Distributed Service Resilience
 
conference paper

On the Impossibility of Boosting Distributed Service Resilience

Attie, Paul
•
Guerraoui, Rachid  
•
Kouznetsov, Petr  
Show more
2005
Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS 2005)
IEEE International Conference on Distributed Computing Systems (ICDCS 2005)

We show that no deterministic algorithm can solve consensus in the presence of t+1 process crash failures, in a system of n processes that communicate in a reliable way and synchronize their activities using any number of t-resilient services. These base services can range from any type of atomic objects shared by the processes (including consensus objects), to any class of non-atomic objects like failure detectors (including perfect ones), and broadcast primitives (including totally ordered one). The services are t-resilient in the sense that their liveness is guaranteed only if no more than t processes crash. Our boosting impossibility result applies also to the case where atomic object services can fail only because of failures of the processes connected to them. Interestingly, in this case, it is possible to boost the resilience level of the system solving problems easier than consensus. For example, we show that the k-set consensus problem is solvable for 2k-1 failures using consensus services that tolerate only 1 failure apiece.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1109/ICDCS.2005.79
Author(s)
Attie, Paul
Guerraoui, Rachid  
Kouznetsov, Petr  
Lynch, Nancy
Rajsbaum, Sergio
Date Issued

2005

Published in
Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS 2005)
Start page

39

End page

48

Written at

EPFL

EPFL units
DCL  
Event name
IEEE International Conference on Distributed Computing Systems (ICDCS 2005)
Available on Infoscience
July 13, 2005
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/214690
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