Keywords: distributed termination detection, asynchronous message passing, Bell-man-Ford algorithm.

In this paper we investigate a pair of termination detection algorithms based on overlapping intervals to determine the global state of the system at some instant of time and the charged system metaphor to determine that no messages are in transit. We prove the cor-
rectness of these techniques and experimentally compare their performance to the conventional technique of maintaining a tree of active locations (objects or processes).

E_i -> E_j
mean that event E_i sends a message that immediately triggers event E_j. (In MDC90, the language we use, there are no processes, and the only causality between events is in fact by message passing. For more conventional languages, please consider the activation
stack to be a message passed between sequential events within a process.)

The relation ->⁺ is the transitive closure of ->.
E_i->⁺E_j
means either E_i-> E_j or there is an event E_k such that E_i-> E_k and E_k ->⁺ E_j.
The relation ->⁺ induces a partial temporal order on the events in the algorithm. We say
E_i precedes E_j (E_j follows E_i) if E_i->⁺ E_j.

We can linearize the events in the execution of the algorithm, numbering them so that if E_i->⁺ E_j then i<j. Further, if i<j then E_i precedes E_j in the ordering (they are not necessarily ordered via messages). Our use of "linearize" is derived from [HERL87], albeit simplified by the functional nature of computational events and their mutual exclusion at locations.

The k^th interval at location i is the time between probe P_i(k-1) and P_ik. (P_i0 is defined as the beginning of the execution at location i.)
We create overlapping intervals by requiring that
P_i(k-1)->⁺ P_jk
for all locations i and j and probe number k>0. The set of all intervals P_i(k-1) to P_ik will be the k^th set of overlapping intervals.
Two techniques for achieving sets of overlapping intervals are cyclic probes and probe trees.
Cyclic probe. In the cyclic probe method [DIJK83], a probe message travels from location to location around a ring. Suppose the locations are numbered L₁, L₂ , ..., L_n and the probe message visits them in ascending order. Then
P_ik -> P_(i+1)k i<n
P_nk -> P_1(k+1)
Clearly
P_ik ->⁺P_j(k+1) for all locations L_i ,L_j

Probe tree. In the tree method [FRAN82] [TOPO84], one location L_r is selected as the root, a set of locations, I, are the internal nodes, and the remaining locations form the set of leaf nodes, F. If there is more than one location, then L_r is in set I. We shall assume this case, since a single location system does not need elaborate termination detection.
We define a function parent that maps each location other than L_r into its parent in the tree. Since the locations form a tree, there are no cycles in the parent graph. For any location L_i not in F, children(L_i) = {L_j | parent (L_j) = L_i}

Query messages travel down the tree from root to leaves, and probes travel back up the tree from leaves to the root. Query messages are sent by Q events. Let Q_ik be the k^th Q event at location i.
For all locations L_j, j < >r, Q_jk is triggered by a query message send by event Q_ik, L_i = parent(L_j). For all L_i in I, Q_ik sends query messages to each location L_j in children(L_i).
For each leaf L_j, Q_jk = P_jk, i.e. the k^th Q event is the k^th probe event. A probe event P_jk,j < > r, sends a probe message to parent (L_j). A probe event at each internal location, L_j, is triggered by the arrival of probe messages from all its children.
The probe event at the root, P_rk, is the same as the k+1^st Q event at the root, P_rk = Q_r(k+1)

Note:
P_jk ->⁺ P_rk, all j < >r
P_r(k-1) = Q_rk ->⁺ Q_jk, all j < > r
P_jk -> P_ik, all j in children (L_i)
It can be seen by induction on the distance from the leaves that
P_r(k-1)->⁺ P_ik, all i
Therefore
P_j(k-1)->⁺ P_ik, all i and j
hence the tree method gives overlapping intervals.

1. If the underlying algorithm terminates, then in the following interval, no busy bits will be set, and since there are no messages in transit, the sum of the charges will be zero.
2. If at the end of one interval all busy bits are false and the sum of the charges is zero, then the charge at each location at the end of the interval is the charge there throughout the entire interval. Since the intervals are overlapping, there is some instant across all the locations at which the sum of the charges at the locations is zero and hence no message is in transit. If there are no messages in transit, the algorithm has terminated.

