Scattering of particles
Particles must reach a configuration in which no two particles occupy neighbouring nodes.
Problem statement and measuresexpand
From any initial configuration of \(n\) contracted particles (each occupying one node of the triangular lattice), the particles must reach a configuration in which no two occupy neighbouring nodes (a scattered configuration), and stop.
Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).
SILBOT
standard settingdraftSilent oblivious particles scatter from any initial configuration.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Memory: oblivious
- No persistent state and no messages; a particle decides from its view only.
- Scheduler: weak scheduler
- An activation's look, compute and move need not be atomic; concurrent activations may interfere. The scheduler of Bazzi and Briones is described as weak sequential, as non-atomic, and as fair asynchronous by different later papers Briones et al. 2023 Dufoulon et al. 2021 Chalopin et al. 2026.
- Orientation: no orientation
- Each particle labels its six incident directions in its own clockwise or counter-clockwise order, starting anywhere.
- Randomness: deterministic
- No random choices.
- Initial shape: holes allowed
- The initial set of occupied nodes induces a connected subgraph; it may enclose empty regions.
- Connectivity during execution: stays connected
- At every time the occupied nodes induce a connected subgraph.
What is known
Results, in order of publication
Introductory journal version and current best.
Open questions
None recorded for this variant.
Notes
Event-driven activation is stronger than the weak scheduler of this setting, so the placement overstates the result. The assumptions are as reported by Navarra & Piselli 2023; the full text of Navarra et al. 2025 was not reachable.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.