Probabilistic distributed algorithm for uniform election in polyo-triangular grid graphs

摘要

Electing in a network is to chose one and only one element in this network. The element can be used later to manage the resource sharing (printer, connection, ...) or centralize some of the network informations (size, diameter ...). In this case, many algorithms are available under different topologies and applicable under appropriate assumptions; the uniform election in trees [1], k-trees [2], polyominoides [3], and triangular grid graph [4]. The work presented here is a continuation of our last researches. Indeed, we introduce a probabilistic algorithm for uniform election in a polyo-tg graph. thereby and first, we will discuss the rules that allow us to generate in distributed manner such family of graphs. Then we present the different rules of the elimination process of our algorithm. These rules are executed in parallel with every active vertex of the network. In a second time, we analytically analyse this process. To do so, we modelled by a continuously Markov death process. We show, therefore, that our algorithm is totally fair such that all the vertices have the same probability to be elected.