Survey of local algorithms | Zendy

Jukka Suomela | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Survey of local algorithms

Author(s) -

Jukka Suomela

Publication year - 2013

Publication title -

acm computing surveys

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 2.079

H-Index - 163

eISSN - 1557-7341

pISSN - 0360-0300

DOI - 10.1145/2431211.2431223

Subject(s) - computer science , impossibility , algorithm , scalability , distributed algorithm , randomized algorithm , local search (optimization) , constant (computer programming) , theoretical computer science , distributed computing , database , political science , law , programming language

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 nontrivial problems. This work surveys the state-of-the-art in the field, covering impossibility results, deterministic local algorithms, randomized local algorithms, and local algorithms for geometric graphs.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research