Name
Abstract | ||
|---|---|---|
We address the depth-first token circulation (DFTC) in tree networks. We first consider oriented trees-every processor knows which of its neighbors leads to a particular processor called the root. On such trees, we propose a state optimal DFTC algorithm. Next, we propose a second algorithm, also for trees, but where no processor knows which of its neighbor leads to the root. This algorithm is also optimal in terms of the number of states per processor. Both algorithms works under any daemon, even unfair. Furthermore, both are snap-stabilizing. A snap-stabilizing protocol guarantees that the system always maintains the desirable behavior. In other words, a snap-stabilizing algorithm is also a self-stabilizing algorithm which stabilizes in 0 steps. Thus, both algorithms are also optimal in terms of the stabilization time. Finally, two approaches of the maximum waiting time to initiate a DFTC are also discussed, whether the tree is oriented or not. In every case but one, we show that the waiting time is asymptotically optimal. In the last case, we conjecture the same result. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.jpdc.2006.08.008 | J. Parallel Distrib. Comput. |
Keywords | Field | DocType |
tree network,self-stabilizing algorithm,last case,asymptotically optimal,trees-every processor,algorithms work,particular processor,distributed mutual exclusion,snap-stabilization,depth-first token circulation,self-stabilization,token passing,snap-stabilizing algorithm,snap-stabilizing protocol guarantee,stabilization time,optimality,self stabilization | Token passing,Computer science,Depth-first search,Algorithm,Self-stabilization,Fault tolerance,Autonomous system (mathematics),Mutual exclusion,Asymptotically optimal algorithm,Daemon,Distributed computing | Journal |
Volume | Issue | ISSN |
67 | 1 | Journal of Parallel and Distributed Computing |
Citations | PageRank | References |
7 | 0.43 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Franck Petit | 1 | 736 | 60.02 |
| Vincent Villain | 2 | 544 | 45.77 |