research-article

What model and what conditions to implement unreliable failure detectors in dynamic networks?

Authors:

Fabíola Greve,

Luciana Arantes,

Pierre SensAuthors Info & Claims

TADDS '11: Proceedings of the 3rd International Workshop on Theoretical Aspects of Dynamic Distributed Systems

Pages 13 - 17

https://doi.org/10.1145/2034640.2034645

Published: 19 September 2011 Publication History

Abstract

Failure detectors are classical mechanisms which provide information about process failures and can help systems to cope with the high dynamics of self-organizing, unstructured and mobile wireless networks. Unreliable failure detectors of class ◊S are of special interest because they meet the weakest assumptions able to solve fundamental problems on the design of dependable systems. Unfortunately, a negative result states that no failure detector of that class can be implemented in a network of an unknown membership; but full membership knowledge as well as fully communication connectivity are no longer appropriate assumptions to the new scenario of dynamic networks. In this paper, we provide a discussion about the conditions and model able to implement failure detectors in dynamic networks and define a new class, namely ◊S^M, which adapts the properties of the ◊S class to a dynamic network with an unknown membership.

References

[1]

M. K. Aguilera. A pleasant stroll through the land of infinitely many creatures. SIGACT News, 35(2):36--59, 2004.

Digital Library

[2]

M. K. Aguilera, W. Chen, and S. Toueg. Heartbeat: A timeout-free failure detector for quiescent reliable communication. In Proc. 11th Int. Work. on Distributed Algorithms, pages 126--140, 1997.

Digital Library

[3]

V. Bhandari and N. H. Vaidya. On reliable broadcast in a radio network. In 24th ACM Symp. on Principles of distributed computing, pages 138--147. ACM, 2005.

Digital Library

[4]

V. Bhandari and N. H. Vaidya. Reliable local broadcast in a wireless network prone to byzantine failures. In 4th ACM Int. Work. on Foundations of Mobile Computing, 2007.

[5]

V. Bhandari and N. H. Vaidya. Reliable broadcast in radio networks with locally bounded failures. IEEE Trans. on Parallel and Distributed Systems, 21:801--811, 2010.

Digital Library

[6]

T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. Wireless Communications & Mobile Computing: Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2:483--502, 2002.

[7]

J. Cao, M. Raynal, C. Travers, and W. Wu. The eventual leadership in dynamic mobile networking environments. In 3th Pacific Rim Int. Symp. on Dependable Computing, pages 123--130, 2007.

Digital Library

[8]

A. Casteigts, S. Chaumette, and A. Ferreira. Characterizing topological assumptions of distributed algorithms in dynamic networks. In Structural Information and Communication Complexity Conf., pages 126--140, 2010.

Digital Library

[9]

A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. Technical report, University of Ottawa, 2011.

[10]

T. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225--267, Mar. 1996.

Digital Library

[11]

B. Devianov and S. Toueg. Failure detector service for dependable computing. In Proc. 1st Int. Conf. on Dependable Syst. and Networks, pages 14--15, 2000.

[12]

R. Friedman and G. Tcharny. Evaluating failure detection in mobile ad-hoc networks. Int. Journal of Wireless and Mobile Computing, 1(8), 2005.

[13]

F. Greve, P. Sens, L. Arantes, and V. Simon. A failure detector for wireless networks with unknown membership. In Euro-Par Conference, LNCS 6853, pages 27--38, 2011.

Digital Library

[14]

I. Gupta, T. D. Chandra, and G. S. Goldszmidt. On scalable and efficient distributed failure detectors. In Proc. of the 20th Symp. on Principles of Distributed Computing, pages 170--179, 2001.

Digital Library

[15]

M. Hutle. An efficient failure detector for sparsely connected networks. In Proc. IASTED Int. Conf. on Parallel and Distributed Computing and Networks, pages 369--374, 2004.

[16]

E. Jiménez, S. Arévalo, and A. Fernández. Implementing unreliable failure detectors with unknown membership. Inf. Process. Lett., 100(2):60--63, 2006.

Digital Library

[17]

C.-Y. Koo. Broadcast in radio networks tolerating byzantine adversarial behavior. In 23th Symp. on Princ. of Distributed Computing, pages 275--282, 2004.

Digital Library

[18]

S. Min-Te, H. Lifei, A. A. Arora, and L. Ten-Hwang. Reliable mac layer multicast in ieee 802.11 wireless networks. In Proc. of the Int. Conference on Parallel Processing, pages 527--536, Aug. 2002.

Digital Library

[19]

A. Mostefaoui, E. Mourgaya, and M. Raynal. Asynchronous implementation of failure detectors. In Proc. of Int. Conf. on Dependable Systems and Networks, 2003.

[20]

A. Mostefaoui, M. Raynal, and C. Travers. Time-free and timer-based assumptions can be combined to obtain eventual leadership. IEEE Trans. Parallel Distrib. Syst., 17(7):656--666, 2006.

Digital Library

[21]

A. Mostefaoui, M. Raynal, C. Travers, S. Patterson, D. Agrawal, and A. Abbadi. From static distributed systems to dynamic systems. In 24th IEEE Symp. on Reliable Distributed Systems, pages 109--118, 2005.

Digital Library

[22]

N. Sridhar. Decentralized local failure detection in dynamic distributed systems. The 25th IEEE Symp. on Reliable Distributed Systems, 0:143--154, 2006.

Digital Library

[23]

A. Tai, K. Tso, and W. Sanders. Cluster-based failure detection service for large-scale ad hoc wireless network applications. In Int. Conf. on Dependable Systems and Networks, pages 805--814, 2004.

