Detecting termination of distributed computations by external agents

An algorithm is presented that defects for termination of distributed computations by an auxiliary controlling agent. The algorithm assigns a weight W, 0<W⩽1, to each active process and to each message in transit. The algorithm maintains that the sum of all the weights related to the computation is equal to one. The controlling agent terminates the algorithm if its weight equals one. A space-efficient scheme is proposed to encode the weights such that an active process can send a very large number of messages before reaching a weight equal to one. Thus, in the proposed encoding scheme, each process and message needs only a small number of bits to encode the weight; the processes can be almost free from the delays of waiting for a supply of weights from the controlling agent