On the impact of sense of direction in arbitrary networks

Bernard Mans*, Nicola Santoro

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

11 Citations (Scopus)

Abstract

In this paper, we study the positive impact that the availability of 'Sense of Direction' has on the message complexity of the Election problem in arbitrary networks of processors. We present a θ(n log n) solution; without sense of direction, this problem requires Ω(e + n log n) messages where e is the number of communication links. This result confirms and extends the evidence on the impact of sense of direction which, up to new, was established only for specific classes of topologies.

Original languageEnglish
Title of host publicationProceedings of the 14th International Conference on Distributed Computing Systems, 1994
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages258-265
Number of pages8
ISBN (Print)0818658401
DOIs
Publication statusPublished - 1994
Externally publishedYes
EventProceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems - Poznan, Pol
Duration: 21 Jun 199424 Jun 1994

Other

OtherProceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems
CityPoznan, Pol
Period21/06/9424/06/94

Fingerprint

Dive into the research topics of 'On the impact of sense of direction in arbitrary networks'. Together they form a unique fingerprint.

Cite this