As we know the run time of most algorithms increases when the input set increases in size. There is one noticeable exception: there is a class of distributed algorithms, dubbed local algorithms, that run in constant time, independently of the size of the network. Being highly scalable and fault tolerant, such algorithms are ideal in the operation of large-scale distributed systems. Furthermore, even though the model of local algorithms is very limited, in recent years we have seen many positive results for nontrivial problems. In this weekend’s paper Jukka Suomela surveys the state-of-the-art in the field, covering impossibility results, deterministic local algorithms, randomized local algorithms, and local algorithms for geometric graphs.

Survey of Local Algorithms, Jukka Suomela, in ACM Computing Surveys (CSUR) Surveys, Volume 45 Issue 2, February 2013, Article No. 24