Survey of distributed decision

MaRDI QIDQ4967211zbMATH OpenFDO

Authors Laurent Feuilloley, Pierre Fraigniaud

Publication date 3 July 2019

Full work available at URL https://arxiv.org/abs/1606.04434, http://bulletin.eatcs.org/index.php/beatcs/article/view/411/391

Mathematics Subject Classification ID

Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Deciding and verifying network properties locally with few output bits
• What Can be Computed Locally?
• Introduction to local certification
• scientific article; zbMATH DE number 1559574
• Towards a complexity theory for local distributed computing

Cited in

(24)

• Distributed decision making----a unified approach.
• What can be verified locally?
• On mobile agent verifiable problems
• Deciding and verifying network properties locally with few output bits
• Redundancy in distributed proofs
• Compact distributed certification of planar graphs
• Proof labeling schemes for reachability-related problems in directed graphs
• A hierarchy of local decision
• Minimizing the number of opinions for fault-tolerant distributed decision using well-quasi orderings
• Distributed Decision-Making Over Adaptive Networks
• A time hierarchy theorem for the LOCAL model
• On the Value of Coordination in Distributed Decision Making
• Introduction to local certification
• Redundancy in distributed proofs
• Local verification of global proofs
• Distributed Testing of Distance-k Colorings
• Full and Local Information in Distributed Decision Making
• Graph classes and forbidden patterns on three vertices
• Approximate proof-labeling schemes
• Twenty-two new approximate proof labeling schemes
• Distributed maximum matching verification in CONGEST
• Distributed model checking on graphs of bounded treedepth
• Tight bounds on the message complexity of distributed tree verification
• A LOCAL view of the polynomial hierarchy

This page was built for publication: Survey of distributed decision

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4967211)