Survey of Distributed Decision

Abstract

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