TIME-OPTIMAL LEADER ELECTION IN GENERAL NETWORKS

被引:67
作者
PELEG, D
机构
[1] Department of Computer Science, Stanford University, Stanford
关键词
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 条
  • [21] Time-optimal parallel algorithms for constructing optimal virtual cellular networks
    Zhang, JY
    Vrbsky, S
    Fan, GB
    NINTH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS, PROCEEDINGS, 2002, : 42 - 47
  • [22] Quasi-optimal leader election algorithms in radio networks with log-logarithmic awake time slots
    Lavault, C
    Marckert, JF
    Ravelomanana, V
    ICT'2003: 10TH INTERNATIONAL CONFERENCE ON TELECOMMUNICATIONS, VOLS I AND II, CONFERENCE PROCEEDINGS, 2003, : 1113 - 1119
  • [23] Brief Announcement: Optimal Leader Election In Multi-Hop Radio Networks
    Czumaj, Artur
    Davies, Peter
    PROCEEDINGS OF THE 2016 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'16), 2016, : 47 - 49
  • [24] SWITCHING INSTANTS IN TIME-OPTIMAL CONTROL WITH GENERAL HARMONIC DISTURBANCE
    PELCZEWSKI, W
    LAWRYNOWICZ, J
    BULLETIN DE L ACADEMIE POLONAISE DES SCIENCES-SERIE DES SCIENCES TECHNIQUES, 1974, 22 (10): : 879 - 885
  • [25] Efficient leader election in complete networks
    Villadangos, J
    Córdoba, A
    Fariña, F
    Prieto, M
    13TH EUROMICRO CONFERENCE ON PARALLEL, DISTRIBUTED AND NETWORK-BASED PROCESSING, PROCEEDINGS, 2005, : 136 - 143
  • [26] WiLE: Leader Election in Wireless Networks
    Sheshashayee, Abhimanyu Venkatraman
    Basagni, Stefano
    AD HOC & SENSOR WIRELESS NETWORKS, 2019, 44 (1-2) : 59 - 81
  • [27] Distributed time-optimal scheduling for convergecast in wireless sensor networks
    Gandham, Shashidhar
    Zhang, Ying
    Huang, Qingfeng
    COMPUTER NETWORKS, 2008, 52 (03) : 610 - 629
  • [28] Near-Optimal Time-Energy Tradeoffs for Deterministic Leader Election
    Chang, Yi-Jun
    Duan, Ran
    Jiang, Shunhua
    ACM TRANSACTIONS ON ALGORITHMS, 2023, 19 (04)
  • [29] Almost Logarithmic-Time Space Optimal Leader Election in Population Protocols
    Gasieniec, Leszek
    Stachowiak, Grzegorz
    Uznanski, Przemyslaw
    SPAA'19: PROCEEDINGS OF THE 31ST ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURESS, 2019, 2019, : 93 - 102
  • [30] A General, Fast, and Robust Implementation of the Time-Optimal Path Parameterization Algorithm
    Quang-Cuong Pham
    IEEE TRANSACTIONS ON ROBOTICS, 2014, 30 (06) : 1533 - 1540