Detecting global termination conditions in the face of uncertainty

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