TR-96-13: Computing on Anonymous Networks with Sense of Direction

Sense of direction refers to a set of global consistency constraints of the lo- cal labeling of the edges of a network. Sense of direction has a large impact on the communication complexity of many distributed problems. In this paper, we study the impact that sense of direction has on computability and we focus on anonymous networks. We establish several results. In particular, we prove that with weak sense of direction, the intuitive knowledge-computability hierarchy be- tween levels of a priori structural knowledge collapses. A powerful implication is the formal proof that shortest path routing is possible in anonymous networks with sense of direction. We prove that weak sense of direction is computationally stronger than topological awareness. We also consider several fundamental prob- lems; for each, we provide a complete characterization of the anonymous networks on which it is computable with sense of direction.