Efficient Reductions for Wait-Free Termination Detection in Faulty Distributed Systems
Neeraj Mittal, Subbarayan Venkatesan, Felix Freiling, Lúcia Draque Penso · 2005
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 that has been designed for a failure-free environment , into a wait-free that tolerates up to any number of process crashes. The transformations are such that a competitive fault-sensitive termination detection algorithm results in a competitive wait-free termination detection algorithm B.