Detecting global termination conditions in the face of uncertainty

Yehuda Afek, Michael Saks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

We introduce a new problem, the Token Collection Problem for distributed networks, which models the general problem of detecting termination conditions in systems which contain uncertainty. We consider a rooted tree in which tokens appear spontaneously at the nodes at arbitrary times. The Token Collection Problem with threshold t, (TCP(r)). is to collect t tokens at the root. Besides modeling fault-tolerant termination detection, this problem arises in other distributed algorithms, such as. fault-tolerant election, resow acquisition, network recovery. and token d ribution. A message-efficient distributed algorithm for the TCP(t) is presented. which uses 0(n · log2t · log2r) messages where n is the total number of nodes. and r is the height of the tree. Using the algorithm as a mechanism for termination detection we establish an 0(m+n · log5n) messages upper bound on the problem of fault-tolerant election, where m is the total number of links in the network. This improves on the previous upper bound of O(n2) messages of Bar-Yehuda and Kutten [B86].

Original languageEnglish (US)
Title of host publicationProceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing, PODC 1987
EditorsFred B. Schneider
PublisherAssociation for Computing Machinery
Pages109-124
Number of pages16
ISBN (Electronic)089791239X
DOIs
StatePublished - Dec 1 1987
Event6th Annual ACM Symposium on Principles of Distributed Computing, PODC 1987 - Vancouver, Canada
Duration: Aug 10 1987Aug 12 1987

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing
VolumePart F130235

Other

Other6th Annual ACM Symposium on Principles of Distributed Computing, PODC 1987
Country/TerritoryCanada
CityVancouver
Period8/10/878/12/87

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Detecting global termination conditions in the face of uncertainty'. Together they form a unique fingerprint.

Cite this