Digital Library

[24]

S. Tucci-Piergiovanni and R. Baldoni. Eventual leader election in infinite arrival message-passing system model with bounded concurrency. In Dependable Computing Conference (EDCC), pages 127--134, 2010.

Digital Library

[25]

R. Van Renesse, Y. Minsky, and M. Hayden. A gossip-style failure detection service. Technical report, Ithaca, NY, USA, 1998.

Digital Library

Cited By

Mauffret EVernier FMonnet S(2023)The Burden of Time on a Large-Scale Data Management ServiceAdvanced Information Networking and Applications10.1007/978-3-031-29056-5_23(248-260)Online publication date: 20-Mar-2023
https://doi.org/10.1007/978-3-031-29056-5_23
Vargas KRajsbaum SRaynal M(2020)An Eventually Perfect Failure Detector for Networks of Arbitrary Topology Connected with ADD Channels Using Time-To-Live ValuesParallel Processing Letters10.1142/S012962642050006130:02(2050006)Online publication date: 17-Jul-2020
https://doi.org/10.1142/S0129626420500061
Jarrah HAli GKumar AChong PSarkar NGutierrez J(2020)The Time-Free Comparison Model for Fault Diagnosis in Wireless Ad Hoc NetworksMobile Networks and Applications10.1007/s11036-020-01691-427:2(469-482)Online publication date: 18-Nov-2020
https://doi.org/10.1007/s11036-020-01691-4
Show More Cited By

Index Terms

What model and what conditions to implement unreliable failure detectors in dynamic networks?
1. Software and its engineering
  1. Software organization and properties
    1. Extra-functional properties
      1. Software fault tolerance
    2. Software system structures
      1. Distributed systems organizing principles
        Organizing principles for web applications

Recommendations

A failure detector for wireless networks with unknown membership
Euro-Par'11: Proceedings of the 17th international conference on Parallel processing - Volume Part II

The distributed computing scenario is rapidly evolving for integrating self-organizing and dynamic wireless networks. Unreliable failure detectors are classical mechanisms which provide information about process failures and can help systems to cope ...
Unreliable failure detectors for reliable distributed systems

We introduce the concept of unreliable failure detectors and study how they can be used to solve Consensus in asynchronous systems with crash failures. We characterise unreliable failure detectors in terms of two properties—completeness and accuracy. We ...
On the Implementation of Unreliable Failure Detectors in Partially Synchronous Systems

Unreliable failure detectors were proposed by Chandra and Toueg as mechanisms that provide information about process failures. Chandra and Toueg defined eight classes of failure detectors, depending on how accurate this information is, and presented an ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

TADDS '11: Proceedings of the 3rd International Workshop on Theoretical Aspects of Dynamic Distributed Systems

September 2011

33 pages

ISBN:9781450309462

DOI:10.1145/2034640

General Chairs:
Roberto Baldoni
University of Rome
,
Alexander A. Shvarstman
University of Connecticut

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 September 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

TADDS '11

TADDS '11: Workshop on Theoretical Aspects on Dynamic Distributed Systems

September 19, 2011

Rome, Italy

Acceptance Rates

Overall Acceptance Rate 5 of 8 submissions, 63%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
98
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mauffret EVernier FMonnet S(2023)The Burden of Time on a Large-Scale Data Management ServiceAdvanced Information Networking and Applications10.1007/978-3-031-29056-5_23(248-260)Online publication date: 20-Mar-2023
https://doi.org/10.1007/978-3-031-29056-5_23
Vargas KRajsbaum SRaynal M(2020)An Eventually Perfect Failure Detector for Networks of Arbitrary Topology Connected with ADD Channels Using Time-To-Live ValuesParallel Processing Letters10.1142/S012962642050006130:02(2050006)Online publication date: 17-Jul-2020
https://doi.org/10.1142/S0129626420500061
Jarrah HAli GKumar AChong PSarkar NGutierrez J(2020)The Time-Free Comparison Model for Fault Diagnosis in Wireless Ad Hoc NetworksMobile Networks and Applications10.1007/s11036-020-01691-427:2(469-482)Online publication date: 18-Nov-2020
https://doi.org/10.1007/s11036-020-01691-4
Vargas KRajsbaum S(2019)An Eventually Perfect Failure Detector for Networks of Arbitrary Topology Connected with ADD Channels Using Time-To-Live Values2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN.2019.00038(264-275)Online publication date: Jun-2019
https://doi.org/10.1109/DSN.2019.00038
Jarrah HChong PSarkar NGutierrez J(2016)A Time-Free Comparison-Based System-Level Fault Diagnostic Model for Highly Dynamic NetworksProceedings of the 11th International Conference on Queueing Theory and Network Applications10.1145/3016032.3016045(1-6)Online publication date: 13-Dec-2016
https://dl.acm.org/doi/10.1145/3016032.3016045
Casteigts AFlocchini PMans BSantoro N(2014)Measuring Temporal Lags in Delay-Tolerant NetworksIEEE Transactions on Computers10.1109/TC.2012.20863:2(397-410)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1109/TC.2012.208
Huaquan HHanchen SLingda WChao Y(2014)Visual Models of Time-Varying Topology of Space-Based NetworksProceedings of the 2014 International Conference on Virtual Reality and Visualization10.1109/ICVRV.2014.4(392-395)Online publication date: 30-Aug-2014
https://dl.acm.org/doi/10.1109/ICVRV.2014.4

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten