Fast and compact self-stabilizing verification, computation, and fault detection of an MST

DOI10.1007/s00446-015-0242-yzbMath1337.68040arXiv1512.07800OpenAlexW3103786737MaRDI QIDQ498670

Shay Kutten, Toshimitsu Masuzawa, Amos Korman

Publication date: 29 September 2015

Published in: Distributed Computing, Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.07800

zbMATH Keywords

fault detectionlocalityminimum spanning treedistributed algorithmsself-stabilizationdistributed verificationself stabilizationdistributed network algorithmsdistributed property verificationfast fault detectionlocal fault detectionproof labels\textsc{MST}local proof checking

Mathematics Subject Classification ID

Related Items (10)

Proof-labeling schemes: broadcast, unicast and in between ⋮ Compact routing messages in self-healing trees ⋮ Locality and checkability in wait-free computing ⋮ A hierarchy of local decision ⋮ Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative ⋮ Randomized proof-labeling schemes ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ Approximate proof-labeling schemes ⋮ Introduction to local certification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compact separator decompositions in dynamic trees and applications to labeling schemes
• Tight bounds for distributed minimum-weight spanning tree verification
• Gradient clock synchronization in dynamic networks
• Self-stabilizing leader election in optimal space under an arbitrary scheduler
• Consensus algorithms with one-bit messages
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Broadcasting in dynamic radio networks
• A new distributed depth-first-search algorithm
• Electing a leader in a ring with link failures
• Programming simultaneous actions using common knowledge
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Self-stabilizing extensions for message-passing systems
• Self-stabilizing depth-first search
• The local detection paradigm and its applications to self-stabilization
• Self-stabilizing multicast protocols for ad hoc networks.
• Memory requirements for silent stabilization
• Snap-stabilization and PIF in tree networks
• Distributed verification of minimum spanning trees
• Continuous consensus via common knowledge
• Randomized distributed decision
• Optimal parallel verification of minimum spanning trees in logarithmic time
• Proof labeling schemes
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• Distributed computation in dynamic networks
• Flooding time in edge-Markovian dynamic graphs
• Fault-containing self-stabilizing algorithms
• Locally checkable proofs
• Applications of Path Compression on Balanced Trees
• Distributed network protocols
• Knowledge and common knowledge in a distributed environment
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony
• Fast Self-stabilizing Minimum Spanning Tree Construction
• A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property
• Fault Tolerance in Networks of Bounded Degree
• Reaching Agreement in the Presence of Faults
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• Perfectly secure message transmission
• Self-stabilizing systems in spite of distributed control
• Distributed reset
• Distributed Computing: A Locality-Sensitive Approach
• Labeling Schemes for Flow and Connectivity
• Distance labeling in graphs
• Distributed Verification and Hardness of Distributed Approximation
• Parsimonious flooding in dynamic graphs
• Optimal gradient clock synchronization in dynamic networks
• What can be computed locally?
• Time optimal self-stabilizing synchronization
• Fast distributed construction of k-dominating sets and applications
• The fault span of crash failures
• Almost-Everywhere Secure Computation
• Local Distributed Decision
• On the Impact of Identifiers on Local Decision
• When graph theory helps self-stabilization
• Distributed error confinement
• Distributed MST for constant diameter graphs

This page was built for publication: Fast and compact self-stabilizing verification, computation, and fault detection of an MST