A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property

Details A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property

2009-05-14

arxiv.org/abs/0905.2287v1

Computer Science

Data Structures and Algorithms

Scientific paper

The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a uni?ed manner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol. We present a new self-stabilizing MST protocol that improves on previous known ap- proaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Second, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most e?cient to date.

Affiliated with

Also associated with

No associations

Rating

A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-400029