In a distributed system, each entity has a label
(port number) associated to each of its
neighbours. It is well known that if the
labeling satisfies a global consistency property
called Sense of Direction, the communication
complexity of many distributed problem can be
greatly reduced. This property is assumed to be present
and implicitly used in most interconnection networks.
In this paper we investigate the nature of the
relationship between Sense of
Direction and network topology.
We first consider the class of labelings which only satisfy
the requirement of local orientation; that is,
at each node, the edges incident on it have distinct labels.
We then consider the class of labelings which also
satisfy edge symmetry; that is,
there exists a
correlation between the labels neighbours give to their
connecting edge. This class includes most of used
labelings.
We completely characterize the interplay
between topological constraints and
consistency constraints for these
two classes of labelings.
In fact, for each class,
we identify both
the set of forbidden subgraphs
and the set of feasible graphs, and
we show that the characterization is complete.