Sense of direction refers to a set of global consistency constraints
of the local 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 between 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 problems; for each, we
provide a complete characterization of the anonymous
networks on which it is computable with sense of direction.