Abstract
In the population protocol model Angluin et al. proposed in 2004, there exists no selfstabilizing leader election protocol for complete graphs, arbitrary graphs, trees, lines, degreebounded graphs and so on unless the protocol knows the exact number of nodes. To circumvent the impossibility, we introduced the concept of loosestabilization in 2009, which relaxes the closure requirement of selfstabilization. A looselystabilizing protocol guarantees that starting from any initial configuration a system reaches a safe configuration, and after that, the system keeps its specification (e.g. the unique leader) not forever, but for a sufficiently long time (e.g. exponentially large time with respect to the number of nodes). Our previous works presented two looselystabilizing leader election protocols for arbitrary graphs; One uses agent identifiers and the other uses random numbers to elect a unique leader. In this paper, we present a looselystabilizing protocol that solves leader election on arbitrary graphs without agent identifiers nor random numbers. By the combination of viruspropagation and tokencirculation, the proposed protocol achieves polynomial convergence time and exponential holding time without such external entities. Specifically, given upper bounds N and Delta of the number of nodes n and the maximum degree of nodes delta respectively, it reaches a safe configuration within O(m*n^3*d + m*N*Delta^2*log(N)) expected steps, and keeps the unique leader for Omega(N*e^N) expected steps where m is the number of edges and d is the diameter of the graph. To measure the time complexity of the protocol, we assume the uniformly random scheduler which is widely used in the field of the population protocols.
BibTeX  Entry
@InProceedings{sudo_et_al:LIPIcs:2016:6605,
author = {Yuichi Sudo and Fukuhito Ooshita and Hirotsugu Kakugawa and Toshimitsu Masuzawa},
title = {{LooselyStabilizing Leader Election on Arbitrary Graphs in Population Protocols Without Identifiers nor Random Numbers}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {116},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897989},
ISSN = {18688969},
year = {2016},
volume = {46},
editor = {Emmanuelle Anceaume and Christian Cachin and Maria PotopButucaru},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6605},
URN = {urn:nbn:de:0030drops66054},
doi = {10.4230/LIPIcs.OPODIS.2015.14},
annote = {Keywords: Loosestabilization, Population protocols, Leader election}
}
Keywords: 

Loosestabilization, Population protocols, Leader election 
Seminar: 

19th International Conference on Principles of Distributed Systems (OPODIS 2015) 
Issue Date: 

2016 
Date of publication: 

29.08.2016 