Self-stabilizing leader election in optimal space under an arbitrary scheduler

被引：27

作者：

Datta, Ajoy K. ^{[1
]}

Larmore, Lawrence L. ^{[1
]}

Vemula, Priyanka ^{[1
]}

机构：

[1] Univ Nevada, Sch Comp Sci, Las Vegas, NV 89154 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2011年 / 412卷 / 40期

关键词：

Distributed algorithm; Leader election; Self-stabilization; Silent algorithm; Unfair daemon; PROTOCOLS; SYSTEMS;

D O I：

10.1016/j.tcs.2010.05.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A silent self-stabilizing asynchronous distributed algorithm, SSLE, is given for the leader election problem in a connected unoriented (bidirectional) network with unique IDs. SSLE also constructs a BFS tree on the network rooted at that leader. SSLE uses 0(log n) space per process and stabilizes in 0(n) rounds, against the unfair daemon, where n is the number of processes in the network. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：5541 / 5561

页数：21

共 8 条

[1]

AFEK Y, 1997, 8 ANN ACM S DISCR AL, P111

[2] DISTRIBUTED RESET [J].

ARORA, A ;

GOUDA, M .

IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (09) :1026-1038

[3]

AWERBUCH B, 1993, 25 ANN ACM S THEOR C, P652

[4]

Datta AK, 2008, LECT NOTES COMPUT SC, V5340, P109, DOI 10.1007/978-3-540-89335-6_11

[5] SELF-STABILIZING SYSTEMS IN SPITE OF DISTRIBUTED CONTROL [J].

DIJKSTRA, EW .

COMMUNICATIONS OF THE ACM, 1974, 17 (11) :643-644

[6]

Dolev S, 1997, CHIC J THEOR COMPUT, P1

[7]

Dolev S., 2000, Self-Stabilization

[8] STABILIZING COMMUNICATION PROTOCOLS [J].

GOUDA, MG ;

MULTARI, NJ .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (04) :448-458

← 1 →