{"ID":2889901,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.20201","arxiv_id":"2507.20201","title":"Silent Self-Stabilising Leader Election in Programmable Matter Systems with Holes","abstract":"Leader election is a fundamental problem in distributed computing, particularly within programmable matter systems, where coordination among simple computational entities is crucial for solving complex tasks. In these systems, particles (i.e., constant-memory computational entities) operate in a regular triangular grid as described in the geometric Amoebot model. While leader election has been extensively studied in non self-stabilising settings, self-stabilising solutions remain more limited. In this work, we study the problem of self-stabilising leader election in connected (but not necessarily simply connected) configurations. We present the first self-stabilising algorithm for connected programmable matter systems that guarantees the election of a unique leader under an unfair scheduler, for oblivious particles (i.e., particles with no persistent memory) that share a common sense of direction. Our approach leverages particle movement, a capability not previously exploited in the self-stabilising context. We show that movement in conjunction with particles sharing a sense of orientation and operating in a grid can overcome classical impossibility results for constant-memory systems established by Dolev, Gouda and Schneider (1999).","short_abstract":"Leader election is a fundamental problem in distributed computing, particularly within programmable matter systems, where coordination among simple computational entities is crucial for solving complex tasks. In these systems, particles (i.e., constant-memory computational entities) operate in a regular triangular grid...","url_abs":"https://arxiv.org/abs/2507.20201","url_pdf":"https://arxiv.org/pdf/2507.20201v2","authors":"[\"Jérémie Chalopin\",\"Shantanu Das\",\"Maria Kokkou\"]","published":"2025-07-27T09:39:10Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false}