Round-Robin Talk for Tiny Devices: CHIRP and S-CHIRP

Press Next round a few times. In each round the devices pair off, and the bold lines show who is talking right now; thin lines are conversations already finished. After eight rounds, all 28 pairs of eight devices have talked. Now tap two devices to take them out, as if their batteries died, and press Start over: the rest still meet each other, and the devices that would have talked to a missing one simply wait that round.

Try the rule by hand with eight devices in round 3. Device 1 computes 3 − 1 = 2, so it talks to device 2; device 2 computes 3 − 2 = 1, so it agrees. Device 5 computes 3 − 5 = −2, and the remainder of −2 after dividing by 8 is 6, so device 5 talks to device 6. A shortcut falls out of the rule: devices a and b meet in the round equal to (a + b) mod n. Every pair has exactly one such round, so every pair meets exactly once per cycle. With n devices, the cycle takes n rounds.

A round can hold at most ⌊n/2⌋ disjoint pairs, so building all n(n − 1)/2 edges needs at least n − 1 rounds for even n and n for odd n (Eq. 1). CHIRP settles on n rounds in every case, and the extra round is a feature: each node pairs with itself exactly once per cycle, a built-in checkpoint the paper suggests for resets or internal work. Missing nodes do not break the schedule. A node whose computed partner is absent idles for that round, and each present node idles in exactly Node_cnt − Node_actual rounds per cycle, the loss Eq. 3 predicts.

Each round r is the matching {s, r − s}; for odd n one node is fixed, and for even n rounds of even r fix two nodes (r/2 and r/2 + n/2) while odd rounds are perfect matchings. The paper states that each round holds at least (n − 1)/2 pairs; for even n the even rounds hold n/2 − 1, so the bound holds as ⌊(n − 1)/2⌋. The page checks the full cycle for every n from 2 to 64: each of the n(n − 1)/2 pairs appears exactly once, each node self-pairs once, and for random sets of missing nodes the measured idle fraction equals Eq. 3 exactly.

A device that wakes up or arrives late does not know which round the group is on. It does not need to ask. The first device that calls it gives away the answer, because the caller’s number plus the newcomer’s own number points straight at the round. The newcomer checks a few more callers to be sure the rounds count up the way they should, then joins in.

Turning the rule around gives the round: if device t calls device s, then the round is (t + s) mod n (Eq. 4). In the paper’s example, device 4 rejoins an eight-device group. It hears from device 0, then 1, 2, and 3, then nobody (its own checkpoint), then 5, 6, and 7. Adding 4 to each and taking the remainder after dividing by 8 gives rounds 4, 5, 6, 7, 0, 1, 2, and 3, which count up in order. Press Join at a random moment to drop in somewhere else.

Re-entry requires Node_actual < Node_cnt and an unused index; the round then follows from any inbound contact. The left table is the paper’s Table I with the newcomer’s column masked; the right is Table II. Validating several consecutive contacts, as the paper suggests, guards against a single spoofed or mistaken contact, and the same idea lets a node detect an index collision: if its inbound contacts do not produce consecutive rounds, its own index is wrong. Under S-CHIRP, Eq. 4 yields Pr(C)[r] rather than r, so a newcomer also needs the network’s permutation to place itself in the cycle.

Plain CHIRP is predictable: once you see one round, you know every round that follows. S-CHIRP keeps the same rule but plays the rounds in a secret order that only members of the group know. Everyone still meets everyone once per cycle. An outsider listening in, though, can no longer tell who will talk next, and a device that calls at the wrong moment stands out.

Compare the two settings. In order, the shaded cells (rounds in which someone talks to device 0) run down a diagonal line. Shuffled, they scatter. The number of possible orders is n! (n factorial: 8 × 7 × 6 × … × 1). Eight devices already have 40,320 orders, and 128 devices have more orders than there are atoms in the observable universe. Storing the chosen order takes very little room: one number per round.

