A Distributed Termination Detection Algorithm for Dynamic Asynchronous Systems

摘要

Termination detection in distributed systems has been a popular problem of study. It involves determining whether a computation running on multiple nodes has ceased all its activities. A large number of termination detection algorithms have been proposed for static distributed systems in which the number of nodes present in the system is fixed and never changes during runtime. Recently, the termination detection problem has been investigated in the context of dynamic distributed systems in which individual nodes may join and/or leave the system at any time. In this paper, we propose an efficient algorithm for detecting termination of a computation in a dynamic, asynchronous, distributed system that allows nodes to join as well as leave the system while the computation is in progress. Our simulation results indicate that our algorithm has lower message complexity as well as lower detection latency than other comparable algorithms for solving the same problem.