Alignment
Oriented particles, following a local stochastic rule, must align their orientations.
Problem statement and measuresexpand
Each particle carries one of \(q \ge 2\) orientations, a spin state, not a sense of direction. Particles run a local Markov chain; the system should be aligned (most particles share an orientation) or not, depending on the bias, with high probability in the stationary distribution, both when connectivity is kept and when particles may disconnect.
Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).
Markov chain, sequential
standard settingverifiedFor every \(q \ge 2\), alignment and non-alignment are both achieved by the bias.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Memory: constant memory
- Each particle has \(O(1)\) bits of persistent memory and reads or writes neighbours' memory.
- Scheduler: sequential
- At most one particle is active at any time.
- Orientation: no orientation
- Each particle labels its six incident directions in its own clockwise or counter-clockwise order, starting anywhere.
- Randomness: randomized
- Particles flip fair coins; guarantees hold with high probability or in expectation.
- 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; simply connected and unconstrained settings.
Open questions
None recorded for this variant.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.