systems
The shopping cart that must not vanish
It is 2006 in Seattle, and an online retailer has learned its most expensive lesson at peak traffic: a strongly consistent database that pauses during a partition costs millions per minute of checkout downtime, while a customer whose cart flickers empty simply leaves. Design a storage system spanning hundreds of machines that stays writable through node failures and network partitions — accepting that replicas will temporarily disagree — and then reconcile the divergence honestly: versioning that detects conflicts, merge rules that never silently lose an item, and an explicit statement of what consistency the application actually gets. Get the trade-off wrong in either direction and you have built the pause that empties the store, or the merge that quietly loses the customer's order.
Who this problem belongs to
The two figures whose methods fit it best, out of 34 in contention.
Lamport's rigorous theoretical foundations for distributed systems, causal ordering, and his broader work characterizing what consistency guarantees are and are not achievable when a system must remain available during network partitions, are the direct intellectual ancestors of this problem's actual engineering challenge. His 1978 causal-ordering paper and his subsequent work on Byzantine-fault-tolerant and replicated systems established the vocabulary, versioning, conflict detection, and explicit consistency tradeoffs, that Amazon's engineers drew on directly when building Dynamo, the real 2006 system this problem describes. His formal-methods tools remain the standard way to specify exactly what guarantees a highly available, partition-tolerant storage system actually provides. He did not build Dynamo itself, which is the only reason his score stops short of the very top.
Liskov's research on Byzantine fault tolerance and her earlier work on Argus, a programming language and runtime built specifically for distributed, replicated transactions that must tolerate node failures, engages precisely this problem's technical core: how to keep a distributed data store both available and eventually correct when replicas can disagree. Her rigorous approach to specifying exactly what consistency guarantees a replicated system provides, rather than leaving it vague, is exactly the discipline this problem's 'explicit statement of what consistency the application actually gets' demands. Her practical fault-tolerance systems work predates Dynamo by roughly a decade and directly influenced the following generation of engineers who built exactly this kind of highly available storage system, keeping her a close second to Lamport's foundational theory.
Fought here
34 figures are scored on this problem. Draw it in a battle to see where you land.