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

boosting-tr.pdf

Access type

openaccess

Size

280.79 KB

Format

Adobe PDF

Checksum (MD5)

fbf3b6235d9fea6a90118e082faa3386

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