Scholarlink

<p>The problem of electing a unique leader is central to all distributed systems, including programmable matter systems where particles have constant size memory. In this paper, we present a silent self-stabilising, deterministic, stationary, election algorithm for particles having constant memory, assuming that the system is simply connected. Our algorithm is elegant and simple, and requires constant memory per particle. We prove that our algorithm always stabilises to a configuration with a unique leader, under a daemon satisfying some fairness guarantees (<i>Gouda fairness</i> [<CitationRef CitationID="CR27">27</CitationRef>]). We use the special geometric properties of programmable matter in 2D triangular grids to obtain the first self-stabilising algorithm for such systems. This result is surprising since it is known that silent self-stabilising algorithms for election in general distributed networks require <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\Omega (\log {n})\)</EquationSource> </InlineEquation> bits of memory per node, even for ring topologies [<CitationRef CitationID="CR20">20</CitationRef>].</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Deterministic self-stabilising leader election for programmable matter with constant memory

  • 期刊论文

  • 发表日期：

    2025年12月10日

查看全文
  • Jérémie Chalopin,
  • Shantanu Das,
  • Maria Kokkou

摘要

The problem of electing a unique leader is central to all distributed systems, including programmable matter systems where particles have constant size memory. In this paper, we present a silent self-stabilising, deterministic, stationary, election algorithm for particles having constant memory, assuming that the system is simply connected. Our algorithm is elegant and simple, and requires constant memory per particle. We prove that our algorithm always stabilises to a configuration with a unique leader, under a daemon satisfying some fairness guarantees (Gouda fairness [27]). We use the special geometric properties of programmable matter in 2D triangular grids to obtain the first self-stabilising algorithm for such systems. This result is surprising since it is known that silent self-stabilising algorithms for election in general distributed networks require \(\Omega (\log {n})\) bits of memory per node, even for ring topologies [20].