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
verifiedWith a 1-hop view and adversarial activation, silent oblivious particles cannot scatter; with the 2-hop view of SILBOT the question is open.
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. 2026b.
- Communication: local communication
- A particle exchanges constant-size information only with the particles on adjacent nodes, by messages or by reading and writing their memory, so information travels at most one particle per activation.
- Activation: adversarial activation
- The scheduler of the setting decides, fairly, when each particle is activated; an isolated particle may be activated, and a particle with a neighbour may wait any finite time.
- 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
- Theorem 4: deterministic, 1-hop view, no common direction and no chirality
- a particle with no neighbour must never move
- three particles in a row: whatever a particle with one neighbour does, a fair asynchronous adversary makes the middle particle move back and forth forever
- open with the 2-hop view of SILBOT
Results, in order of publication
No result recorded yet.
Open questions
Is scattering solvable in SILBOT with its original 2-hop view under adversarial activation? Navarra et al. 2025 leave it open.
Notes
Model of Navarra et al. 2025 (Section 2): SILBOT particles are silent, oblivious and disoriented, all operations are non-atomic, and a fair adversary decides activations; for scattering the view is restricted to 1 hop. The impossibility uses three particles in a row (Figures 3 and 4): a particle with one neighbour must move, either straight away from it or to one of two symmetric nodes, and in both cases the adversary makes the middle particle move back and forth forever. Theorem 7 (obstacles, even synchronous) is recorded on the event-driven setting. Checked against the full text.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Branches from here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.