Brewer’s cap theorem

On Friday 4th June 1976, in a small upstairs room away from the main concert auditorium, the Sex Pistols kicked off their first gig at Manchester’s Lesser Free Trade Hall. There’s some confusion as to who exactly was there in the audience that night, partly because there was another concert just six weeks later, but mostly because it’s considered to be a gig that changed western music culture forever. So iconic and important has that appearance become that David Nolan wrote a book, I Swear I Was There: The Gig That Changed the World, investigating just whose claim to have been present was justified. Because the 4th of June is generally considered to be the genesis of punk rock.

Prior to this (in fact since around 1971) there had been a number of protopunk bands, such as the New York Dolls and the Velvet Underground, but it was this one set by the Sex Pistols that in music folklore started the revolution that set in motion the driving guitars of the Buzzcocks, the plaintive wailing of The Smiths, the eclectic syncopations of the The Fall, the rising majesty of Joy Division and Simply Red (I guess you can’t have everything).

Wednesday 19th July 2000, may not go down in popular culture with quite the same magnitude but it’s had a similar impact on internet scale business as the Sex Pistols did on music a quarter of a century earlier, for that was the keynote speechby Eric Brewer at the ACM Symposium on the Principles of Distributed Computing (PODC).

The Sex Pistols had shown that barely-constrained fury was more important to their contemporaries than art-school structuralism, giving anyone with three chords and something to say permission to start a band. Eric Brewer, in what became known as Brewer’s Conjecture, said that as applications become more web-based we should stop worrying about data consistency, because if we want high availability in these new distributed applications, then guaranteed consistency of

data is something we cannot have, thus giving anyone with three servers and a keen eye for customer experience permission to start an internet scale business. Disciples of Brewer (present that day or later converts) include the likes of Amazon, EBay, and Twitter.

Two years later, in 2002, Seth Gilbert and Nancy Lynch of MIT, formally provedBrewer to be correct and thus Brewer’s Theorem was born.

Brewer’s (CAP) Theorem

So what exactly is Brewer’s Theorem, and why does it warrant comparison with a 1976 punk gig in Manchester?

Brewer’s 2000 talk was based on his theoretical work at UC Berkley and observations from running Inktomi, though Brewer and others were talking about trade-off decisions that need to be made in highly scalable systems years before that (e. g. “Cluster-Based Scalable Network Services” from SOSP in 1997 and “Harvest, yield, and scalable tolerant systems” in 1999) so the contents of the presentation weren’t new and, like many of these ideas, they were the work of many smart people (as I am sure Brewer himself would be quick to point out).

What he said was there are three core systemic requirements that exist in a special relationship when it comes to designing and deploying applications in a distributed environment (he was talking specifically about the web but so many corporate businesses are multi-site/multi-country these days that the effects could equally apply to your data-centre/LAN/WAN arrangement).

The three requirements are: Consistency, Availability and Partition Tolerance, giving Brewer’s Theorem its other name – CAP.