Indulgent algorithms (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Indulgent algorithms (preliminary version)

Full text

Pdf (1.06 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing table of contents

Portland, Oregon, United States

Pages: 289 - 297

Year of Publication: 2000

ISBN:1-58113-183-6

Author

Rachid Guerraoui

Communication Systems Department, Swiss Federal Institute of Technology, CH 1015 Lausanne

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 18, Citation Count: 19

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/343477.343630 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Rida A. Bazzi , Gil Neiger, Simulating Crash Failures with Many Faulty Processors (Extended Abstract), Proceedings of the 6th International Workshop on Distributed Algorithms, p.166-184, November 02-04, 1992
	2	Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
	3	Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
	4	F. Cristian and C. Fetzer. The Timed Asynchronous System Model Technical Report, CSE 97-519, University of California at Saint Diego, 1997.
	5	Roberto De Prisco , Butler W. Lampson , Nancy A. Lynch, Revisiting the Paxos Algorithm, Proceedings of the 11th International Workshop on Distributed Algorithms, p.111-125, September 24-26, 1997
	6	Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
	7	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	8	Rachid Guerraoui, Revistiting the Relationship Between Non-Blocking Atomic Commitment and Consensus, Proceedings of the 9th International Workshop on Distributed Algorithms, p.87-100, September 13-15, 1995
	9	Vassos Hadzilacos , Sam Toueg, A Modular Approach to Fault-Tolerant Broadcasts and Related Problems, Cornell University, Ithaca, NY, 1994
	10	Michel Hurfin , Michel Raynal, A simple and fast asynchronous consensus protocol based on a weak failure detector, Distributed Computing, v.12 n.4, p.209-223, September 1999 [doi>10.1007/s004460050067]
	11	Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
	12	Brian M. Oki , Barbara H. Liskov, Viewstamped replication: a general primary copy, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.8-17, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62549]
	13	Laura S. Sabel , Keith Marzullo, Election Vs. Consensus in Asynchronous Systems, Cornell University, Ithaca, NY, 1995
	15	Fred B. Schneider, Decomposing Properties into Safety and Liveness, Cornell University, Ithaca, NY, 1987
	16	Fred B. Schneider, Replication management using the state-machine approach, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
	17	Dale Skeen, Nonblocking commit protocols, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582339]

CITED BY 19

	Jean-François Hermant , Gérard Le Lann, Fast Asynchronous Uniform Consensus in Real-Time Distributed Systems, IEEE Transactions on Computers, v.51 n.8, p.931-944, August 2002
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, The combined power of conditions and failure detectors to solve asynchronous set agreement, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Romain Boichat , Partha Dutta , Svend Frølund , Rachid Guerraoui, Deconstructing paxos, ACM SIGACT News, v.34 n.1, March 2003
	Idit Keidar , Sergio Rajsbaum, A simple proof of the uniform consensus synchronous lower bound, Information Processing Letters, v.85 n.1, p.47-52, 16 January 2003
	Partha Dutta , Rachid Guerraoui, The inherent price of indulgence, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Rachid Guerraoui, Non-blocking atomic commit in asynchronous distributed systems with failure detectors, Distributed Computing, v.15 n.1, p.17-25, January 2002
	Rachid Guerraoui , Michel Raynal, The Information Structure of Indulgent Consensus, IEEE Transactions on Computers, v.53 n.4, p.453-466, April 2004
	Michel Reynal, A short introduction to failure detectors for asynchronous distributed systems, ACM SIGACT News, v.36 n.1, March 2005
	Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Toward a theory of transactional contention managers, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Idit Keidar , Alexander Shraer, Timeliness, failure-detectors, and consensus performance, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Partha Dutta , Rachid Guerraoui, The inherent price of indulgence, Distributed Computing, v.18 n.1, p.85-98, July 2005
	Hagit Attiya , Fabian Kuhn , C. Greg Plaxton , Mirjam Wattenhofer , Roger Wattenhofer, Efficient adaptive collect using randomization, Distributed Computing, v.18 n.3, p.179-188, February 2006
	Weigang Wu , Jiannong Cao , Jin Yang , Michel Raynal, Using asynchrony and zero degradation to speed up indulgent consensus protocols, Journal of Parallel and Distributed Computing, v.68 n.7, p.984-996, July, 2008
	Sung Hoon Park, The election problem in asynchronous distributed systems with bounded faulty processes, The Journal of Supercomputing, v.41 n.1, p.89-104, July 2007
	Michel Raynal , Gadi Taubenfeld, The notion of a timed register and its application to indulgent synchronization, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Antonio Fernández , Michel Raynal, From an intermittent rotating star to a leader, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Piotr Zielinski, Anti-Ω: the weakest failure detector for set agreement, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	R. Guerraoui , N. Lynch, A general characterization of indulgence, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.3 n.4, p.1-19, November 2008
	Hein Meling , Alberto Montresor , Bjarne E. Helvik , Ozalp Babaoglu, Jgroup-ARM: a distributed object group platform with autonomous replication management, Software—Practice & Experience, v.38 n.9, p.885-923, July 2008