S-CHIRP changes one term: target = (Pr(C)[r] − self) mod Node_cnt (Eq. 6). Because Pr(C) is a bijection on the cycle, each round is still a valid matching and each edge still appears once per cycle; only the order changes. The paper offers two ways to share Pr(C): a seeded Fisher–Yates shuffle computed on each device (O(n) time, in place, but every device must run the same random number generator), or a permutation built off-device and stored, at 4n bytes with 32-bit indices (40 KB for 10,000 nodes, 4 MB for a million). A footnote adds Sattolo’s algorithm, which draws only single n-cycles.

The paper argues that a permuted cycle “requires immense resources to track, detect and exploit,” and lists the per-network permutation as the mechanism that lets nodes detect rogue communication. This page quantifies one side of that claim with its own analysis. A receiver can check a caller with (caller + self) mod n = Pr(C)[r]; that check rejects a rogue that does not know the current round value. The same equation also means one overheard pair reveals that round’s value, so the protection against an eavesdropper is forward-looking: after k observed rounds of a cycle the next value is uniform over the n − k unused values, and a permutation reused unchanged across cycles is fully exposed after one cycle. Re-seeding per cycle, which the paper’s seeded shuffle makes cheap, removes the second weakness.

Neighbors run their own device groups, and those groups often share the same airwaves. If two groups count their rounds the same way, their devices can end up talking to the wrong neighbor’s devices. The Potentials article suggests a fix: give each group a different prime number of slots (a prime divides only by itself and one), even if that leaves a few slots empty. Press Figs. 4 and 5, then Fig. 6, and watch how much less often the two groups fall into step.

Each colored box marks the round where a group starts a new cycle. With four and two devices, group B’s cycle fits exactly twice into group A’s, so the two start together every four rounds, and in half of all rounds the two groups sit at the same step of their cycles. Giving the groups five and three slots instead makes the cycles line up only once every 15 rounds, the least common multiple of 5 and 3. The cost: the extra slots are empty, so some devices spend rounds calling nobody.

Identifiers are assigned within each clique, so device 1 of clique A and device 1 of clique B answer to the same index on a shared medium. When two cliques use the same Node_cnt, or counts that divide one another, their schedules coincide in many rounds and cross-clique exchanges recur on a short period. The article’s remedy pads each clique’s count to a distinct prime, which pushes full alignment out to lcm(p₁, p₂) = p₁p₂ rounds at the price of inactive exchanges toward empty slots. The table counts each kind of exchange over one joint period under this page’s event rules.

Computed by this page, not reported in the article: for the example cliques of four and two devices, distinct prime counts cut invalid cross-clique pairs from 0.50 to 0.27 per round and collisions from 1.00 to 0.80, while adding 1.47 inactive attempts per round and lowering valid pairs from 2.00 to 1.53. The fraction of rounds with at least one cross-clique event rises from 2 of 4 to 10 of 15, so prime counts make cross-clique contact less regular and less frequent per round without eliminating it, consistent with the article’s caution that overlap persists at the least common multiple. S-CHIRP’s per-clique permutations address the remaining exposure from a different direction.

• Any number of devices can all talk to one another, one pair at a time, in as many rounds as there are devices, using a rule small enough for the cheapest chip.
• The group keeps working when devices disappear and lets them rejoin without asking anyone for help.
• Playing the rounds in a secret order turns the schedule into a password that outsiders cannot easily guess.
• Neighboring groups on the same channel step on each other less when their sizes are distinct prime numbers.

• One formula, partner = (round − my number) mod n, gives every device its partner with no central controller.
• n devices need only n rounds, and every device gets one free round per cycle to check itself.
• With 64 devices, the number of possible secret round orders passes 10⁸⁹; storing one order for a million devices takes about 4 MB.
• Groups of four and two devices fall into step every four rounds; padding them to five and three slots stretches that to every 15.

