Show simple item record

dc.contributor.authorAttie, Paul
dc.contributor.authorGuerraoui, Rachid
dc.contributor.authorKouznetsov, Petr
dc.contributor.authorLynch, Nancy
dc.contributor.authorRajsbaum, Sergio
dc.contributor.otherTheory of Computation
dc.date.accessioned2005-12-22T02:24:53Z
dc.date.available2005-12-22T02:24:53Z
dc.date.issued2005-02-25
dc.identifier.otherMIT-CSAIL-TR-2005-013
dc.identifier.otherMIT-LCS-TR-982
dc.identifier.urihttp://hdl.handle.net/1721.1/30526
dc.description.abstractWe prove two theorems saying that no distributed system in whichprocesses coordinate using reliable registers and f-resilient servicescan solve the consensus problem in the presence of f+1 undetectableprocess stopping failures. (A service is f-resilient if it isguaranteed to operate as long as no more than f of the processesconnected to it fail.)Our first theorem assumes that the given services are atomic objects,and allows any connection pattern between processes and services. Incontrast, we show that it is possible to boost the resilience ofsystems solving problems easier than consensus: the k-set consensusproblem is solvable for 2k-1 failures using 1-resilient consensusservices. The first theorem and its proof generalize to the largerclass of failure-oblivious services.Our second theorem allows the system to contain failure-awareservices, such as failure detectors, in addition to failure-obliviousservices; however, it requires that each failure-aware service beconnected to all processes. Thus, f+1 process failures overall candisable all the failure-aware services. In contrast, it is possibleto boost the resilience of a system solving consensus if arbitrarypatterns of connectivity are allowed between processes andfailure-aware services: consensus is solvable for any number offailures using only 1-resilient 2-process perfect failure detectors.
dc.format.extent20 p.
dc.format.extent30546523 bytes
dc.format.extent1297125 bytes
dc.format.mimetypeapplication/postscript
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.relation.ispartofseriesMassachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory
dc.titleImpossibility of boosting distributed service resilience


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record