1986 | OriginalPaper | Chapter
Symmetric Distributed Termination
Authors : Sven Skyum, Ole Eriksen
Published in: The Book of L
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we present a simple algorithm for deciding when to terminate a distributed computation. Former solutions to the termination problem, e.g. [2, 5], are restricted to rings and undirected connected networks, resp., and they rely on the existence of a special master processor present in the network. The class of configurations for which our algorithm is applicable is the most general possible, namely the class of configurations, where the underlying (directed) networks are strongly connected. If the network is not strongly connected then there exists a group of processors which cannot send messages to the rest and it becomes impossible to detect when to terminate. Furthermore, the algorithm does not require a special master processor acting differently from the others. The only information needed is an upper bound on the diameter of the network (the number of processors, for example). The protocol for all processors is in other words identical.