A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors

Hans L. Bodlaender

A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors

Hans L. Bodlaender^*

^*Corresponding author for this work

Utrecht University

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

Abstract

In this article we prove a lower bound of 1 2nH_n ≈ 0.346n log n for the average number of messages for distributed leader finding in asynchronous, bidirectional rings of processors.

Original language	English
Pages (from-to)	287-290
Number of pages	4
Journal	Information Processing Letters
Volume	27
Issue number	6
Publication status	Published - 13 May 1988
Externally published	Yes

Keywords

Distributed computing
leader finding on rings of processors
lower bound

Cite this

@article{c21898a9fc9648ad9bf57c09e5f94059,

title = "A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors",

abstract = "In this article we prove a lower bound of 1 2nHn ≈ 0.346n log n for the average number of messages for distributed leader finding in asynchronous, bidirectional rings of processors.",

keywords = "Distributed computing, leader finding on rings of processors, lower bound",

author = "Bodlaender, {Hans L.}",

year = "1988",

month = may,

day = "13",

language = "English",

volume = "27",

pages = "287--290",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier BV",

number = "6",

}

TY - JOUR

T1 - A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors

AU - Bodlaender, Hans L.

PY - 1988/5/13

Y1 - 1988/5/13

N2 - In this article we prove a lower bound of 1 2nHn ≈ 0.346n log n for the average number of messages for distributed leader finding in asynchronous, bidirectional rings of processors.

AB - In this article we prove a lower bound of 1 2nHn ≈ 0.346n log n for the average number of messages for distributed leader finding in asynchronous, bidirectional rings of processors.

KW - Distributed computing

KW - leader finding on rings of processors

KW - lower bound

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

M3 - Article

AN - SCOPUS:0024011359

SN - 0020-0190

VL - 27

SP - 287

EP - 290

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors

Abstract

Keywords

Other files and links

Fingerprint

Cite this