On the impact of sense of direction in arbitrary networks

Bernard Mans; Nicola Santoro

doi:10.1109/ICDCS.1994.302421

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 proceeding › Conference proceeding contribution

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 language	English
Title of host publication	Proceedings of the 14th International Conference on Distributed Computing Systems, 1994
Place of Publication	Piscataway, NJ
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	258-265
Number of pages	8
ISBN (Print)	0818658401
DOIs	https://doi.org/10.1109/ICDCS.1994.302421
Publication status	Published - 1994
Externally published	Yes
Event	Proceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems - Poznan, Pol Duration: 21 Jun 1994 → 24 Jun 1994

Other

Other	Proceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems
City	Poznan, Pol
Period	21/06/94 → 24/06/94

Access to Document

10.1109/ICDCS.1994.302421

Link to publication in Scopus

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

@inproceedings{dc7144433b554629b82ec4464eee1529,

title = "On the impact of sense of direction in arbitrary networks",

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.",

author = "Bernard Mans and Nicola Santoro",

year = "1994",

doi = "10.1109/ICDCS.1994.302421",

language = "English",

isbn = "0818658401",

pages = "258--265",

booktitle = "Proceedings of the 14th International Conference on Distributed Computing Systems, 1994",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

}

Mans, B & Santoro, N 1994, On the impact of sense of direction in arbitrary networks. in Proceedings of the 14th International Conference on Distributed Computing Systems, 1994., 302421, Institute of Electrical and Electronics Engineers (IEEE), Piscataway, NJ, pp. 258-265, Proceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems, Poznan, Pol, 21/06/94. https://doi.org/10.1109/ICDCS.1994.302421

On the impact of sense of direction in arbitrary networks. / Mans, Bernard; Santoro, Nicola.

Proceedings of the 14th International Conference on Distributed Computing Systems, 1994. Piscataway, NJ : Institute of Electrical and Electronics Engineers (IEEE), 1994. p. 258-265 302421.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution

TY - GEN

T1 - On the impact of sense of direction in arbitrary networks

AU - Mans, Bernard

AU - Santoro, Nicola

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028583685&partnerID=8YFLogxK

U2 - 10.1109/ICDCS.1994.302421

DO - 10.1109/ICDCS.1994.302421

M3 - Conference proceeding contribution

SN - 0818658401

SP - 258

EP - 265

BT - Proceedings of the 14th International Conference on Distributed Computing Systems, 1994

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, NJ

ER -