TIME-OPTIMAL LEADER ELECTION IN GENERAL NETWORKS

被引：67
|
作者：
PELEG, D
机构：
[1] Department of Computer Science, Stanford University, Stanford
来源：
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 1990年 / 8卷 / 01期
关键词：
D O I：
10.1016/0743-7315(90)90074-Y
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This note presents a simple time-optimal distributed algorithm for electing a leader in a general network. For several important classes of networks this algorithm is also message-optimal and thus performs better than previous algorithms for the problem. © 1990.
引用
收藏
页码：96 / 99
页数：4
相关论文
共 50 条
  • [1] Time-Optimal Leader Election in Population Protocols
    Sudo, Yuichi
    Ooshita, Fukuhito
    Izumi, Taisuke
    Kakugawa, Hirotsugu
    Masuzawa, Toshimitsu
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2020, 31 (11) : 2620 - 2632
  • [2] Brief Announcement: Beeping a Time-Optimal Leader Election
    Dufoulon, Fabien
    Burman, Janna
    Beauquier, Joffroy
    PODC'18: PROCEEDINGS OF THE 2018 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2018, : 237 - 239
  • [3] Time-Optimal Self-Stabilizing Leader Election in Population Protocols
    Burman, Janna
    Chen, Ho-Lin
    Chen, Hsueh-Ping
    Doty, David
    Nowak, Thomas
    Severson, Eric
    Xu, Chuan
    PROCEEDINGS OF THE 2021 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC '21), 2021, : 33 - 44
  • [4] Time-Optimal Self-Stabilizing Leader Election on Rings in Population Protocols
    Yokota, Daisuke
    Sudo, Yuichi
    Masuzawa, Toshimitsu
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2021, E104A (12) : 1675 - 1684
  • [5] Singularly near optimal leader election in asynchronous networks
    Kutten, Shay
    Moses, William K.
    Pandurangan, Gopal
    Peleg, David
    arXiv, 2021,
  • [6] Time-optimal construction of overlay networks
    Goette, Thorsten
    Hinnenthal, Kristian
    Scheideler, Christian
    Werthmann, Julian
    DISTRIBUTED COMPUTING, 2023, 36 (03) : 313 - 347
  • [7] Time-Optimal Construction of Overlay Networks
    Goette, Thorsten
    Hinnenthal, Kristian
    Scheideler, Christian
    Werthmann, Julian
    PROCEEDINGS OF THE 2021 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC '21), 2021, : 457 - 468
  • [8] Time-optimal construction of overlay networks
    Thorsten Götte
    Kristian Hinnenthal
    Christian Scheideler
    Julian Werthmann
    Distributed Computing, 2023, 36 : 313 - 347
  • [9] Optimal Time and Space Leader Election in Population Protocols
    Berenbrink, Petra
    Giakkoupis, George
    Kling, Peter
    PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20), 2020, : 119 - 129
  • [10] Compact self-stabilizing leader election for general networks
    Blin, Lelia
    Tixeuil, Sebastien
    JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2020, 144 : 278 - 294
12345