6533b828fe1ef96bd128842b
RESEARCH PRODUCT
Distributed Leader Election and Computation of Local Identifiers for Programmable Matter
Nicolas GastineauOlivier TogniWahabou AbdouNader Mbareksubject
Vertex (graph theory)0209 industrial biotechnologyLeader electionComputer scienceComputation[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technology[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Topology01 natural sciencesGraphIdentifier[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]Programmable matter020901 industrial engineering & automation010201 computation theory & mathematicsGraph coloringdescription
International audience; The context of this paper is programmable matter, which consists of a set of computational elements, called particles, in an infinite graph. The considered infinite graphs are the square, triangular and king grids. Each particle occupies one vertex, can communicate with the adjacent particles, has the same clockwise direction and knows the local positions of neighborhood particles. Under these assumptions, we describe a new leader election algorithm affecting a variable to the particles, called the k-local identifier, in such a way that particles at close distance have each a different k-local identifier. For all the presented algorithms, the particles only need a O(1)-memory space.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2019-02-01 |