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 proceedingConference contributionAcademicpeer-review

88 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 languageEnglish
Title of host publicationNetworked Systems
Subtitle of host publication9th International Conference, NETYS 2021, Virtual Event, May 19–21, 2021, Proceedings
EditorsKarima Echihabi, Roland Meyer
PublisherSpringer Science and Business Media Deutschland GmbH
Pages71-87
Number of pages17
ISBN (Electronic)9783030910143
ISBN (Print)9783030910136
DOIs
Publication statusPublished - 2021
Event9th International Conference on Networked Systems, NETYS 2021 - Virtual, Online
Duration: 19 May 202121 May 2021

Publication series

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

Conference

Conference9th International Conference on Networked Systems, NETYS 2021
CityVirtual, Online
Period19/05/2121/05/21

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Fingerprint

Dive into the research topics of 'Fault-Tolerant Termination Detection with Safra’s Algorithm'. Together they form a unique fingerprint.

Cite this