Mobility Matters
Home›Programmable matter›Self-organising particle systems›Energy distribution

Energy distribution

Only some particles reach the energy source; particles must share energy so that every action is paid for.

Problem statement and measurescollapse
312211221011223312121012233Start: one particle has an empty batteryThe stressed particle raises a flagEnergy reaches the stressed particleThe flag reaches the rootInhibition spreads down the treeFinal: no particle stressed, all can act
Energy distribution, following Daymude et al. 2021: numbers are battery levels (capacity 3) and every action costs 1; only the source (amber) harvests energy, 1 per round. The particles form a tree hanging from the source (arrows point to parents); a particle with energy to spare passes 1 to a child whose battery is not full. A particle with an empty battery is stressed (red): it raises a flag that climbs to the root (outlined), the root then inhibits its tree (grey: inhibited particles stop spending energy on their own actions), and energy flows down until the stress is gone; then the flags clear and everyone acts again. One frame per round.

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.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Think of a colony of bacteria where only cells at the edge of the colony get food and must pass nutrients inward so that every cell can keep working. The floor is the triangular lattice: the endless graph whose nodes are the corners of a tiling of the plane by equal triangles; each node is joined by an edge to six others, its neighbours. A particle occupies one node and moves in two actions: an expansion into an empty neighbouring node, after which it occupies both, then a contraction into one of the two; so one expansion and one contraction move it by one node. The system of \(n\) particles is connected; only \(s\) of them, the sources, can take energy from outside. Every action (a move, or any step of some other algorithm) costs energy; each particle has a battery of fixed capacity and can pass a limited amount of energy to a neighbour each time it is activated (an activation). The goal is that no particle stays stressed (short of energy for its next action) for long, and that the system as a whole keeps acting; we count rounds (intervals of time in which every particle is activated at least once). Particles have constant memory and no compass.

1AlgorithmShare energy down a forest, and hold back when a particle is stressed Unfair adversary → Daymude et al. 2021
  1. Set-up. The sources are roots. Every other particle picks a neighbour that is already in a tree as its parent, so the system becomes a forest of trees hanging from the sources.
  2. Signal. A stressed particle raises a 'stress' flag. A particle with a stressed child raises its flag too, so the signal climbs to the root.
  3. Inhibit. A root that hears of stress raises an 'inhibit' flag, which spreads down its whole tree: inhibited particles stop spending energy on their own actions.
  4. Share. Roots harvest energy; any particle with enough energy passes some to a child whose battery is not full.
  5. Use. A particle that is not inhibited and has enough energy performs its next action. Flags are cleared when the stress is gone.
Why it works and what it costs. Energy flows down the trees like water through pipes, and the inhibit signal stops particles near the source from using everything before it reaches the far ends. Daymude et al. 2021 prove that no particle stays stressed for more than \(O(n)\) rounds; without the inhibit step, their simulations show particles staying stressed forever. With a constant number of sources this is optimal, by the next idea. Weber et al. 2023 show how to run any algorithm designed without energy limits on top of this: one that needs \(T\) rounds then needs \(O(n^2\,T)\) rounds.

Why it matters. It was the first model of energy as a limited resource in programmable matter, and the stress/inhibit signals are modelled on how bacterial biofilms share nutrients.

2Lower boundEnergy enters only through the sources Unfair adversary → Daymude et al. 2021

Start with every battery empty and every particle needing a full battery. Then the system needs \(n\) full batteries' worth of energy in total. Energy enters only at the \(s\) sources, and each source harvests at most a fixed amount per activation. An unkind scheduler activates each source only once per round.

Why it holds. So at most a constant times \(s\) units of energy enter per round, and filling \(n\) batteries takes at least a constant times \(n/s\) rounds: \(\Omega(n/s)\) Daymude et al. 2021 (Theorem 9). With a constant number of sources this matches the \(O(n)\) algorithm; with many sources there is a gap of a factor \(s\) between \(n/s\) and \(n\) that has not been closed.

Why it matters. It is a supply argument rather than a distance argument: the bottleneck is how fast energy can enter, not how far it must travel.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Unfair adversary standard
Energy 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.
polynomial gap \(O(n)\) vs \(\Omega(n/s)\) distance

What the community started looking at

Energy distribution was inspired by biofilms Daymude et al. 2021; the later question was a general transformation of energy-agnostic algorithms and its overhead under unfair adversaries Weber et al. 2023.

All settings

The assumption tree (1 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Memory › Scheduler › Orientation › Randomness › Initial shape › Connectivity during execution.

tight near-optimal polynomial gap unknown impossible no variant

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.