Bit-optimal election in synchronous rings

Hans L. Bodlaender; Gerard Tel

doi:10.1016/0020-0190(90)90187-3

Bit-optimal election in synchronous rings

Hans L. Bodlaender^*, Gerard Tel

^*Corresponding author for this work

Utrecht University

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

Abstract

An election algorithm is presented for synchronous rings with unknown size. The bit complexity of the proposed algorithm is linear in the number of processes. The time complexity is polynomial in the number of processes, but exponential in the smallest identity of any process.

Original language	English
Pages (from-to)	53-56
Number of pages	4
Journal	Information Processing Letters
Volume	36
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(90)90187-3
Publication status	Published - 1 Dec 1990
Externally published	Yes

Keywords

Analysis and complexity of algorithms
Bit optimal election
Synchronous rings

Access to Document

10.1016/0020-0190(90)90187-3

Cite this

@article{1ba1f95873c3480ea5f2f6a8ee24330c,

title = "Bit-optimal election in synchronous rings",

abstract = "An election algorithm is presented for synchronous rings with unknown size. The bit complexity of the proposed algorithm is linear in the number of processes. The time complexity is polynomial in the number of processes, but exponential in the smallest identity of any process.",

keywords = "Analysis and complexity of algorithms, Bit optimal election, Synchronous rings",

author = "Bodlaender, {Hans L.} and Gerard Tel",

year = "1990",

month = dec,

day = "1",

doi = "10.1016/0020-0190(90)90187-3",

language = "English",

volume = "36",

pages = "53--56",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier BV",

number = "1",

}

TY - JOUR

T1 - Bit-optimal election in synchronous rings

AU - Bodlaender, Hans L.

AU - Tel, Gerard

PY - 1990/12/1

Y1 - 1990/12/1

N2 - An election algorithm is presented for synchronous rings with unknown size. The bit complexity of the proposed algorithm is linear in the number of processes. The time complexity is polynomial in the number of processes, but exponential in the smallest identity of any process.

AB - An election algorithm is presented for synchronous rings with unknown size. The bit complexity of the proposed algorithm is linear in the number of processes. The time complexity is polynomial in the number of processes, but exponential in the smallest identity of any process.

KW - Analysis and complexity of algorithms

KW - Bit optimal election

KW - Synchronous rings

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

U2 - 10.1016/0020-0190(90)90187-3

DO - 10.1016/0020-0190(90)90187-3

M3 - Article

AN - SCOPUS:0025505065

SN - 0020-0190

VL - 36

SP - 53

EP - 56

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

Bit-optimal election in synchronous rings

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this