Document Type

Conference Proceeding

Publication Date

12-17-2018

Publication Title

22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Publisher

Schloss Dagstuhl – Leibniz Center for Informatics

Publisher Location

Hong Kong, China

First page number:

1

Last page number:

16

Abstract

A loosely-stabilizing leader election protocol with polylogarithmic convergence time in the population protocol model is presented in this paper. In the population protocol model, which is a common abstract model of mobile sensor networks, it is known to be impossible to design a self-stabilizing leader election protocol. Thus, in our prior work, we introduced the concept of loose-stabilization, which is weaker than self-stabilization but has similar advantage as self-stabilization in practice. Following this work, several loosely-stabilizing leader election protocols are presented. The loosely-stabilizing leader election guarantees that, starting from an arbitrary configuration, the system reaches a safe configuration with a single leader within a relatively short time, and keeps the unique leader for an sufficiently long time thereafter. The convergence times of all the existing loosely-stabilizing protocols, i.e., the expected time to reach a safe configuration, are polynomial in n where n is the number of nodes (while the holding times to keep the unique leader are exponential in n). In this paper, a loosely-stabilizing protocol with polylogarithmic convergence time is presented. Its holding time is not exponential, but arbitrarily large polynomial in n.

Keywords

Loose-stabilization; Population protocols; Leader election

Disciplines

Computer Sciences

File Format

pdf

File Size

569 KB

Language

English

Creative Commons License

Creative Commons Attribution 3.0 License
This work is licensed under a Creative Commons Attribution 3.0 License.

Download

UNLV article access

Share

COinS