Indulgent algorithms (preliminary version)
- 16 July 2000
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 289-297
- https://doi.org/10.1145/343477.343630
Abstract
Informally, an indulgent algorithm is a distributed algorithm that tolerates unreliable failure detection: the algorithm is indulgent towards its failure detector. This paper formally characterises such algorithms and states some of their interesting features. We show that indulgent algorithms are inherently safe and uniform. We also state impossibility results for indulgent solutions to divergent problems like consensus, and failure-sensitive problems like non-blocking atomic commit and terminating reliable broadcast.Keywords
This publication has 8 references indexed in Scilit:
- A simple and fast asynchronous consensus protocol based on a weak failure detectorDistributed Computing, 1999
- The part-time parliamentACM Transactions on Computer Systems, 1998
- The weakest failure detector for solving consensusJournal of the ACM, 1996
- Unreliable failure detectors for reliable distributed systemsJournal of the ACM, 1996
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- Viewstamped replication: a general primary copyPublished by Association for Computing Machinery (ACM) ,1988
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Nonblocking commit protocolsPublished by Association for Computing Machinery (ACM) ,1981