In this paper, we prove a general result on the impact of Sense of Direction.
We show that, in arbitrary graphs,
any Sense of Direction has a dramatic effect on the
communication complexity of several important distributed problems:
Broadcast, Depth-First Traversal, Election,
and Spanning Tree Construction.
In systems with n nodes and e communication links,
the solution for the
the Depth First Traversal and the Broadcast problems
require O(e) messages without labeling; we show that,
with any Sense of Direction, they can be solved
exchanging only Theta(n) messages, even if the system is anonymous.
The problems of Election and of Spanning-Tree Construction
require O(e + n log n) messages in absence of labeling;
on the other hand, with Sense of Direction we show that they can be solved with
Theta(n log n) messages
The results presented here completely explain and generalize the
existing results which now follow as
corollaries for specific labelings.