Advances in Population Protocols and Graph Exploration

The field of distributed computing is witnessing significant advancements, particularly in the areas of population protocols and graph exploration. Researchers are focusing on developing efficient algorithms and techniques to solve fundamental problems, such as leader election, relative majority, and graph exploration. A key direction in this field is the trade-off between time and space complexity, with a emphasis on minimizing the number of states and interactions required to achieve a certain outcome. Notable contributions include the development of novel techniques for collision detection and energy minimization-inspired protocols. Noteworthy papers in this area include:

  • A Space-Time Trade-off for Fast Self-Stabilizing Leader Election in Population Protocols, which presents a parametrized protocol that achieves asymptotically optimal time using a reduced number of states.
  • Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors, which introduces a novel graph exploration algorithm that requires only six colors.
  • Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols, which presents a protocol that solves the relative majority problem with a cubic number of states.
  • An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model, which provides an almost tight lower bound on the stabilization time for the plurality consensus problem.

Sources

A Space-Time Trade-off for Fast Self-Stabilizing Leader Election in Population Protocols

Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors

Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols

An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model

Built with on top of