2013hotsdn - CAP works.pdf.pdf

CAP works Aurojit Panda ? Colin Scott ? Ali Ghodsi ?? Teemu Koponen \ Scott Shenker ???UC Berkeley ?KTH/Royal Institute of Technology \VMware ?ICSI Alice laughed. “There’s no use trying,” she said: “one can’t believe impossible things.”“I daresay you haven’t had much practice,” said the Queen. “When I was your age, I always did it for half-an-hour a day. Why, sometimes I’ve believed as many as six impossible things before breakfast.”(Lewis Caroll) ABSTRACT The CAP theorem showed that it is impossible for datastore systems to achieve all three of strong consistency, availability and partition tolerance. In this paper we investigate how these trade-o?s apply to software-works. Speci?- cally, we work policies such as tenant isolation and middlebox traversal, and prove that it is impossible for implementations to enforce them without sacri?cing availability. We conclude by distilling practical design lessons from our observations. Categories and Subject Descriptors [Distributed Systems]: Network operating systems Keywords Software work, Distributed Controllers, Correct- ness, Availability 1. INTRODUCTION In his famous PODC keynote [5], Eric Brewer artic- ulated the CAP conjecture, a fundamental trade-o? be- tween linearizability, 1availability and partition tolerance 1Brewer’s original talk referred to consistency, without specifying a particular form of consistency. Howeve