Family Shopping List: Offline Sync and Convergence

Family Shopping List: Offline Sync and Convergence

You've joined the team behind Pantry, a shared shopping list that a family keeps on several phones. Phones are offline most of the time (supermarkets, basements, tunnels) and exchange data whenever two of them happen to meet. There is no server in charge: each phone is a replica that applies edits locally and merges with other replicas in whatever order the syncs happen. The one promise Pantry makes is convergence: once every phone has heard from every other phone, they all show exactly the same list. Support says that promise is currently broken, and the roadmap has three more changes queued behind the fix.

Codebase

How your code is run

run(replicas, operations) creates one empty replica per id in replicas (2 to 12 distinct, non-empty strings) and executes operations in order, returning one result per operation. Each operation is [name, *args]. Errors are returned as "error: <code>", never raised.

Edits happen on one replica. A replica learns about edits made on other replicas only through send / sync / converge; nothing else is shared.

• A wrong number of arguments, or an operation that is not a non-empty list starting with a string, returns "error: invalid arguments"; an unknown operation name returns "error: unknown operation". adjust, gc and tombstones return "error: unsupported operation" until you implement them.
• Item names are normalized by names.normalize_item_name: surrounding whitespace removed, every run of whitespace inside the name collapsed to a single space, then lower-cased. A name that is not a string, is empty after that, or is longer than 40 characters is invalid item. " Whole MILK " and "whole milk" are the same item.
• A quantity (qty) is an int from 1 to 99 (booleans and floats are invalid qty).
• An item is on the list at a replica when that replica currently shows it. add on an item that is on the list at that replica is already on list; remove, set_qty, check, uncheck (and adjust) on an item that is not on the list there are not on list.
• list returns one line per item on the list: "[ ] milk x2" (unchecked) or "[x] eggs x12" (checked). Order: unchecked items first, then checked items; inside each group ascending by name in plain string comparison.
• send src dst: dst absorbs everything src knows; src is unchanged. sync a b: a absorbs b, then b absorbs a, then a absorbs b once more (until Part 3 the third step cannot change anything you can observe). converge: with replicas in the order given to run, sync each neighbouring pair going forward (r0,r1, r1,r2, ...), then each pair going backward (r[n-2],r[n-1], ..., r0,r1).
• digest is a fingerprint of what list would return: [number of lines, crc32 of the lines joined by "\n"].
• wall replica seconds is the phone's wall clock, pushed by the app whenever it changes.

Part 1 — Phones disagree after syncing (PANT-412, PANT-418)

Goal: make replicas converge, and keep deleted items deleted.

Support reports: (1) "Mom ticked off the milk and Dad unticked it at the same moment. After syncing, my phone said ticked and Dad's said unticked, and every sync swaps them." (2) "Kid's phone clock is set to 2037 and its edits beat everyone's, even edits made hours later." (3) "We deleted bananas, then someone's old phone synced and they came back."

Today every write is stamped with the phone's wall clock and ties go to whoever merges last. Replace that with a logical clock, and stop deleting by erasing.

Rules

1. Each item name has one register holding either (qty, checked) or *removed*, plus a stamp. Writes: add writes (qty, unchecked); set_qty, check and uncheck write the current value with one field changed; remove writes *removed*. Every write gets a new stamp, even when the value does not change (ticking an already-ticked item still writes). An item is on the list iff its register holds a value.
2. A stamp is (counter, replica id). Each replica's counter starts at 0; a write sets counter = counter + 1 and stamps (counter, replica id). Stamps compare counter first, then replica ids as plain strings ("mom" > "kid" > "dad"). The larger stamp wins; two different writes never share a stamp, so merging gives the same result in either direction.
3. A removal is just another write: *removed* competes with edits by stamp. A removed item stays removed on every replica that merges it, until a later add writes a larger stamp. Re-adding a removed item must work.
4. When a replica absorbs another's state, its counter becomes max(own counter, other's counter), so its next write is stamped after anything it has seen. Do this for every absorb, even when nothing in the other state wins.
5. Wall clocks no longer decide anything. wall is still accepted and validated (the app keeps sending it) but has no effect on any outcome.
6. Item names must be normalized exactly as described above.

Example (replicas = ["mom", "dad"])

[["add", "mom", "Milk", 2],
 ["sync", "mom", "dad"],
 ["check", "mom", "milk"],
 ["uncheck", "dad", "milk"],
 ["sync", "mom", "dad"],
 ["list", "mom"],
 ["list", "dad"]]

