Title: About the local detection of termination of local computations in graphs

Authors: Yves M{\'e}tivier (1), Anca Muscholl (2) , Pierre-Andr{\'e} Wacrenier (1)

Affiliations:
(1) LaBRI, Universit{\'e} Bordeaux I, ENSERB,
    351 cours de la Lib{\'e}ration,
    33405 Talence, France
(2) Institut f{\"u}r Informatik, Universit{\"a}t Stuttgart,
    Breitwiesenstr.~20-22, 70565 Stuttgart, Germany 

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.