Fast Self-Stabilizing Minimum Spanning Tree Construction

2010/06/16 by Lélia Blin, Blin, Lélia, Shlomi Dolev +5
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS #cs.NI

paper · pdf · doi:10.48550/arxiv.1006.3141

arxiv created 2010/07/21 · arxiv updated 2010/07/26

Abstract

We present a novel self-stabilizing algorithm for minimum spanning tree (MST) construction. The space complexity of our solution is O(log²n) bits and it converges in O(n²) rounds. Thus, this algorithm improves the convergence time of all previously known self-stabilizing asynchronous MST algorithms by a multiplicative factor Θ(n), to the price of increasing the best known space complexity by a factor O(log n). The main ingredient used in our algorithm is the design, for the first time in self-stabilizing settings, of a labeling scheme for computing the nearest common ancestor with only O(log²n) bits.

Related

• Fast Self-Stabilizing Minimum Spanning Tree Construction Using Compact Nearest Common Ancestor Labeling Scheme
• A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property
• Polynomial-Time Space-Optimal Silent Self-Stabilizing Minimum-Degree Spanning Tree Construction
• A Uniform Self-Stabilizing Minimum Diameter Spanning Tree Algorithm
• Analysis of a Memory-Efficient Self-Stabilizing BFS Spanning Tree