Interval routing schemes allow broadcasting with linear message-complexity

Pierre Fraigniaud; Cyril Gavoille; Bernard Mans

doi:10.1145/343477.343503

Interval routing schemes allow broadcasting with linear message-complexity

Pierre Fraigniaud, Cyril Gavoille, Bernard Mans

School of Computing

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

Abstract

The purpose of compact routing is to provide a labeling of the nodes of a network, and a way to encode the routing tables so that routing can be performed efficiently (e.g., on shortest paths) while keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving therefore the O(m + n) previous known bound.

Original language	English
Title of host publication	Nineteenth Annual ACM Symposium on Principles of Distributed Computing
Editors	James Anderson
Place of Publication	New York
Publisher	ACM Press
Pages	11-20
Number of pages	10
ISBN (Print)	1581131836
DOIs	https://doi.org/10.1145/343477.343503
Publication status	Published - 2000
Event	19th Annual ACM Symposium on Principles of Distributed Computing - Portland, OR, USA Duration: 16 Jul 2000 → 19 Jul 2000

Other

Other	19th Annual ACM Symposium on Principles of Distributed Computing
City	Portland, OR, USA
Period	16/07/00 → 19/07/00

Access to Document

10.1145/343477.343503

Cite this

@inproceedings{aedb0e05acd24944b3cf6f3700db4108,

title = "Interval routing schemes allow broadcasting with linear message-complexity",

abstract = "The purpose of compact routing is to provide a labeling of the nodes of a network, and a way to encode the routing tables so that routing can be performed efficiently (e.g., on shortest paths) while keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving therefore the O(m + n) previous known bound.",

author = "Pierre Fraigniaud and Cyril Gavoille and Bernard Mans",

year = "2000",

doi = "10.1145/343477.343503",

language = "English",

isbn = "1581131836 ",

pages = "11--20",

editor = "James Anderson",

booktitle = "Nineteenth Annual ACM Symposium on Principles of Distributed Computing",

publisher = "ACM Press",

note = "19th Annual ACM Symposium on Principles of Distributed Computing ; Conference date: 16-07-2000 Through 19-07-2000",

}

Fraigniaud, P, Gavoille, C & Mans, B 2000, Interval routing schemes allow broadcasting with linear message-complexity. in J Anderson (ed.), Nineteenth Annual ACM Symposium on Principles of Distributed Computing. ACM Press, New York, pp. 11-20, 19th Annual ACM Symposium on Principles of Distributed Computing, Portland, OR, USA, 16/07/00. https://doi.org/10.1145/343477.343503

TY - GEN

T1 - Interval routing schemes allow broadcasting with linear message-complexity

AU - Fraigniaud, Pierre

AU - Gavoille, Cyril

AU - Mans, Bernard

PY - 2000

Y1 - 2000

N2 - The purpose of compact routing is to provide a labeling of the nodes of a network, and a way to encode the routing tables so that routing can be performed efficiently (e.g., on shortest paths) while keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving therefore the O(m + n) previous known bound.

AB - The purpose of compact routing is to provide a labeling of the nodes of a network, and a way to encode the routing tables so that routing can be performed efficiently (e.g., on shortest paths) while keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving therefore the O(m + n) previous known bound.

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

U2 - 10.1145/343477.343503

DO - 10.1145/343477.343503

M3 - Conference proceeding contribution

AN - SCOPUS:0034503758

SN - 1581131836

SP - 11

EP - 20

BT - Nineteenth Annual ACM Symposium on Principles of Distributed Computing

A2 - Anderson, James

PB - ACM Press

CY - New York

T2 - 19th Annual ACM Symposium on Principles of Distributed Computing

Y2 - 16 July 2000 through 19 July 2000

ER -

Interval routing schemes allow broadcasting with linear message-complexity

Abstract

Other

Access to Document

Other files and links

Fingerprint

Cite this