Infinite networks, halting and local algorithms (Draft)

Antti KuusistoTampere 2013 · OpenAlex

Abstract

The immediate past has witnessed an increasing amount of interest in local algorithms, i.e., constant time distributed graph algorithms. In the recent survey of local algorithms (Suomela, ACM Computing Surveys, 2013), it is argued that local algorithms provide a framework that could be used in order to (theoretically) control infinitely large networks in finite time. We investigate
\nhalting of distributed algorithms from a theoretical point of view. We establish
\nfor a comprehensive collection of models of distributed computing that if
\ninfinite networks are included in the class of structures investigated, then
\nevery halting distributed algorithm is in fact a local algorithm. The models
\nstudied include various weak models of distributed computing in anonymous
\nnetworks investigated by Hella and co-authors in (Hella et al., PODC 2012).
BibTeX
@inproceedings{kuusisto2013infinite,
  author = {Antti Kuusisto},
  title = {{Infinite networks, halting and local algorithms (Draft)}},
  booktitle = {Tampere},
  year = {2013},
}

Loading related content...

Figure