Efficient Reductions for Wait-Free Termination Detection in Faulty
Distributed Systems

Neeraj Mittal, Felix Freiling, S. Venkatesan, Lucia Draque Penso

We investigate the problem of detecting termination of a distributed
computation in asynchronous systems where processes can fail by crashing.
More specifically, for both fully and arbitrarily connected communication
topologies, we describe efficient ways to transform any fault-sensitive
termination detection algorithm A, that has been designed for a
failure-free environment, into a wait-free termination detection
algorithm B, that tolerates up to any number of process crashes. The
transformations are such that a competitive fault-sensitive termination
detection algorithm A results in a competitive wait-free termination
detection algorithm B.  Furthermore, they work whether the termination
detection is effective (allowing messages in-transit from crashed
processes towards a live one able to ignore them) or strict (not allowing
messages in-transit towards a live process). Finally, though we focus
on crash failures, we also discuss how to tolerate message omissions,
and how they impact on the performance.

Let m(n,c,M) and d(n,c,M) denote message complexity and detection
latency of A when the system has n processes and c bidirectional reliable
channels, and when the distributed computation exchanges M application
messages. For fully connected communication topologies, the message
complexity and the detection latency of B are at most O(n + m(n,c,0))
messages per fault more and O(d(n,c,0)) time units per fault more than
those of A, while for arbitrary ones, they are at most O(nlog n + c +
m(n,c,0)) messages per fault more and O(n + d(n,c,0)) time units per
fault more than those of A. Moreover, for both cases, the overhead (that
is, the amount of control data piggybacked) increases by only O(log n)
bits per fault on an application message and at most O(log n) bits per
fault plus O(log M) on a control message.

We also prove that in a crash-prone distributed system, irrespective
of the number of faulty processes, the perfect failure detector is the
weakest failure detector for solving the effective-termination detection
problem, whereas a failure detection sequencer is both necessary and
sufficient for solving the strict-termination detection problem. This
guarantees that our transformation method, which requires a perfect
failure detector, does not demand stronger than necessary assumptions.