About the Local Detection of Termination of Local Computations in Graphs

Abstract

In this paper we give a formalization of the problem of locally detecting the global termination of distributed algorithms on graphs. We introduce the notion of quasi k-coverings. Using (quasi) k-coverings, we present methods for showing that it is not possible to detect locally the global termination of local computations in certain families of graphs. These methods also allow to show that some knowledge, e.g. the size of the graph, is necessary in order to solve certain problems in a distributed way.