Distributed termination detection revisited

We consider a network of $N$ machines $M[i]$ (osic $< N$ ). Each machine is either active or passive. A passive machine becomes active upon receipt of a message; only active machines send messages and an active machine may turn itself into a passive one. When all machines are passive they remain so and we say that the computation has terminated. Message transmission between two machines is regarded as instantaneous. The problem is to detect in $M[0]$ that the computation has terminated. The following design solves the problem under the assumption that each $M[i]$ "can transmit the marker" to $M[(i+1) \mod N]$ .

We imagine -as is not unusual- the machines in a linear arrangement such that "M[i] is to the left of M[j]" means $i < j$ . The marker is either black or white, and so is each machine. The system maintains the following invariant

P: the machines to the left of the marker are passive or the marker is black or

at the marker or at its right exists a black machine.

When M[o] owns the marker, P holds regardless of the marker's colour and it can initiate a probe by making the marker white. If the marker travels to the right under invariance of P, the computation has terminated when M[N-1] transmits a white marker to M[o]; when M[o] has received a black marker from M[N-1], it can initiate a next probe.

In order that message sending - which may activate a passive machine - does not violate P, a machine sending a message to a machine to its left makes itself black.

Only passive machines transmit the marker; as a result, an active machine receiving the marker keeps it as long as it remains active.

A white machine transmits the marker in its current colour; a black machine transmits the marker black and

makes itself white. In neither case marker transmission violates $p$ .

Since passive machines transmit the marker, the marker will reach M[0] when the computation has terminated. Since there may be black machines, one more probe - but only one! - may return a black marker; the next probe will return a white marker to M[o] and detection is therefore guaranteed.

Note. A message sending machine may always make itself black, regardless of the direction in which it sends its message. (End of Note.)

Note. We have described our solution as if also marker transmission were instantaneous. By defining the place of the marker as the machine that has it or is going to get it, $P$ remains invariant. In other words: the edges of the network don't need to provide the cyclic path directly. (End of Note.)

For the above I am greatly indebted to K. Mani Chandy and Jayadev Misra of the Computer Sciences Department of the University of Texas at Austin. They considered a string of machines, each only sending messages to its immediate neighbour(s), with an uncoloured marker travelling back and forth.

Plataansstraat 5 SG71 AL NUENEN The Netherlands

17 June 1982 prof. dr. Edsger W. Dgkstra Burroughs Research Fellow