2
$\begingroup$

I'm going through Brewer's theorem and its proof by Nancy Lynch and Seth Gilbert. But the paper left me with one question. What prevents the theorem from being applicable to a single node?

I haven’t encountered any explicit definition of network partition that restricts its applicability to a network. There are some hints in [1] that suggest that a network partition with a single node would mean cutting off all communication to that node itself. This doesn’t make a whole lot of sense to me because you could always have a partition with all the service nodes on one side and the client node on the other. No service could possibly tolerate that.

A single node data object can be consistent and available if requests sent to it get through. To me, the definition of a network partition and where it applies leaves something to be desired. What am I missing here?

[1] Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services by Seth Gilbert and Nancy Lynch

$\endgroup$
  • $\begingroup$ IMO, the CAP theorem is applicable specifically to distributed systems, like a distributed web service with multiple servers. In this situation, the "network" here refers to the communications among servers (instead of clients or between clients and servers). $\endgroup$ – hengxin Nov 12 '14 at 2:40
2
$\begingroup$

In my opinion, the CAP theorem is applicable intentionally to distributed systems. To quote the article "Perspectives on the CAP Theorem @ IEEE Computer'2012 by Gilbert and Lynch":

Brewer first presented CAP in the context of a Web service implemented by a set of servers distributed over a set of geographically diverse datacenters. Clients issue requests to the service, which sends back responses.

In this context, the "network" in CAP theorem refers to communications among servers (instead of communications among clients or between clients and servers). This can be justified by the following two arguments.

  1. To quote the above article again (with emphasis added):

Unlike the other two requirements, partition tolerance is really a statement about the underlying system rather than the service itself: communication among the servers is unreliable, and the servers can be partitioned into multiple groups that cannot communicate with one another.

  1. In the proof of the CAP theorem in the above article, it says,

Consider an execution in which the servers are partitioned into two disjoint sets: $\{p_1\}$ and $\{ p_2, \ldots, p_n\}$. Some client send a read request to server $p_2$.

The proof followed is based on the communication among the two disjoint sets of servers.

To summarize, CAP theorem (again, it is my own opinion) does not consider the situation in which client nodes and server nodes are partitioned. After all, we can do almost nothing in this bad situation. In other words, CAP theorem assumes that the communications between clients and servers behave well and focuses on the theory and implementation of the distributed service itself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.