Views in a Graph: To Which Depth Must Equality Be Checked?

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.