Communication-efficient failure detection and consensus in omission environments

Freiling F, Soraluze I, Larrea M, Lafuente A, Cortinas R (2011)

Publication Type: Journal article, Original article

Publication year: 2011

Journal

Information Processing Letters Elsevier

Publisher: Elsevier

Book Volume: 111

Pages Range: 262-268

Journal Issue: 6

DOI: 10.1016/j.ipl.2010.12.008

Abstract

Failure detectors have been shown to be a very useful mechanism to solve the consensus problem in the crash failure model, for which a number of communication-efficient algorithms have been proposed. In this paper we deal with the definition, implementation and use of communication-efficient failure detectors in the general omission failure model, where processes can fail by crashing and by omitting messages when sending and/or receiving. We first define a new failure detector class for this model in terms of completeness and accuracy properties. Then we propose an algorithm that implements a failure detector of the proposed class in a communication-efficient way, in the sense that only a linear number of links are used to send messages forever. We also explain how the well-known consensus algorithm of Chandra and Toueg can be adapted in order to use the proposed failure detector. © 2010 Elsevier B.V.

Authors with CRIS profile

Felix Freiling Lehrstuhl für Informatik 1 (IT-Sicherheitsinfrastrukturen)

Involved external institutions

University of Basque Country / Universidad del Pais Vasco (UPV) / Euskal Herriko Unibersitatea (EHU) ES Spain (ES)

How to cite

APA:

Freiling, F., Soraluze, I., Larrea, M., Lafuente, A., & Cortinas, R. (2011). Communication-efficient failure detection and consensus in omission environments. Information Processing Letters, 111(6), 262-268. https://dx.doi.org/10.1016/j.ipl.2010.12.008

MLA:

Freiling, Felix, et al. "Communication-efficient failure detection and consensus in omission environments." Information Processing Letters 111.6 (2011): 262-268.

BibTeX: Download