Self-Stabilizing Weak Leader Election in Anonymous Trees Using Constant Memory per Edge

Document Type

Article

Publication Date

1-1-2017

Publication Title

Parallel Processing Letters

Volume

27

Issue

2

Abstract

We propose a deterministic silent self-stabilizing algorithm for the weak leader election problem in anonymous trees. Our algorithm is designed in the message passing model, and requires only O(1) bits of memory per edge. It does not necessitate the a priori knowledge of any global parameter on the network. Finally, its stabilization time is at most 3D2×(X+2Imax+2) time units, where is the diameter of the network, X is an upper bound on the time to execute some recurrent code by processes, and Imax is the maximal number of messages initially in a link. © 2017 World Scientific Publishing Company.

Keywords

Self-stabilization; Weak leader election; Anonymous tree; Message passing; Intermittent faults

Language

english

Find It

UNLV article access

Find in your library

Share

COinS