Symmetric Distributed Termination
DOI:
https://doi.org/10.7146/dpb.v14i189.7462Resumé
In this paper we present a simple algorithm for deciding when to terminate a distributed computation. Former solutions to the termination problem are restricted to rings and undirected connected networks, 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.Downloads
Publiceret
1985-01-01
Citation/Eksport
Eriksen, O., & Skyum, S. (1985). Symmetric Distributed Termination. DAIMI Report Series, 14(189). https://doi.org/10.7146/dpb.v14i189.7462
Nummer
Sektion
Articles
Licens
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.