• Complete exchange in n rounds. Eq. 2 yields a complete graph of n(n − 1)/2 edges in n rounds, one round above the lower bound for even n (Eq. 1, Figs. 1 to 3).
• Graceful loss and re-entry. Efficiency falls linearly with missing nodes (Eq. 3, Fig. 4), and a returning node recovers the round from inbound indices (Eq. 4, Tables I and II).
• Keyed schedules. A shared cycle permutation preserves every property above and draws from n! schedules (Eq. 6, Tables III and IV); storage is 4n bytes, within 10 MB at a million nodes.
• Collocated cliques. Overlapping identifiers produce valid, invalid, colliding, and inactive exchanges; distinct prime device counts delay cycle alignment to the least common multiple (Potentials, Figs. 3 to 6).
• Limits. The articles name changing populations, the security of the non-keyed protocol, and conflicts with already busy devices as open problems, and leave multi-agent simulation to future work.

Swarms of tiny devices (crop sensors, delivery drones, pill-sized medical sensors, and smart-home gadgets) often have no server, little memory, and no reliable map of who is nearby. CHIRP gives them a way to share everything with everyone using three numbers and one line of arithmetic, and S-CHIRP adds a secret that keeps outsiders guessing. Ultimately, the simpler the rule, the more kinds of devices can follow it, from radios to blinking lights to sound.

Most IoT security work builds on addressing and key distribution schemes that assume a stable topology. CHIRP assumes almost nothing: no routing tables, no leader, and no knowledge of the network beyond its maximum size, which suits ephemeral, heterogeneous swarms where nodes are lost, replaced, or moved. Because the schedule is independent of the physical medium, the same protocol can run over radio, visible light, or sound in a contested electromagnetic environment, and it leaves room to layer existing key-sharing and encryption on top.

The contribution is a schedule with provable coverage, constant per-node state, and O(1) computation per round, which makes keyed communication patterns affordable on devices that cannot run a routing protocol. Its security rests on the secrecy of the permutation and on per-round validation of callers; the papers do not evaluate an active adversary, and the event analysis above suggests that clique separation by device counts alone reduces, rather than removes, cross-clique contact.

Notes from building this page

• Table IV is one round value behind Eq. 6. With Pr(C) = [7, 5, 2, 0, 4, 6, 1, 3], all 64 printed cells equal (Pr(C)[r] − 1 − self) mod 8, and none equals Eq. 6 as written. The text’s “simple 5 round offset, C = [5, 6, 7, 0, 1, 2, 3]” lists seven values and starts one above Table I’s first row, which Eq. 2 places at r = 4. Both point to a one-based round counter in the code that produced the tables. The Potentials article numbers rounds from 1, and its figures match Eq. 2 with r = round − 1. The page uses Eq. 6 as printed.
• Table III. The 8-node row should read 4.03 × 10⁴ (8! = 40,320). The other five rows match to three figures, two of them (64 and 128) by truncation rather than rounding (1.2689 and 3.8562).
• Pairs per round. For even n, rounds with even r hold n/2 − 1 pairs, so the stated minimum of (n − 1)/2 pairs holds as ⌊(n − 1)/2⌋.
• Distinct primes. The article’s rule (“the nearest unique prime number”) is read here as the smallest unused prime greater than the clique’s size, which reproduces its example (four and two become five and three). Sizes that are already prime are padded too under this reading; “nearest” could instead allow a prime size to keep its count.
• Collocated events. The article defines valid, invalid, collision, and inactive exchanges (Fig. 3) without counts. The rules here (shared channel, shared round counter, an index names a device in each clique that has it, collisions counted once per contested index) are this page’s formalization, and the per-round figures in the cliques demo depend on them.
• Eavesdropper analysis. The 1 in (n − k) prediction chance and the observation that one overheard pair reveals Pr(C)[r] are this page’s analysis, not the paper’s.

Try this in class

1. Seat six classmates in a circle, numbered 0 to 5. For rounds 0 through 5, each student computes (round − own number) mod 6 and stands with that partner. Record the pairs and check that every pair of students met exactly once.
2. Take one student out and repeat. Count the rounds each remaining student spends waiting, and compare with (6 − 5) / 6 of the cycle.
3. Write the six round numbers on cards, shuffle them, and replay the cycle in the shuffled order while one student, who has not seen the cards, tries to predict each next pair. Record how often the predictor is right as the cycle goes on.