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 with event-driven activation
standard settingverifiedUnder event-driven activation, silent oblivious particles with a 1-hop view and no common direction scatter from any configuration without obstacles.
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: event-driven
- A contracted particle is activated as soon as it has, or gains, a neighbour, and a contracted particle with no neighbour is not activated. The adversary still chooses the duration of each activation, the time an expansion or a contraction takes, and the activation of expanded particles; operations stay non-atomic.
- 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 and current best (Theorem 6, Corollary 2): the rule of the primer, from any configuration of contracted particles, connected or not; particles share no direction and no chirality. No bound on rounds or moves.
Open questions
Bound the rounds and moves of scattering under event-driven activation Navarra et al. 2025.
Scattering with obstacles: unsolvable deterministically with a 1-hop view even under a synchronous scheduler (Theorem 7 of Navarra et al. 2025); which extra capability (chirality, a 2-hop view, randomised choices) makes it solvable?
Notes
Scattering is Simple Distancing (Definition 4 of Navarra et al. 2025): eventually every particle is contracted and has no neighbour; under event-driven activation the particles then stop. The proof takes the smallest regular hexagon around a fixed centre containing all particles: no particle on its border moves inwards (Lemma 3), each particle moves outwards at most \(n-1\) times (Lemma 4), and induction on \(n\) finishes (Theorem 6). With obstacles, where Strong Distancing also asks particles to keep away from obstacles, the problem is unsolvable even under a synchronous scheduler, in which only particles with a neighbour may move (Theorem 7); the paper then tests heuristic rules with randomised tie-breaking in simulation only. 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
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.