A note on the token distribution problem

Kieran T. Herley

doi:10.1016/0020-0190(91)90090-5

A note on the token distribution problem

Kieran T. Herley

Cornell University

Research output: Contribution to journal › Article › peer-review

Abstract

Consider a set of packets distributed unevenly among the nodes of a bounded degree network of processors. The Token Distribution Problem involves redistributing these packets so that each node holds the same number. Token distribution algorithms underlie several efficient routing algorithms. Peleg and Upfal formulated this problem and presented a communication-efficient solution. In this paper we refine their techniques to provide a solution that is efficient with respect to both communication and local computation.

Original language	English
Pages (from-to)	329-334
Number of pages	6
Journal	Information Processing Letters
Volume	38
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(91)90090-5
Publication status	Published - 28 Jun 1991
Externally published	Yes

Keywords

expander graphs
Parallel algorithms
routing

Access to Document

10.1016/0020-0190(91)90090-5

Cite this

@article{14cdb8cae4ed4488b14193c70462e2fa,

title = "A note on the token distribution problem",

abstract = "Consider a set of packets distributed unevenly among the nodes of a bounded degree network of processors. The Token Distribution Problem involves redistributing these packets so that each node holds the same number. Token distribution algorithms underlie several efficient routing algorithms. Peleg and Upfal formulated this problem and presented a communication-efficient solution. In this paper we refine their techniques to provide a solution that is efficient with respect to both communication and local computation.",

keywords = "expander graphs, Parallel algorithms, routing",

author = "Herley, \{Kieran T.\}",

year = "1991",

month = jun,

day = "28",

doi = "10.1016/0020-0190(91)90090-5",

language = "English",

volume = "38",

pages = "329--334",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - A note on the token distribution problem

AU - Herley, Kieran T.

PY - 1991/6/28

Y1 - 1991/6/28

N2 - Consider a set of packets distributed unevenly among the nodes of a bounded degree network of processors. The Token Distribution Problem involves redistributing these packets so that each node holds the same number. Token distribution algorithms underlie several efficient routing algorithms. Peleg and Upfal formulated this problem and presented a communication-efficient solution. In this paper we refine their techniques to provide a solution that is efficient with respect to both communication and local computation.

AB - Consider a set of packets distributed unevenly among the nodes of a bounded degree network of processors. The Token Distribution Problem involves redistributing these packets so that each node holds the same number. Token distribution algorithms underlie several efficient routing algorithms. Peleg and Upfal formulated this problem and presented a communication-efficient solution. In this paper we refine their techniques to provide a solution that is efficient with respect to both communication and local computation.

KW - expander graphs

KW - Parallel algorithms

KW - routing

UR - https://www.scopus.com/pages/publications/0026170468

U2 - 10.1016/0020-0190(91)90090-5

DO - 10.1016/0020-0190(91)90090-5

M3 - Article

AN - SCOPUS:0026170468

SN - 0020-0190

VL - 38

SP - 329

EP - 334

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

A note on the token distribution problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this