Bridging
Particles moving between two sites must build a bridge across a gap that balances path length against bridge cost.
Problem statement and measuresexpand
Particles occupy a path between two fixed sites across a gap in the terrain. They run a local Markov chain that rewards neighbours and penalises particles over the gap. The system should form a shortcut bridge whose length and cost are balanced, with high probability in the stationary distribution.
Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).
Markov chain, sequential
standard settingverifiedA local stochastic rule builds near-optimal shortcut bridges; for large biases a single bridge forms.
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 for shortcut bridging; the trade-off depends on the gap angle.
A single bridge almost certainly forms for large biases; occupancy-chain technique.
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.