Survey of Distributed Decision

2016/06/14 by Laurent Feuilloley, Feuilloley, Laurent, Pierre Fraigniaud +1 · 1 citation
Computer Science · #Advanced Data Storage Technologies #Distributed #Distributed and Parallel Computing Systems #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1606.04434

openalex publication_date 2016/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• Complexity landscape for local certification

Related

• Notes on Theory of Distributed Systems
• Decision Problems in a Logic for Reasoning about Reconfigurable Distributed Systems
• A Compendium on Distributed Systems
• A hierarchy of local decision
• Verification of Sometimes Termination of Lazy-Bounded Declarative Distributed Systems