THE SPACE COMPLEXITY OF LEADER ELECTION IN ANONYMOUS NETWORKS

被引：2

作者：

Ando, Ei ^{[1
]}

Ono, Hirotaka ^{[1
,2
]}

Sadakane, Kunihiko ^{[1
]}

Yamashita, Masafumi ^{[1
,2
]}

机构：

[1] Kyushu Univ, Dept Comp Sci & Commun Engn, Nishi Ku, Fukuoka 8190395, Japan

[2] Inst Syst Informat Technol & Nanotechnol, Sawara Ku, Fukuoka 8140001, Japan

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2010年 / 21卷 / 03期

关键词：

Distributed computing; anonymous networks; leader election problem; space complexity;

D O I：

10.1142/S0129054110007349

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The leader election problem is unsolvable for some anonymous networks. A leader election algorithm for anonymous networks thus elects a leader whenever it is possible; if it is impossible, the algorithm reports this fact. This paper investigates the space complexity of the leader election problem in anonymous networks, where the space complexity is measured by the size (in the number of bits) of memory per processor used by a leader election algorithm. We first observe that Omega(M + log d) bits are necessary and then show that O(n log d) bits are sufficient to construct a leader election algorithm that works on any network, where n,d and M are the number of processors, the maximum number of adjacent processors, and the maximum size (in bits) of a message, respectively. We next show that, for any arbitrarily fixed constant n, O(1) bits are sufficient to construct a leader election algorithm that works in any network of size n.

引用

页码：427 / 440

页数：14

共 13 条

[1]

Angluin Dana, 1980, P 12 ANN ACM S THEOR, P82, DOI DOI 10.1145/800141.804655

[2]

ATTIYA H, 1998, P INT S DISTR COMP, P49

[3]

Boldi P., 1996, Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, P16

[4]

Das S, 2006, LECT NOTES COMPUT SC, V4288, P732

[5]

Dobrev S, 2003, PDPTA'03: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS 1-4, P1400

[6]

Gross J. L., 2006, GRAPH THEORY ITS APP

[7]

Johnson R.E., 1985, Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC '85, P13

[8] UNIVERSAL COVERS OF GRAPHS - ISOMORPHISM TO DEPTH N-1 IMPLIES ISOMORPHISM TO ALL DEPTHS [J].

NORRIS, N .

DISCRETE APPLIED MATHEMATICS, 1995, 56 (01) :61-74

[9]

Sakamoto N., 1999, Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, P173, DOI 10.1145/301308.301352

[10] Computing on anonymous networks .1. Characterizing the solvable cases [J].

Yamashita, M ;

Kameda, T .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1996, 7 (01) :69-89

← 1 2 →