Survey of Distributed Decision

Laurent Feuilloley et Pierre Fraigniaud

Bulletin of the EATCS
No 119, June 2016, p.41-65

We survey the recent distributed computing literature on checking whether a given distributed system configuration satisfies a given boolean predicate, i.e., whether the configuration is legal or illegal w.r.t. that predicate. We consider classical distributed computing environments, including mostly synchronous fault-free network computing (LOCAL and CONGEST models), but also asynchronous crash-prone shared-memory computing (WAIT-FREE model), and mobile computing (FSYNC model).

We have updated the paper on the Arxiv on September 21 2017. Many thanks to the authors who pointed out possible improvements.