grr12
Summary
Hendrickx, J.M. (2014) Views in a Graph: To Which Depth Must Equality Be Checked? Parallel and Distributed Systems, IEEE Transactions on, 25(7):1907-1912.
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.
Bibtex entry
@ARTICLE { grr12,
AUTHOR = { Hendrickx, J.M. },
JOURNAL = { Parallel and Distributed Systems, IEEE Transactions on },
TITLE = { Views in a Graph: To Which Depth Must Equality Be Checked? },
YEAR = { 2014 },
MONTH = { July },
VOLUME = { 25 },
NUMBER = { 7 },
PAGES = { 1907-1912 },
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. },
DOI = { 10.1109/TPDS.2013.232 },
ISSN = { 1045-9219 },
}