Proof labeling schemes

DOI10.1007/s00446-010-0095-3zbMath1267.68061OpenAlexW2056295140MaRDI QIDQ2377139

David Peleg, Shay Kutten, Amos Korman

Publication date: 28 June 2013

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-010-0095-3

zbMATH Keywords

distributed networksself stabilizationproof labelsproperty verification

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (45)

On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency ⋮ A silent self-stabilizing algorithm for the generalized minimal \(k\)-dominating set problem ⋮ Planarity can be verified by an approximate proof labeling scheme in constant-time ⋮ The ANTS problem ⋮ Finding the size and the diameter of a radio network using short labels ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ What can be verified locally? ⋮ Proof-labeling schemes: broadcast, unicast and in between ⋮ Distributed Testing of Distance-k Colorings ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width ⋮ Fast rendezvous with advice ⋮ Lower bound for constant-size local certification ⋮ Drawing maps with advice ⋮ Unnamed Item ⋮ Locality and checkability in wait-free computing ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ A hierarchy of local decision ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Deciding and verifying network properties locally with few output bits ⋮ On mobile agent verifiable problems ⋮ Impact of knowledge on election time in anonymous networks ⋮ Randomized proof-labeling schemes ⋮ Randomized distributed decision ⋮ A meta-theorem for distributed certification ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ Fast distributed algorithms for testing graph properties ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ Approximate proof-labeling schemes ⋮ Compact distributed certification of planar graphs ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Locality and Checkability in Wait-Free Computing ⋮ Optimized silent self-stabilizing scheme for tree-based constructions ⋮ Local certification of graphs on surfaces ⋮ Local mending ⋮ Proof labeling schemes for reachability-related problems in directed graphs ⋮ A meta-theorem for distributed certification ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ Local certification of graphs with bounded genus ⋮ Introduction to local certification ⋮ Topology recognition with advice

Cites Work

• Unnamed Item
• Local MST computation with short advice
• Local stabilizer
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• The local detection paradigm and its applications to self-stabilization
• Memory requirements for silent stabilization
• Informative labeling schemes for graphs
• Crash failures can drive protocols to arbitrary states
• Labelling and Implicit Routing in Networks
• Lower bounds on communication complexity in distributed computer networks
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• Implicat Representation of Graphs
• Self-stabilizing systems in spite of distributed control
• A randomized linear-time algorithm to find minimum spanning trees
• Distributed Computing: A Locality-Sensitive Approach
• Labeling Schemes for Flow and Connectivity
• A trade-off between space and efficiency for routing tables
• Distance labeling in graphs
• Communication Complexity
• Proximity-preserving labeling schemes
• Proof labeling schemes
• Distributed verification of minimum spanning trees
• Oracle size
• What can be computed locally?
• Time optimal self-stabilizing synchronization
• The fault span of crash failures
• Labeling Schemes for Vertex Connectivity
• Distributed Weighted Matching
• Distributed Computing – IWDC 2005
• What cannot be computed locally!
• Automata, Languages and Programming
• Tree Exploration with an Oracle

This page was built for publication: Proof labeling schemes