Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
A Self-stabilizing Algorithm for Finding a Spanning Tree in a Polynomial Number of Moves
verfasst von : Adrian Kosowski, Łukasz Kuszner
Erschienen in: Parallel Processing and Applied Mathematics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the self-stabilizing model each node has only local information about the system. Regardless of the initial state, the system must achieve a desirable global state. We discuss the construction of a solution to the spanning tree problem in this model. To our knowledge we give the first self-stabilizing algorithm working in a polynomial number of moves, without any fairness assumptions. Additionally we show that this approach can be applied under a distributed daemon. We briefly discuss implementation aspects of the proposed algorithm and its application in broadcast routing and in distributed computing.