Energy distribution
Only some particles reach the energy source; particles must share energy so that every action is paid for.
Problem statement and measuresexpand
Each action costs energy, and only \(s\) particles, the sources, can harvest energy from outside. Particles must distribute energy locally so that every particle can act, or so that a given energy-agnostic algorithm runs correctly. Time is in rounds.
Measures: Time, asynchronous rounds.
Unfair adversary
standard settingverifiedEnergy can be distributed in \(O(n)\) rounds, against an \(\Omega(n/s)\) lower bound; any conforming energy-agnostic algorithm becomes energy-constrained with \(O(n^2)\) rounds of overhead per action, even under an unfair adversary.
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: 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 8); a self-stabilising spanning forest tolerates crash failures.
Theorem 4: \(T_A(n)\) is the running time of the energy-agnostic algorithm. Composes with the concurrency control framework.
Open questions
None recorded for this variant.
Notes
No orientation is assumed. Checked against the full texts.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.