NDLI: On the weakest failure detector ever

Please wait, while we are loading the content...

On the weakest failure detector ever

Content Provider	Springer Nature Link
Author	Guerraoui, Rachid Herlihy, Maurice Kuznetsov, Petr Lynch, Nancy Newport, Calvin
Copyright Year	2009
Abstract	Many problems in distributed computing are impossible to solve when no information about process failures is available. It is common to ask what information about failures is necessary and sufficient to circumvent some specific impossibility, e.g., consensus, atomic commit, mutual exclusion, etc. This paper asks what information about failures is necessary to circumvent any impossibility and sufficient to circumvent some impossibility. In other words, what is the minimal yet non-trivial failure information. We present an abstraction, denoted $${\Upsilon}$$ , that provides very little information about failures. In every run of the distributed system, $${\Upsilon}$$ eventually informs the processes that some set of processes in the system cannot be the set of correct processes in that run. Although seemingly weak, for it might provide random information for an arbitrarily long period of time, and it eventually excludes only one set of processes (among many) that is not the set of correct processes in the current run, $${\Upsilon}$$ still captures non-trivial failure information. We show that $${\Upsilon}$$ is sufficient to circumvent the fundamental wait-free set-agreement impossibility. While doing so, (a) we disprove previous conjectures about the weakest failure detector to solve set-agreement and (b) we prove that solving set-agreement with registers is strictly weaker than solving n + 1-process consensus using n-process consensus. We show that $${\Upsilon}$$ is the weakest stable non-trivial failure detector: any stable failure detector that circumvents some wait-free impossibility provides at least as much information about failures as $${\Upsilon}$$ does. Our results are generalized, from the wait-free to the f-resilient case, through an abstraction $${\Upsilon^f}$$ that we introduce and prove minimal to solve any problem that cannot be solved in an f-resilient manner, and yet sufficient to solve f-resilient f-set-agreement.
Starting Page	353
Ending Page	366
Page Count	14
File Format	PDF
ISSN	01782770
Journal	Distributed Computing
Volume Number	21
Issue Number	5
e-ISSN	14320452
Language	English
Publisher	Springer-Verlag
Publisher Date	2009-01-30
Publisher Place	Berlin/Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Theory of Computation Software Engineering/Programming and Operating Systems Computer Systems Organization and Communication Networks Computer Hardware Computer Communication Networks
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Anti-Ω: the weakest failure detector for set agreement

The weakest failure detector to solve nonuniform consensus

Renaming and the weakest family of failure detectors

The weakest failure detectors to boost obstruction-freedom

Failure detectors as type boosters

On the computability power and the robustness of set agreement-oriented failure detector classes

The overhead of consensus failure recovery

Special issue on PODC 2008

Special issue on DISC 2011

On the weakest failure detector ever

Similar Documents

Anti-Ω: the weakest failure detector for set agreement

The weakest failure detector to solve nonuniform consensus

Renaming and the weakest family of failure detectors

The weakest failure detectors to boost obstruction-freedom

Failure detectors as type boosters

On the computability power and the robustness of set agreement-oriented failure detector classes

The overhead of consensus failure recovery

Special issue on PODC 2008

Special issue on DISC 2011

On the weakest failure detector ever