The local detection paradigm and its applications to self-stabilization

DOI10.1016/S0304-3975(96)00286-1zbMath0893.68073WikidataQ56387684 ScholiaQ56387684MaRDI QIDQ1389769

Shay Kutten, Yehuda Afek, Mordechai M. Yung

Publication date: 30 June 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

local detectionself-stabilizing distributed algorithms

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (22)

Proof labeling schemes ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Distributed Testing of Distance-k Colorings ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives ⋮ Distributed verification of minimum spanning trees ⋮ A hierarchy of local decision ⋮ Universal dynamic synchronous self-stabilization ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Deciding and verifying network properties locally with few output bits ⋮ Randomized proof-labeling schemes ⋮ A self-stabilizing transformer for population protocols with covering ⋮ A meta-theorem for distributed certification ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ Self-stabilizing leader election in dynamic networks ⋮ Compact distributed certification of planar graphs ⋮ Local certification of graphs on surfaces ⋮ Stabilizing time-adaptive protocols ⋮ A meta-theorem for distributed certification ⋮ Local certification of graphs with bounded genus ⋮ Introduction to local certification

Cites Work

• Unnamed Item
• Unnamed Item
• The instability of self-stabilization
• Self-stabilization (in spite of distributed control) in tree-structured systems
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Self-stabilization over unreliable communication media
• Elections in anonymous networks
• Calling names on nameless networks
• Distributed network protocols
• Complexity of network synchronization
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Self-stabilizing systems in spite of distributed control
• What can be computed locally?
• Time optimal self-stabilizing synchronization
• The slide mechanism with applications in dynamic networks
• Memory-efficient and self-stabilizing network RESET (extended abstract)
• Token systems that self-stabilize

This page was built for publication: The local detection paradigm and its applications to self-stabilization