2 posts tagged with "CAS"

Distributed coordination requires locks, leader election, and consistent configuration. The standard approach: deploy etcd, ZooKeeper, or provision a DynamoDB table with conditional expressions. Teams treat S3 as file storage.

Object stores now support consensus primitives.

Google Cloud Storage (GCS) has supported conditional writes via generation-match preconditions since its early releases. Azure Blob Storage has supported If-Match / If-None-Match on ETags for the same duration. S3 was the last to adopt. In May 2024, materializedview.io identified the gap: "S3 has no compare-and-swap operation, something every single other competitor has."

S3 closed the gap in two releases. If-None-Match shipped in August 2024. Full If-Match Compare-And-Swap (CAS) shipped in November 2024. AWS described the feature as "reliably offloading compare and swap operations to S3."

All three major object stores now support CAS. Herlihy proved in 1991 that CAS is a universal primitive: the single operation sufficient to build any concurrent data structure, wait-free.

Every major object store provides a universal coordination primitive. Most teams have not recognized this.

This blog post is inspired by the first 6 chapters of The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit.

Imagine building a distributed counter that must handle millions of updates per second across dozens of threads. Traditional locks serialize access, creating bottlenecks. You need something better: a way for threads to coordinate without blocking, without deadlocks, without the performance collapse that comes with contention. This isn't just a performance optimization problem; it's a fundamental question about what synchronization primitives are actually necessary. Can we build wait-free concurrent data structures? Which hardware instructions must processors provide? The answer, discovered through decades of theoretical work, reveals that one primitive, Compare-And-Swap (CAS), is universal.