This proof is at a rather high level. For a more detailed proof, it is advantageous to phrase the proof in terms of linearizations of the computational events.
Let b_i be the busy bit at location L_i. This bit is set (to true) by any action A_ijk. It is reset (to false) by any probe P_ik. Let ^kb_i be the value of b_i as probe event P_ik begins execution.
Let ^kc_i be the value of c_i at event P_ik.

Theorem : The algorithm has terminated iff
(SUM_i^k c_i = 0) AND ¬ (^kb₁ OR^kb₂ OR ... OR^kb_n)

1. Proof that if the algorithm has terminated, then
   (SUM_i^k c_i = 0) AND ¬ (^kb₁ OR^kb₂ OR ... OR^kb_n)
   Linearize the events in the execution giving a sequence E₁, E₂ , ..., E_N. (Recall that if E_i ->⁺ E_j , then i Let
   
   • b_ij be the value of b_i following event E_j. b_i0 is the initial value, true.
   • c_ij be the value of c_i following event E_j. c_i0 is the initial value.
   • M_j be the number of task messages in transit following event E_j.
     

   is invariant.
   

   SUM_iC_ij = M_j
   If the algorithm terminates at action E_x=A_ij(k'), then M_x = M_x+1 = M_x+2 = .... = 0. Also, there is no action E_u where u>x, hence c_gx = c_g(x+1) = c_g(x+2) = .... for all locations L_g

   Pick an event E_w = A_i'v'k", w <= x, for which k" is largest. (It might not be E_{x^{.)
   Following P}ik" ^{(for all i), b}i ^{will remain false since P}ik ^{resets the bit and there are no actions to set it. Therefore k"+1 b}i ^{= false for all i.
   Recall E}x^=Aij(k') ^{is the event (the last action) at which the algorithm terminated, and k'<= k". Let E}z^=Pik"^{. Observe x<z, since the actions of the kth interval occur before the kth probe.
   Since P}ik" ^{->+ P}j(k"+1) ^{for all L}j ^{, and since after termination, M=0}}
   

   ^SUMi^k"+1Ci ^{= 0}

   ^{Therefore, letting k=k"+1, (SUM}i^{k c}i ^{= 0) AND¬ (kb}1 ^ORkb2 ^{OR ... ORkb}n⁾
   

2. ^{Proof that if
   (SUM}i^{k c}i ^{= 0) AND¬ (kb}1 ^ORkb2 ^{OR ... ORkb}n^{)
   for some kth set of overlapping intervals, then the algorithm has terminated.
   Suppose the condition (SUM}i^{k c}i ^{= 0) AND¬ (kb}1 ^ORkb2 ^{OR ... ORkb}n^{)
   is met at the end of interval k.}

   ^{We will show that for any legal linearizations of events E}1^{, E}2^{, ..., E}N^{, the formula will hold only if the algorithm has terminated.
   Choose an arbitrary linearization of the events.
   Let E}x ^=Pi(k-1) ^{such that for all P}j(k-1)^=Ez ^{, z <= x. E_x is the last probe event for any of the k-1st intervals in the linearization.
   By the definition of overlapping intervals, Pi(k-1) ->+ Pjk. In the linearization, this is preserved, hence for all Ey = Pjk, y>x.
   Since no location Li has been busy over interval k, ci has remained constant from Pi(k-1) to Pik. At the instant following event Ex, which is within all of the kth intervals and the}

   ^{SUMiCix=Mx = 0}

   ^{algorithm has terminated.}
   

• ^{<i,i+2> for all 0 <= i <i,i+1> for all even i in the range 0...N-2.}
• ^{<i,i+3> for all odd i in the range 0...N-5.}
• ^{The lengths of the edges are uniformly distributed random integers in the range [0..9].}

^{As shown in [CHRI92b], the X-ladder graph with random edge lengths yields an number of distance messages in the Bellman-Ford algorithm exponential in the number of vertices.
We laid out the vertices so that vertex number i is allocated to processor number (i modulus P) for P processors.
Details of termination detection algorithms. All locations in a process are scheduled round robin. Each time a location is dispatched in the active tree algorithm, it consumes one distance or acknowledgement message, giving higher priority to distance messages; a location will not consume an acknowledgement message if there is a distance message waiting to be processed. The probe tree algorithm superimposes a hypercube upon the locations and builds a spanning tree along edges of the hypercube. The locations are numbered from zero. Location zero is the root. If the binary representation of a location's number has k rightmost zeros, the location has k children in the tree whose numbers are the same as their parent's except for precisely one of k low order zeros being changed to a one (if they exist).
Language. We use the language MDC90 [CHRI92] based on the Message Driven Computing model. A Message Driven Computation system has five characteristics:}

1. ^{Computational events are executions of functions that map sets of input messages into output messages.}
2. ^{Computational events communicate with each other only through asynchronous, unidirectional message passing.}
3. ^{Messages are sent to locations where the messages matching a pattern become inputs to a computational event.}
4. ^{Locations have structured, computable names.}
5. ^{There is mutual exclusion between computational events at the same location.}

^{Experiments. In our experiments, we ran each algorithm 32 times for a given number of vertices to permit the use of large sample statistics. The lengths assigned to the edges were assigned using a random number generator seeded from a different random number generator. No two runs in the same experiment used the same seed. The order of runs was randomized to avoid being influenced by secular trends (e.g. other load on the machine).}

^{Hardware system. The experiments were run on an Encore Multimax computer with 20 processors at a time of low utilization. To implement MDC90's distributed memory model, processes on the Encore simulate the nodes on a multicomputer: an MDC90 location is assigned to a particular process. Messages, however, are allocated in shared memory and passed among the processes through linked queues, not by copying.}

• ^{AGHA86 Agha, G. A.; Actors: A Model of Concurrent Computation in Distributed Systems, MIT Press, Cambridge, MA., 1986.}
• ^{APT84 Apt, K. R., Francez, N., "Modeling the Distributed Termination Convention of CSP," ACM TOPLAS , 6,3, July, 1984.}
• ^{APT86 Apt, K. R., "Correctness Proofs of Distributed Termination Algorithms," ACM TOPLAS, 8,3, July, 1986.}
• ^{CHRI92a Christopher, T. W., and Freitag, G. A. MDC90 Language Description , Version 2.0, Technical Report, Computer Science Department, Illinois Institute of Technology, Chicago IL 60616, 1992.}
• ^{CHRI92b Christopher, T. W. "A Technique for Damping Exponential Behavior in Reactive Object Algorithms With Invalidation," 1992 Int'l. Conf. on Parallel Processing, St. Charles IL, Aug. 1992.}
• ^{DIJK80 Dijkstra, E. W., and Scholten, C. S., "Termination Detection for Diffusing Computations," Information Processing Letters, 11, pp1-4, Aug. 1980.}
• ^{DIJK83 Dijkstra, E. W., Feijen, W.H.J., van Gasteren, A.J.M., "Derivation of a Termination Detection Algorithm for Distributed Computations," Information Processing Letters, 16, pp 217-219, June 1983.}
• ^{FRAN80 Francez, N., "Distributed Termination," ACM TOPLAS, 2,1, Jan. 1980.}
• ^{FRAN82 Francez, N., Rodeh, M., "Achieving Distributed Termination without Freezing," IEEE Trans. on Software Engineering, SE-8,3, May 1982.}
• ^{HERL87 Herlihy, M. P., and Wing, J. M., "Axioms for Concurrent Objects", ACM Principles of Programming Languages Conference, January 1987.}
• ^{TOPO84 Topor, R. W., "Termination Detection for Distributed Computations," Information Processing Letters, 18 pp.33-36, Jan. 20, 1984.}
• ^{ROKU88 Kazuaki Rokusawa, Nobuyuki Ichiyoshi, Takashi Chikayama, Hiroshi Nakashima, "An Efficient Termination Detection and Abortion Algorithm for Distributed Processing Systems," 1988 Int'l. Conf. on Parallel Processing, St. Charles IL, Aug. 1988.}