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 › peer-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 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

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

note = "Proceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems ; Conference date: 21-06-1994 Through 24-06-1994",

}

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 › peer-review

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

AN - SCOPUS:0028583685

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

T2 - Proceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems

Y2 - 21 June 1994 through 24 June 1994

ER -

On the impact of sense of direction in arbitrary networks

Abstract

Other

Access to Document

Fingerprint

Cite this