Name
Abstract | ||
|---|---|---|
The view of depth $k$ of a node is a tree containing all the walks of length $k$ leaving that node. Views contain all the information that nodes could obtain by exchanging messages with their neighbors. In particular, a value can be computed by a node on a network using a distributed deterministic algorithm if and only if that value only depends on the node's view of the network. Norris has proved that if two nodes have the same view of depth $n - 1$, they have the same views for all depths. Taking the diameter $d$ into account, we prove a new bound in $O(d + d \\log (n/d))$ instead of $n - 1$ for bidirectional graphs with port numbering, which are natural models in distributed computation. This automatically improves various results relying on Norris's bound. We also provide a bound that is stronger for certain colored graphs and extend our results to graphs containing directed edges. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/TPDS.2013.232 | Parallel and Distributed Systems, IEEE Transactions |
Keywords | Field | DocType |
deterministic algorithms,directed graphs,distributed algorithms,trees (mathematics),Norris bound,bidirectional graphs,colored graphs,directed graph edges,distributed deterministic algorithm,natural models,node view of depth,port numbering,tree,Distributed algorithms,computer networks,graph theory,message passing,network topology | Graph theory,Numbering,Computer science,Directed graph,Network topology,Distributed algorithm,Deterministic algorithm,Message passing,Distributed computing,Computation | Journal |
Volume | Issue | ISSN |
25 | 7 | 1045-9219 |
Citations | PageRank | References |
8 | 0.47 | 11 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julien M. Hendrickx | 1 | 772 | 77.11 |