Jukka Suomela

Survey of local algorithms

ACM Computing Surveys · volume 45, issue 2, article 24, 40 pages, February 2013 · doi:10.1145/2431211.2431223

author’s version publisher’s version

Abstract

A local algorithm is a distributed algorithm that runs 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 non-trivial problems. This work surveys the state-of-the-art in the field, covering impossibility results, deterministic local algorithms, randomised local algorithms, and local algorithms for geometric graphs.

Links

© ACM 2013 — This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Computing Surveys 45 (2013). http://doi.acm.org/10.1145/2431211.2431223

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.