CAP for Networks

TitleCAP for Networks
Publication TypeConference Paper
Year of Publication2013
AuthorsPanda A, Scott C, Ghodsi A, Koponen T, Shenker S
Other Numbers3429

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-os apply to software-defined networks. Specifically, we investigate network policies such as tenant isolation and middlebox traversal, and prove that it is impossible for implementations to enforce them without sacrificing availability. We conclude by distilling practical design lessons from our observations.


We thank Shivaram Venkataraman, Kay Ousterhout,Peter Bailis, and Amin Tootoonchian for their feedbackand suggestions. This research is supported by NSF grants CNS-1040838 and CNS-1015459.. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the National Science Foundation.

Bibliographic Notes

Proceedings of ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking (HotSDN '13), pp.91-96, Hong Kong, China

Abbreviated Authors

A. Panda, C. Scott, A. Ghodsi, T. Koponen and S. Shenker

ICSI Research Group

Networking and Security

ICSI Publication Type

Article in conference proceedings