Paper Info
Title
A snap-stabilizing DFS with a lower space requirement
Abstract
A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In [4], we presented the first snap-stabilizing depth-first search (DFS) wave protocol for arbitrary rooted networks working under an unfair daemon. However, this protocol needs O(NN) states per processors (where N is the number of processors) and needs ids on processors. In this paper, we propose an original snap-stabilizing solution for this problem with a strongly enhanced space complexity, i.e., O(Δ2 × N) states where Δ is the degree of the network. Furthermore, this new protocol does not need a completely identified network: only the root needs to be identified, i.e., the network is semi-anonymous.
Year
DOI
Venue
2005
10.1007/11577327_3
Self-Stabilizing Systems
Keywords
Field
DocType
lower space requirement,enhanced space complexity,new protocol,arbitrary rooted network,arbitrary initial configuration,original snap-stabilizing solution,snap-stabilizing depth-first search,snap-stabilizing dfs,unfair daemon,wave protocol,snap-stabilizing protocol,fault tolerant,depth first search,space complexity,distributed system
Distributed File System,Computer science,Fault tolerance,Autonomous system (mathematics),Transmission protocol,Anonymity,Daemon,Distributed computing,Communications protocol
Conference
Volume
ISSN
ISBN
3764
0302-9743
3-540-29814-2
Citations 
PageRank 
References 
8
0.48
10
Authors
3
Name
Order
Citations
PageRank
Alain Cournier128122.07
Stéphane Devismes219225.74
Vincent Villain354445.77