The Keighley projectLeader election: 2,234 agents, 2,594 links, no boss
Each agent knows only its own number and its neighbours. The aim is for all of them to name the same leader.
The learner downloads the roads in a box around Keighley with one Overpass request and keeps the largest connected network, 232.0 km long. An agent is placed wherever roads meet or stop, which gives 2,234 agents joined by 2,594 links. Every agent is handed a different random ID. The rule is short. Each agent starts out believing its own ID is the highest. In every round, any agent whose belief has just changed tells its neighbours the highest ID it knows. An agent that hears a higher one adopts it. When a round passes in silence, the election is over and the highest ID has won.
Five hundred elections on the Keighley network, each with freshly shuffled IDs (our Python simulation)| Measure | Lowest | Median | Highest |
|---|
| Rounds until silence | 60 | 76.5 | 116 |
| Messages sent | 32,669 | 37,681 | 51,068 |
Nothing in the rule mentions the map, yet the map sets the speed. News of the winner travels one link per round, so the election lasts as long as the winner's distance, counted in links, to the agent furthest from it. For this network that distance ranges from 58, its radius, to 115, its diameter, and one more silent round confirms the result. The cost is modest. A median of 37,681 messages elects a leader, where every agent contacting every other directly would take 4,988,522 and would need each one to hold the address of all the rest.
What happens if agents stop listening too soon: share of agents that have not yet heard of the true leader, averaged over the 500 elections| Agents stop after | Share still wrong | Elections left unfinished |
|---|
| 30 rounds | 57.1% | 500 of 500 |
| 50 rounds | 19.9% | 500 of 500 |
| 60 rounds | 10.0% | 494 of 500 |
| 70 rounds | 4.6% | 338 of 500 |
This is the first trap. An agent that has heard nothing new for a while cannot tell "finished" from "the news has not reached me yet". A timeout chosen by guesswork, such as 50 rounds, leaves a fifth of the agents following leaders that lost. The second trap is a broken link. In this network 1,095 of the 2,594 links are bridges, meaning no other route goes round them. Most are harmless: 801 lead only to a dead end. But 16 would each cut off 50 agents or more, and the worst separates 255 agents from the other 1,979. We removed that link and ran the election again. It ended calmly with two leaders, each group certain it had the only one. Engineers call that split brain. The usual cure is to let a leader act only when more than half of all agents stand behind it, which 1,979 can show and 255 cannot.
Ages 8 to 11
Pupils in a line whisper the highest number they have heard. Count the whispers, then cut the line in the middle.
Ages 11 to 15
Simulate the election in Python on a small hand-drawn network and time it from different starting IDs.
Ages 15 and up
Load the real street graph, measure its diameter, find the bridges and add a majority rule.
Data and honesty notes
Road data © OpenStreetMap contributors, licensed under the Open Database Licence. The agents, the rule and all counts come from our own simulation. No real device sits on any junction. The network is cut at the edge of our box, and a larger box would change the radius, the diameter and the bridges.
