Paper Info
Title
A new polynomial silent stabilizing spanning-tree construction algorithm
Abstract
Stabilizing algorithms can automatically recover their specifications from an arbitrary configuration in finite time. They are therefore well-suited for dynamic and failure prone environments. A silent algorithm always reaches a terminal configuration in a finite time. The spanning-tree construction is a fundamental task in distributed systems which forms the basis for many other network algorithms (like Token Circulation, Routing or Propagation of Information with Feedback). In this paper we present a silent stabilizing algorithm working in n2 steps (where n is the number of processors in the network) with a distributed daemon, without any fairness assumptions. This complexity is totally independent of the initial values present in the network. So, this improves all the previous results of the literature.
Year
DOI
Venue
2009
10.1007/978-3-642-11476-2_12
SIROCCO
Keywords
Field
DocType
spanning-tree construction algorithm,terminal configuration,token circulation,network algorithm,silent algorithm,fundamental task,initial value,fairness assumption,arbitrary configuration,failure prone environment,finite time,distributed systems,spanning tree,fault tolerance,distributed system
Distributed minimum spanning tree,Polynomial,Network algorithms,Computer science,Algorithm,Distributed algorithm,Fault tolerance,Spanning tree,Daemon,Finite time
Conference
Volume
ISSN
ISBN
5869
0302-9743
3-642-11475-X
Citations 
PageRank 
References 
7
0.47
17
Authors
1
Name
Order
Citations
PageRank
Alain Cournier128122.07