TY - GEN

T1 - Detecting global termination conditions in the face of uncertainty

AU - Afek, Yehuda

AU - Saks, Michael

N1 - Publisher Copyright:
© 1987 ACM.

PY - 1987/12/1

Y1 - 1987/12/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=84915333536&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84915333536&partnerID=8YFLogxK

U2 - 10.1145/41840.41850

DO - 10.1145/41840.41850

M3 - Conference contribution

AN - SCOPUS:84915333536

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 109

EP - 124

BT - Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing, PODC 1987

A2 - Schneider, Fred B.

PB - Association for Computing Machinery

T2 - 6th Annual ACM Symposium on Principles of Distributed Computing, PODC 1987

Y2 - 10 August 1987 through 12 August 1987

ER -