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 | |
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.