Survey of local algorithms

Tutkimustuotos: ArtikkelijulkaisuKatsausartikkeliTieteellinenvertaisarvioitu

Abstrakti

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.
Alkuperäiskielienglanti
LehtiACM Computing Surveys
Vuosikerta45
Numero2
SivutArticle No. 24
Sivumäärä40
ISSN0360-0300
DOI - pysyväislinkit
TilaJulkaistu - 2013
OKM-julkaisutyyppiA2 Katsausartikkeli tieteellisessä aikakauslehdessä

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä