Fault-Tolerant Termination Detection with Safra’s Algorithm

Georgios Karlos; Wan Fokkink; Per Fuchs

doi:10.1007/978-3-030-91014-3_5

Fault-Tolerant Termination Detection with Safra’s Algorithm

Georgios Karlos^*
, Wan Fokkink
, Per Fuchs

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

224 Downloads (Pure)

Abstract

Safra’s distributed termination detection algorithm employs a logical token ring structure within a distributed network; only passive nodes forward the token, and a counter in the token keeps track of the number of sent minus the number of received messages. We adapt this classic algorithm to make it fault-tolerant. The counter is split into counters per node, to discard counts from crashed nodes. If a node crashes, the token ring is restored locally and a backup token is sent. Nodes inform each other of detected crashes via the token. Our algorithm imposes no additional message overhead, tolerates any number of crashes as well as simultaneous crashes, and copes with crashes in a decentralized fashion. Experiments with an implementation of our algorithm were performed on top of two fault-tolerant distributed algorithms.

Original language	English
Title of host publication	Networked Systems
Subtitle of host publication	9th International Conference, NETYS 2021, Virtual Event, May 19–21, 2021, Proceedings
Editors	Karima Echihabi, Roland Meyer
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	71-87
Number of pages	17
ISBN (Electronic)	9783030910143
ISBN (Print)	9783030910136
DOIs	https://doi.org/10.1007/978-3-030-91014-3_5
Publication status	Published - 2021
Event	9th International Conference on Networked Systems, NETYS 2021 - Virtual, Online Duration: 19 May 2021 → 21 May 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12754 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Networked Systems, NETYS 2021
City	Virtual, Online
Period	19/05/21 → 21/05/21

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Access to Document

10.1007/978-3-030-91014-3_5

Karlos2021_Chapter_Fault-TolerantTerminationDetectionWithSafrasAlgorithmFinal published version, 710 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

Karlos, G., Fokkink, W., & Fuchs, P. (2021). Fault-Tolerant Termination Detection with Safra’s Algorithm. In K. Echihabi, & R. Meyer (Eds.), Networked Systems: 9th International Conference, NETYS 2021, Virtual Event, May 19–21, 2021, Proceedings (pp. 71-87). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12754 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-91014-3_5

Karlos, Georgios ; Fokkink, Wan ; Fuchs, Per. / Fault-Tolerant Termination Detection with Safra’s Algorithm. Networked Systems: 9th International Conference, NETYS 2021, Virtual Event, May 19–21, 2021, Proceedings. editor / Karima Echihabi ; Roland Meyer. Springer Science and Business Media Deutschland GmbH, 2021. pp. 71-87 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{450d3dab85a3415bb23a989ad88cb0fd,

title = "Fault-Tolerant Termination Detection with Safra{\textquoteright}s Algorithm",

abstract = "Safra{\textquoteright}s distributed termination detection algorithm employs a logical token ring structure within a distributed network; only passive nodes forward the token, and a counter in the token keeps track of the number of sent minus the number of received messages. We adapt this classic algorithm to make it fault-tolerant. The counter is split into counters per node, to discard counts from crashed nodes. If a node crashes, the token ring is restored locally and a backup token is sent. Nodes inform each other of detected crashes via the token. Our algorithm imposes no additional message overhead, tolerates any number of crashes as well as simultaneous crashes, and copes with crashes in a decentralized fashion. Experiments with an implementation of our algorithm were performed on top of two fault-tolerant distributed algorithms.",

author = "Georgios Karlos and Wan Fokkink and Per Fuchs",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 9th International Conference on Networked Systems, NETYS 2021 ; Conference date: 19-05-2021 Through 21-05-2021",

year = "2021",

doi = "10.1007/978-3-030-91014-3\_5",

language = "English",

isbn = "9783030910136",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "71--87",

editor = "Karima Echihabi and Roland Meyer",

booktitle = "Networked Systems",

address = "Germany",

}

Karlos, G , Fokkink, W & Fuchs, P 2021, Fault-Tolerant Termination Detection with Safra’s Algorithm. in K Echihabi & R Meyer (eds), Networked Systems: 9th International Conference, NETYS 2021, Virtual Event, May 19–21, 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12754 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 71-87, 9th International Conference on Networked Systems, NETYS 2021, Virtual, Online, 19/05/21. https://doi.org/10.1007/978-3-030-91014-3_5

Fault-Tolerant Termination Detection with Safra’s Algorithm. / Karlos, Georgios ; Fokkink, Wan; Fuchs, Per.
Networked Systems: 9th International Conference, NETYS 2021, Virtual Event, May 19–21, 2021, Proceedings. ed. / Karima Echihabi; Roland Meyer. Springer Science and Business Media Deutschland GmbH, 2021. p. 71-87 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12754 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Fault-Tolerant Termination Detection with Safra’s Algorithm

AU - Karlos, Georgios

AU - Fokkink, Wan

AU - Fuchs, Per

PY - 2021

Y1 - 2021

N2 - Safra’s distributed termination detection algorithm employs a logical token ring structure within a distributed network; only passive nodes forward the token, and a counter in the token keeps track of the number of sent minus the number of received messages. We adapt this classic algorithm to make it fault-tolerant. The counter is split into counters per node, to discard counts from crashed nodes. If a node crashes, the token ring is restored locally and a backup token is sent. Nodes inform each other of detected crashes via the token. Our algorithm imposes no additional message overhead, tolerates any number of crashes as well as simultaneous crashes, and copes with crashes in a decentralized fashion. Experiments with an implementation of our algorithm were performed on top of two fault-tolerant distributed algorithms.

AB - Safra’s distributed termination detection algorithm employs a logical token ring structure within a distributed network; only passive nodes forward the token, and a counter in the token keeps track of the number of sent minus the number of received messages. We adapt this classic algorithm to make it fault-tolerant. The counter is split into counters per node, to discard counts from crashed nodes. If a node crashes, the token ring is restored locally and a backup token is sent. Nodes inform each other of detected crashes via the token. Our algorithm imposes no additional message overhead, tolerates any number of crashes as well as simultaneous crashes, and copes with crashes in a decentralized fashion. Experiments with an implementation of our algorithm were performed on top of two fault-tolerant distributed algorithms.

UR - https://www.scopus.com/pages/publications/85121875744

UR - https://www.scopus.com/pages/publications/85121875744#tab=citedBy

U2 - 10.1007/978-3-030-91014-3_5

DO - 10.1007/978-3-030-91014-3_5

M3 - Conference contribution

AN - SCOPUS:85121875744

SN - 9783030910136

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 71

EP - 87

BT - Networked Systems

A2 - Echihabi, Karima

A2 - Meyer, Roland

PB - Springer Science and Business Media Deutschland GmbH

T2 - 9th International Conference on Networked Systems, NETYS 2021

Y2 - 19 May 2021 through 21 May 2021

ER -

Karlos G , Fokkink W, Fuchs P. Fault-Tolerant Termination Detection with Safra’s Algorithm. In Echihabi K, Meyer R, editors, Networked Systems: 9th International Conference, NETYS 2021, Virtual Event, May 19–21, 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 71-87. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2021 Dec 2. doi: 10.1007/978-3-030-91014-3_5

Fault-Tolerant Termination Detection with Safra’s Algorithm

Abstract

Publication series

Conference

Bibliographical note

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this