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 impossibility of boosting distributed service resilience
 
research article

The impossibility of boosting distributed service resilience

Attie, Paul
•
Guerraoui, Rachid  
•
Kuznetsov, Petr
Show more
2011
Information and Computation

We study f -resilient services, which are guaranteed to operate as long as no more than f of the associated processes fail. We prove three theorems asserting the impossibility of boosting the resilience of such services. Our first theorem allows any connection pattern between processes and services but assumes these services to be atomic (linearizable) objects. This theorem says that no distributed system in which processes coordinate using f -resilient atomic objects and reliable registers can solve the consensus problem in the presence of f + 1 undetectable process stopping failures. In contrast, we show that it is possible to boost the resilience of some systems solving problems easier than consensus: for example, the 2-set consensus problem is solvable for 2n processes and 2n − 1 failures (i.e., wait-free) using n-process consensus services resilient to n − 1 failures (wait-free). Our proof is short and self-contained. We then introduce the larger class of failure-oblivious services. These are services that cannot use information about failures, although they may behave more flexibly than atomic objects. An example of such a service is totally ordered broadcast. Our second theorem generalizes the first theorem and its proof to failure-oblivious services. Our third theorem allows the system to contain failure-aware services, such as failure de- tectors, in addition to failure-oblivious services. This theorem requires that each failure-aware service be connected to all processes; thus, f +1 process failures overall can disable all the failure- aware services. In contrast, it is possible to boost the resilience of a system solving consensus using failure-aware services if arbitrary connection patterns between processes and services are allowed: consensus is solvable for any number of failures using only 1-resilient 2-process perfect failure detectors. As far as we know, this is the first time a unified framework has been used to describe both atomic and non-atomic objects, and the first time boosting analysis has been performed for services more general than atomic objects.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1016/j.ic.2010.07.005
Author(s)
Attie, Paul
Guerraoui, Rachid  
Kuznetsov, Petr
Lynch, Nancy
Rajsbaum, Sergio
Date Issued

2011

Publisher

Elsevier

Published in
Information and Computation
Volume

209

Issue

6

Start page

927

End page

950

Subjects

distributed services

•

resilience

Editorial or Peer reviewed

NON-REVIEWED

Written at

EPFL

EPFL units
DCL  
Available on Infoscience
June 12, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/115069
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