Benefit and Cost of Sense of Direction in Distributed Computations

A sense of direction in a processor network is a labelling of the links with `directions' (such as East, West, North, South) that provides the processors with a uniform orientation. Such a labelling is commonly assumed when designing algorithms for hypercubes, tori and chordal ring networks. In the talk, we shall explore to what degree a sense of direction can be exploited to reduce the amount of communication that must take place in the network. We include algorithms for constructing sense of direction and some recent, very efficient algorithms (for leader election) for cliques and hypercubes without sense of direction.