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 条
[21]   Brief Announcement: Optimal Time and Space Leader Election in Population Protocols [J].
Berenbrink, Petra ;
Giakkoupis, George ;
Kling, Peter .
PROCEEDINGS OF THE 39TH SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, PODC 2020, 2020, :218-220
[22]   Optimal time-space tradeoff for shared memory leader election [J].
Afek, Y ;
Stupp, G .
JOURNAL OF ALGORITHMS, 1997, 25 (01) :95-117
[23]   Time-optimal parallel algorithms for constructing optimal virtual cellular networks [J].
Zhang, JY ;
Vrbsky, S ;
Fan, GB .
NINTH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS, PROCEEDINGS, 2002, :42-47
[24]   Quasi-optimal leader election algorithms in radio networks with log-logarithmic awake time slots [J].
Lavault, C ;
Marckert, JF ;
Ravelomanana, V .
ICT'2003: 10TH INTERNATIONAL CONFERENCE ON TELECOMMUNICATIONS, VOLS I AND II, CONFERENCE PROCEEDINGS, 2003, :1113-1119
[25]   Brief Announcement: Optimal Leader Election In Multi-Hop Radio Networks [J].
Czumaj, Artur ;
Davies, Peter .
PROCEEDINGS OF THE 2016 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'16), 2016, :47-49
[26]   SWITCHING INSTANTS IN TIME-OPTIMAL CONTROL WITH GENERAL HARMONIC DISTURBANCE [J].
PELCZEWSKI, W ;
LAWRYNOWICZ, J .
BULLETIN DE L ACADEMIE POLONAISE DES SCIENCES-SERIE DES SCIENCES TECHNIQUES, 1974, 22 (10) :879-885
[27]   Efficient leader election in complete networks [J].
Villadangos, J ;
Córdoba, A ;
Fariña, F ;
Prieto, M .
13TH EUROMICRO CONFERENCE ON PARALLEL, DISTRIBUTED AND NETWORK-BASED PROCESSING, PROCEEDINGS, 2005, :136-143
[28]   WiLE: Leader Election in Wireless Networks [J].
Sheshashayee, Abhimanyu Venkatraman ;
Basagni, Stefano .
AD HOC & SENSOR WIRELESS NETWORKS, 2019, 44 (1-2) :59-81
[29]   Near-Optimal Time-Energy Tradeoffs for Deterministic Leader Election [J].
Chang, Yi-Jun ;
Duan, Ran ;
Jiang, Shunhua .
ACM TRANSACTIONS ON ALGORITHMS, 2023, 19 (04)
[30]   Almost Logarithmic-Time Space Optimal Leader Election in Population Protocols [J].
Gasieniec, Leszek ;
Stachowiak, Grzegorz ;
Uznanski, Przemyslaw .
SPAA'19: PROCEEDINGS OF THE 31ST ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURESS, 2019, 2019, :93-102
12345