Survey of local algorithms

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