Survey of local algorithms

Research output: Contribution to journalReview ArticleScientificpeer-review

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.
Original languageEnglish
JournalACM Computing Surveys
Volume45
Issue number2
Pages (from-to)Article No. 24
Number of pages40
ISSN0360-0300
DOIs
Publication statusPublished - 2013
MoE publication typeA2 Review article in a scientific journal

Fields of Science

  • 113 Computer and information sciences

Cite this

Suomela, Jukka. / Survey of local algorithms. In: ACM Computing Surveys. 2013 ; Vol. 45, No. 2. pp. Article No. 24 .
@article{2857910342ed45419b3e167a031e396c,
title = "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.",
keywords = "113 Computer and information sciences",
author = "Jukka Suomela",
year = "2013",
doi = "10.1145/2431211.2431223",
language = "English",
volume = "45",
pages = "Article No. 24",
journal = "ACM Computing Surveys",
issn = "0360-0300",
publisher = "Association for Computing Machinery",
number = "2",

}

Survey of local algorithms. / Suomela, Jukka.

In: ACM Computing Surveys, Vol. 45, No. 2, 2013, p. Article No. 24 .

Research output: Contribution to journalReview ArticleScientificpeer-review

TY - JOUR

T1 - Survey of local algorithms

AU - Suomela, Jukka

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - 113 Computer and information sciences

U2 - 10.1145/2431211.2431223

DO - 10.1145/2431211.2431223

M3 - Review Article

VL - 45

SP - Article No. 24

JO - ACM Computing Surveys

JF - ACM Computing Surveys

SN - 0360-0300

IS - 2

ER -