On the Impossibility of Implementing Perpetual Failure Detectors in Partially Synchronous Systems

P
PDP
2002
10th Euromicro Workshop on Parallel, Distributed and Network-based Processing (EUROMICRO-PDP 2002)
Abstract - On the Impossibility of Implementing Perpetual Failure Detectors in Partially Synchronous Systems

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Mikel Larrea Articles by Antonio Fernández Articles by Sergio Arévalo

10th Euromicro Workshop on Parallel, Distributed and Network-based Processing (EUROMICRO-PDP 2002)

Canary Islands, Spain

January 09-January 11

ISBN: 0-7695-1444-8

	ASCII Text	x
	Mikel Larrea, Antonio Fernández, Sergio Arévalo, "On the Impossibility of Implementing Perpetual Failure Detectors in Partially Synchronous Systems," Parallel, Distributed, and Network-Based Processing, Euromicro Conference on, pp. 0099, 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing (EUROMICRO-PDP 2002), 2002.

	BibTex	x
	@article{ 10.1109/EMPDP.2002.994241, author = {Mikel Larrea and Antonio Fernández and Sergio Arévalo}, title = {On the Impossibility of Implementing Perpetual Failure Detectors in Partially Synchronous Systems}, journal ={Parallel, Distributed, and Network-Based Processing, Euromicro Conference on}, volume = {0}, year = {2002}, issn = {1066-6192}, pages = {0099}, doi = {http://doi.ieeecomputersociety.org/10.1109/EMPDP.2002.994241}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel, Distributed, and Network-Based Processing, Euromicro Conference on TI - On the Impossibility of Implementing Perpetual Failure Detectors in Partially Synchronous Systems SN - 1066-6192 SP EP A1 - Mikel Larrea, A1 - Antonio Fernández, A1 - Sergio Arévalo, PY - 2002 KW - consensus KW - uniform reliable broadcast KW - crash failures KW - failure detectors KW - perpetual accuracy KW - partial synchrony VL - 0 JA - Parallel, Distributed, and Network-Based Processing, Euromicro Conference on ER -

Mikel Larrea, Universidad del Pa?s Vasco

Antonio Fernández, Universidad Rey Juan Carlos

Sergio Arévalo, Universidad Rey Juan Carlos

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/EMPDP.2002.994241

In this paper we study the implementability of different classes of failure detectors in several models of partial synchrony. We show that no failure detector with perpetual accuracy (namely, P, Q, S, and W) can be implemented in any of the models of partial synchrony proposed in [2] and [4] in systems with even a single failure. We also show that, in these models of partial synchrony, it is necessary a majority of correct processes to implement a failure detector of class Theta.

Index Terms:

consensus, uniform reliable broadcast, crash failures, failure detectors, perpetual accuracy, partial synchrony

Citation:

Mikel Larrea, Antonio Fernández, Sergio Arévalo, "On the Impossibility of Implementing Perpetual Failure Detectors in Partially Synchronous Systems," pdp, pp.0099, 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing (EUROMICRO-PDP 2002), 2002

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.