Algorithms for leader election by cellular automata

被引：6

作者：

Nichitiu, C ^{[1
]}

Mazoyer, J

Rémila, E

机构：

[1] Univ St Etienne, EURISE, 23 Rue Dr Paul Michelon, F-42023 St Etienne, France

[2] Ecole Normale Super Lyon, LIP, F-69364 Lyon, France

[3] Univ St Etienne, IUT Roanne, Grima, F-42334 Roanne, France

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2001年 / 41卷 / 02期

关键词：

D O I：

10.1006/jagm.2001.1175

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present two cellular algorithms, in O(n) and respectively in O(w(2)), for the leader election problem on finite connected rings F and respectively finite connected subsets of Z(d), of eccentricity w, for any fixed d. The problem consists of finding an algorithm such that when setting the elements of F to a special state, and all the others to a state #, the cellular automaton iterates a finite number of steps and sets only one precise element of F to a special state called leader state, and all the others to a different state. We describe the algorithms in detail, give their proofs and complexities, and discuss the possible extensions. (C) 2001 Elsevier Science.

引用

页码：302 / 329

页数：28

共 50 条

[11] Distributed Algorithms on IoT Devices: Bully Leader Election
Mendez, Mariano
Tinetti, Fernando G.
Duran, Adrian M.
Obon, Daniel A.
Bartolome, Natalia G.
PROCEEDINGS 2017 INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE AND COMPUTATIONAL INTELLIGENCE (CSCI), 2017, : 1351 - 1355
[12] Experimental evaluation of leader election algorithms for ring networks
Ikegawa, Yukinori, 1600, (22):
[13] A Note on Leader Election Algorithms. Preliminary Report
Bojko, Dominik
Cichon, Jacek
2019 IEEE ASIA PACIFIC CONFERENCE ON WIRELESS AND MOBILE (APWIMOB), 2019, : 81 - 87
[14] Leader election algorithms for wireless ad hoc networks
Vasudevan, S
DeCleene, B
Immerman, N
Kurose, J
Towsley, D
DARPA INFORMATION SURVIVABILITY CONFERENCE AND EXPOSITION, VOL I, PROCEEDINGS, 2003, : 261 - 272
[15] Distributed Algorithms on IoT Devices: Bully Leader Election
Mendez, Mariano
Tinetti, Fernando G.
Duran, Adrian M.
Obon, Daniel A.
Bartolome, Natalia G.
Proceedings - 2017 International Conference on Computational Science and Computational Intelligence, CSCI 2017, 2018, : 1351 - 1355
[16] Acceleration of cellular automata algorithms using genetic algorithms
Karafyllidis, I
ADVANCES IN ENGINEERING SOFTWARE, 1999, 30 (06) : 419 - 437
[17] Leader Election Algorithms for Multi-channel Wireless Networks
Bansal, Tarun
Mittal, Neeraj
Venkatesan, S.
WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, PROCEEDINGS, 2008, 5258 : 310 - 321
[18] NEW MODEL AND ALGORITHMS FOR LEADER ELECTION IN SYNCHRONOUS FIBEROPTIC NETWORKS
ABUAMARA, H
GUMMADI, V
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994, 5 (08) : 891 - 896
[19] Initial conditions solving the leader election problem by randomized algorithms
Sakamoto, N
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2002, E85D (01) : 203 - 213
[20] Algorithms for computing preimages of cellular automata configurations
Jeras, Iztok
Dobnikar, Andrej
PHYSICA D-NONLINEAR PHENOMENA, 2007, 233 (02) : 95 - 111

← 1 2 3 4 5 →