On the impact of sense of direction on message complexity

Paola Flocchini, Bernard Mans*, Nicola Santoro

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)

Abstract

In this paper, we prove a general result on the impact of sense of direction. We show that, in arbitrary graphs, any sense of direction has a dramatic effect on the communication complexity of several important distributed problems: Broadcast, Depth First Traversal, Election, and Spanning Tree Construction. In systems with n nodes and e communication links, the solution for the Depth First Traversal and the Broadcast problems require Ω(e) messages with arbitrary labelings; we show that, with any sense of direction, they can be solved exchanging only Θ(n) messages, even if the system is anonymous. The problems of Election and of Spanning Tree Construction require Ω(e + n log n) messages with arbitrary labelings; on the other hand, we show that they can be solved with Θ(n) messages with any sense of direction. The results presented here completely explain and generalize the existing results which now follow as corollaries for specific labelings.

Original languageEnglish
Pages (from-to)23-31
Number of pages9
JournalInformation Processing Letters
Volume63
Issue number1
Publication statusPublished - 14 Jul 1997

Keywords

  • Complexity
  • Distributed algorithms
  • Graph algorithms

Fingerprint Dive into the research topics of 'On the impact of sense of direction on message complexity'. Together they form a unique fingerprint.

Cite this