Carleton University
Technical Report TR-95-10
April 1995
Sense of Direction: Definitions, Properties, and Classes
Abstract
An extensive body of evidence exists of the impact that speci c edge labelings have on the communication complexity of distributed problems. It has been long suspected that these very di erent labelings share a common property, named a long time ago Sense of Direction. In spite of the large amount of investigations, and of the obvious practical importance, a formal characterization of this property did not exist.In this paper, we nally provide a formal de nition of Sense of Direction. We show that in Sense of Direction there is a very speci c link between three factors: the labeling, the topological structure, and the local view that an entity has of the system. In a way, Sense of Direction is the capacity of a node in the system to use the labeling to translate the local view of its neighbors into its own. Using the formal de nition as an observational platform, we describe several properties which allow the translation process to be possible beyond the immediate neighborhood. Finally, we identify four general classes of labelings and analyzed their properties; these classes include all the labelings used in the literature.