The event loop
The scheduler is a queue of timed events: each robot's next LOOK or WAIT, a crash, and a periodic Visualize tick. advance() handles them one at a time, in time order, until its budget, a limit or the end. This is Scheduler.handle_event in the original scheduler, ported line by line.
Notes
- Ties in time break exactly as in Python's heap of (time, id, state) tuples: lower robot id first, then Crash < Look < Visualize < Wait.
- Visualize ticks change nothing; they are kept so event counts and limits match the Python.
- The run ends when every robot that is neither crashed nor Byzantine has terminated.
- Under the sequential scheduler robots have no clocks of their own: only one Look is ever in the queue, and the next one is queued when a turn ends (chart 5).
One Look–Compute–Move cycle
The robot takes a snapshot (LOOK), its algorithm computes a target (COMPUTE), and it moves there (MOVE); a WAIT event at the arrival time ends the move. Faults, freezing and termination all branch off this path. This is Robot.look, Robot.move and Robot.wait in the original simulator.
Notes
- The snapshot is taken at the exact LOOK time: moving robots are seen at their interpolated position, never a stale one.
- A robot freezes (stays put this cycle) when its target is within ε = 10^-precision of where it is, or when an omission fault skips the move (probability ½).
- Rigid movement always reaches the target. Non-rigid movement does too (finding #3 in report.md) unless a minimum move δ is set: then the robot may be stopped on the way, never before it has covered δ, and the WAIT event is scheduled at the stopping point (chart 5).
Gathering (center of gravity)
Each robot moves to the average position of the robots it sees. Repeated asynchronously, the swarm converges to a single point. This is Robot._midpoint and Robot._midpoint_terminal in the original simulator.
Notes
- The average includes crashed robots, but the termination test ignores them: the original's behaviour, kept on purpose (finding #4 in report.md).
- The sum is a plain left-to-right loop, as in the Python, so results match to the last digits.
- Only guaranteed to gather with unlimited visibility. With a limited radius the swarm can stop in several separate groups, all marked terminated: a robot that sees nobody terminates (the original's rule, chart 2), and moving to the average can break visibility links. Algorithms built for limited visibility, such as Go-To-Center (Ando et al.), limit the step length to keep them.
In the browser
The page never runs the simulation itself. A Web Worker owns the Rust core and simulates in short slices at the chosen playback speed; the page asks for the latest frame whenever it is ready to draw, so drawing never slows the simulation.
Notes
- Frames travel as typed arrays that are transferred, not copied or turned into JSON; the page hands each frame's arrays back to be refilled, so playback allocates nothing per frame.
- The worker computes in ~6 ms slices and yields between them, so messages (frame requests, pause, speed changes) get through immediately.
The sequential scheduler
Under the sequential scheduler only one robot's Look is ever waiting in the queue. When its turn ends, next_turn() decides who goes next, and the others stay still until then. This is the sequential scheduler of Section 2.2 of "Universal pattern formation by oblivious robots under sequential schedulers" (arXiv:2412.10733); it is new in the Rust core, not in the Python original.
Notes
- Round-robin and the shuffle each epoch both give every robot that is still active exactly one turn per epoch. An explicit list of turns ends its epoch once every robot has had at least one, as in the paper.
- Crashed and terminated robots are skipped. The paper has no crashes; this is the simulator's own rule.
- Stalled is not in the paper either. Robots are deterministic and remember nothing, so if a whole epoch changes nothing, every later epoch is the same and the run can never end. It is not checked with faults, because an omission fault skips moves at random.
- A run can also end at a turn limit (max_turns): the last turn's move still finishes. It says nothing about the algorithm, only that the budget ran out.
- With non-rigid movement, a robot whose destination is within δ always arrives; otherwise the adversary stops it somewhere at least δ along its way. δ is not shown to the algorithms: in the paper, the robots do not know it.
SqGathering (Algorithm 8)
Algorithm 8 of "Universal pattern formation by oblivious robots under sequential schedulers" (arXiv:2412.10733, Section 6). The active robot sees each occupied point only as single or multiplicity, counts the multiplicities κ, and follows one of three rules. It runs only under the sequential scheduler of chart 5: the registry refuses the async one.
Notes
- Weak multiplicity detection: one bit per point, never a count. Two robots on a point and five robots on a point look the same.
- Why the sequential scheduler: without multiplicity detection Gathering is unsolvable under any sequential scheduler (Theorem 4); with more than one robot active at once it is unsolvable even with detection (Lemma 8). So SqGathering refuses the async scheduler, limited visibility and faults.
- In the paper robots never terminate. Here a robot that sees a single occupied point terminates: everyone is there, and every robot activated later would stay, so it changes nothing and lets the run end.
- Points closer than ε (10^-precision) are one point. Equally close points are told apart by their coordinates; any fixed choice is allowed.
- A move cut short after δ can stop on a single robot and make a second multiplicity; the κ > 1 rule then separates them again.
- With several large multiplicities, each robot leaving one halves the distance of the robot that left before it. After enough of them it is closer than ε, cannot leave, and the run ends Stalled (chart 5): a precision limit, not a flaw of the algorithm.
Go-To-Center
Each robot heads for the centre of the smallest circle around the robots it sees, but never so far that it could lose sight of a neighbour. This is Robot._go_to_center and Robot._gtc_terminal in the original simulator, from Ando, Oasa, Suzuki and Yamashita (1999). With limited visibility it keeps a swarm that starts connected together, which simple centre-of-gravity gathering does not.
Notes
- The limit: for each visible neighbour j, the destination must stay inside the disc of radius V/2 around the midpoint of the robot and j. Both robots then stay within V of each other whatever else happens. The step is the farthest point of the way to the centre that is inside all of these discs.
- A robot stopped part-way by non-rigid movement is still on that segment, inside every disc, so no link is lost either. Robots that start within sight of each other stay within sight in all the runs tested, under the sequential and the asynchronous scheduler.
- The smallest circle is the same randomized routine as SEC's, run for every group of two or more robots, so it draws the same random numbers as the Python and the runs match event by event.
- A robot is done when the circle around what it sees has a radius below ε. Under the sequential scheduler this can deadlock: the robots that define the circle have stopped, the rest are within ε of its centre so they do not move, and the radius is just above ε, so nobody finishes. About 7 in 100 sequential runs of 8 robots do this at the default precision; the swarm is then within 0.00002 of one point and the core ends the run as Stalled. The original Python, which only ran asynchronously, finished all 139 of the same starts.