The detection of termination for a sequential program is trivial. The process knows its own state and it may terminate when its task is complete. The detection of termination is also easy for concurrent processes executing on one machine and sharing memory. The information required to allow the processes to decide if they can terminate can be stored at some shared memory location. However, when several sequential processes must work together in a distributed system, shared memory is non-existent and other methods of detection must be found. The problem arises because a process is aware only of its own local state and is not aware of the states of other processes at that same instant in time. The problem of designing control communication to detect termination, and superimposing it on an application, is called the "distributed termination problem".
In this talk I will discuss some of the issues related to the detection of termination in a distributed system. Several algorithms will be used as illustrations for centralized distributed systems and fully distributed systems. These algorithms will be analyzed for effectiveness and efficiency.
I will also present my own algorithm for the asynchronous distributed case with first-in-first-out message ordering. It allows any process to initiate detection of termination and makes use of multiple tokens.
Colloquia Series page.