Wait-free atomic snapshot

Write codeHard35 min

Your task

Implement a wait-free atomic snapshot of an array of counters using the classic double-collect technique. You are given M counters (initially all 0) and a list of events. Each event is either ['inc', i] (counter i increments by 1) or ['snap'] (a reader attempts to take a snapshot). Model the reader's wait-free scan as: take a 'collect' of all counters, take a second 'collect'; if the two collects are identical, that is the snapshot. Otherwise, between the two collects exactly one inc happened (events are sequential), so RETRY by collecting again until two consecutive collects match. Since events are sequential, a 'snap' event sees no concurrent change and the first double-collect always matches. Return the list of snapshots (each a list of M ints) in the order 'snap' events occur.

Examples

atomic_snapshots(m: int, events: list[list]) -> list[list[int]]
Example 1
Inputatomic_snapshots(2, [["inc", 0], ["snap"], ["inc", 1], ["snap"]])
Output[[1, 0], [1, 1]]