returns [true, true, true, true, true, ["[x] milk x2"], ["[x] milk x2"]]: both edits have counter 2, and "mom" > "dad", so Mom's tick wins on both phones.

tests/test_api.py::test_sync_makes_both_phones_agree_even_on_a_tie currently fails.

Part 2 — Add wins over remove (PANT-431)

Goal: removing an item must only remove what the removing phone actually saw. If someone else adds the item at the same time, it stays.

Part 1's removal is "a write that competes by stamp", which has two problems: a remove can wipe out an add it never saw, and a stale edit (set_qty, check) with a larger stamp can undo a remove. Replace the presence part of the design with an observed-remove set; the value register still carries quantity and checked state.

Rules (these replace Part 1 rule 1's "on the list iff the register holds a value" and rule 3)

1. Every successful add creates a tag (replica id, n), where n is the number of successful adds that replica has performed, including this one. Tags are never reused.
2. remove kills exactly the tags the removing replica currently sees alive for that item (they become tombstones). It writes no register and uses no stamp.
3. An item is on the list at a replica iff that replica knows at least one tag for it that is not tombstoned. Absorbing a replica unions both tag sets and both tombstone sets. A dead tag stays dead everywhere; a tag the remover never saw stays alive.
4. add still writes the register (qty, unchecked); set_qty, check, uncheck still write the whole (qty, checked) register by stamp, exactly as in Part 1. A register write never brings an item back: only a new add (a new tag) does. The register is kept even while the item is off the list.
5. A replica that sees two live tags for an item (two phones added it independently) shows the register winner's quantity for now; Part 3 changes that.

Example (replicas = ["mom", "dad", "kid"])

[["add", "kid", "eggs", 6],
 ["sync", "kid", "dad"],
 ["add", "mom", "eggs", 12],
 ["remove", "dad", "eggs"],
 ["sync", "dad", "mom"],
 ["list", "dad"],
 ["list", "mom"]]

returns [true, true, true, true, true, ["[ ] eggs x12"], ["[ ] eggs x12"]]. Dad only saw Kid's tag ("kid", 1) and killed it; Mom's concurrent add ("mom", 1) survives with her register write.

Part 3 — Counters, independent fields, and tombstone collection (PANT-455)

Goal: a product change. (a) Ticking an item and changing its quantity at the same time must keep both. (b) Quantity edits made at the same time must add up instead of one overwriting the other (the app is getting +/- buttons). (c) Tombstones must not pile up forever.

This changes Part 1/2 behaviour: concurrent set_qty calls no longer have a winner, and a register that holds (qty, checked) together is gone.

Rules

1. Independent fields. checked is its own register per item name: (bool, stamp), initially (false, (0, "")), merged by larger stamp as in Part 1. add writes it as false (new stamp); check / uncheck write it (new stamp, even if unchanged) and nothing else. Quantity is no longer a register. From now on only add, check and uncheck write a register and advance the replica's counter; remove, set_qty and adjust do not.
2. Quantity counters. Each live tag owns a PN-counter: for every replica r a total p[r] of increments and a total n[r] of decrements. A tag's value is sum(p) - sum(n). An item's stored quantity is the sum of the values of its live tags. Merging two copies of a counter takes the entrywise maximum of every p[r] and n[r]. A tag created by add with quantity q starts with p[adder] = q. When a tag is tombstoned its counter is discarded, so its quantity leaves the item. Two phones that add the same item independently therefore end up with the sum of both quantities.
3. adjust replica item delta (delta a non-zero int, not a bool; otherwise invalid delta). If the stored quantity at that replica plus delta would be below 1 or above 99, the error is invalid qty and nothing changes. Otherwise the change is applied to the lowest live tag (ordered by replica id as a string, then n): delta > 0 adds to this replica's p, delta < 0 adds -delta to this replica's n.
4. set_qty means adjust by qty - stored quantity at this replica. If that difference is 0 nothing changes (and the result is still true). Two phones that both set_qty the same item at the same time add their differences; that is the intended product behaviour.
5. Display. list shows min(99, max(1, stored quantity)). The stored quantity itself is never clamped: after merging, it can be 0, negative, or above 99, and later edits are relative to it.
6. Events and version vectors. Every successful state-changing operation on a replica r is an *event*: add, remove (one event, however many tags it kills), adjust, set_qty with a non-zero difference, check, uncheck. Its dot is (r, k) where k is the number of events r has performed, including this one. Each replica keeps a version vector vv: vv[q] is how many of q's events it has absorbed. A tombstone remembers the dot of the removal that created it.
7. Acknowledgements. Each replica also keeps, for every *other* replica y, known[y]: the latest version vector of y it has heard about, starting at all zeros. When replica x absorbs replica s: x.vv becomes the entrywise maximum of x.vv and s.vv, and for every other replica y (not x), x.known[y] becomes the entrywise maximum of x.known[y] and s's view of y, where s's view of itself is s.vv and its view of anyone else is s.known[...]. (So knowledge travels through third parties.) x's view of itself is x.vv.
8. gc replica drops every tombstone at that replica whose dot (o, k) satisfies view[o] >= k for every replica's view held there (its own vv and every known[y]), and returns how many were dropped. tombstones replica returns how many tombstones the replica currently stores. Collecting never changes what list shows.
9. A collected tombstone must not come back: when a replica absorbs another's state, it ignores any tombstone whose removal dot its own vv already covered before this absorb (it either still has it or has collected it). Collecting too early is the dangerous direction: a phone that never saw the removal can still hold the tag alive and bring the item back.

Rules from Parts 1 and 2 that still apply: stamps and counter updates (they now order the checked register), tags and tombstones, names, ordering, error codes.

Example 1 (replicas = ["mom", "dad"]): both phones set the quantity from 3 at the same time.

[["add", "mom", "milk", 3],
 ["sync", "mom", "dad"],
 ["set_qty", "mom", "milk", 5],
 ["set_qty", "dad", "milk", 7],
 ["sync", "mom", "dad"],
 ["list", "mom"],
 ["list", "dad"]]

returns [true, true, true, true, true, ["[ ] milk x9"], ["[ ] milk x9"]] (3 + 2 + 4).

Example 2 (replicas = ["mom", "dad", "kid"]): the removal is not acknowledged by Kid, so nothing is collected even though Dad has seen it.

[["add", "mom", "milk", 3],
 ["sync", "mom", "dad"],
 ["sync", "mom", "kid"],
 ["remove", "mom", "milk"],
 ["sync", "mom", "dad"],
 ["gc", "mom"],
 ["check", "kid", "milk"],
 ["sync", "kid", "mom"],
 ["list", "mom"],
 ["gc", "mom"],
 ["tombstones", "mom"],
 ["gc", "dad"],
 ["send", "mom", "dad"],
 ["gc", "dad"],
 ["tombstones", "dad"]]

returns [true, true, true, true, true, 0, true, true, [], 1, 0, 0, true, 1, 0]. Mom's first gc finds nothing because she has no proof that Kid saw the removal. Kid's tick arrives while the tombstone still exists, so the milk stays removed. After the second sync, Mom knows everyone has seen it and collects it. Dad has to learn that from Mom (send) before his gc can collect.

Part 4 — Twelve phones, a year of shopping (PANT-470)

Goal: syncing must scale. Pantry now runs with up to 12 phones and long-lived lists; a sync that copies and re-merges the whole state is far too slow.

["storm", seed, steps] (or ["storm", seed, steps, pool]) feeds a deterministic pseudo-random mix of add, remove, adjust, set_qty, check, uncheck, send and sync operations through the normal dispatcher, so a few operations can stand for tens of thousands of events. The generator in pantry/workload.py is fixed (do not change it); seed is an int >= 0, steps an int in 0..50000, pool an int in 1..1000 (default 240) controls how many distinct item names are used. It returns [applied, rejected]: how many generated operations returned a non-error result and how many returned an "error: ..." string. Bad arguments (a non-int or bool, seed < 0, steps or pool out of range, any other argument count) return "error: invalid arguments".

Rules

1. Everything from Parts 1 to 3 must behave exactly the same: same lists, same digests, same gc and tombstones numbers. A change that makes things faster but moves any observable result is wrong.
2. The cost of send and sync must be proportional to what the receiver has not seen yet, not to the total size of the list and its history. Hidden tests run tens of thousands of generated steps across up to 12 replicas inside a single run, with several converge calls, and the whole suite has a few seconds. Snapshotting and re-merging every item on every exchange will time out.
3. Replicas relay: a replica forwards what it learned from third parties too, not just its own edits. After converge every replica must have the same digest.
4. gc and tombstones are still exact and per replica (Part 3 rules 7 to 9).

Notes

• names.py, render.py, workload.py and errors.py only need small changes, if any.
• You may use the AI assistant freely; you are expected to verify what it produces.
• Later parts must not break earlier ones; hidden tests re-check earlier behaviour after the later rules are in place, and a scenario never depends on rules a Part has not introduced yet.
• Parts 1 to 3 are a strong result. Part 4 is a stretch.