Sense of direction

Definitions, properties, and classes

Paola Flocchini*, Bernard Mans, Nicola Santoro

*Corresponding author for this work

Research output: Contribution to journalArticle

44 Citations (Scopus)

Abstract

An extensive body of evidence exists of the impact that specific edge labelings have on the communication complexity of distributed problems. It has been long suspected that these very different labelings share a common property, named sense of direction. In spite of the large number of investigations, and of the obvious practical importance, a formal characterization of this property did not exist. In this paper, we finally provide a formal definition of sense of direction, making explicit the very specific relationship 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 capability of a node in the system to use the labeling to translate the local view of its neighbors into its own. Using the formal definition 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 analyze their properties; these classes include all the labelings used in the literature.

Original languageEnglish
Pages (from-to)165-180
Number of pages16
JournalNetworks
Volume32
Issue number3
Publication statusPublished - Oct 1998

Fingerprint Dive into the research topics of 'Sense of direction: Definitions, properties, and classes'. Together they form a unique fingerprint.

  • Cite this

    Flocchini, P., Mans, B., & Santoro, N. (1998). Sense of direction: Definitions, properties, and classes. Networks, 32(3), 165-180.