tag:blogger.com,1999:blog-8899645800948009496.post4800003712758047173..comments2024-03-27T21:57:04.787-07:00Comments on DBMS Musings: IEEE Computer issue on the CAP TheoremDaniel Abadihttp://www.blogger.com/profile/16753133043157018521noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-8899645800948009496.post-23417483021936884242016-08-14T19:17:19.821-07:002016-08-14T19:17:19.821-07:00Link fixed.Link fixed.Daniel Abadihttps://www.blogger.com/profile/16753133043157018521noreply@blogger.comtag:blogger.com,1999:blog-8899645800948009496.post-45132917355228783032016-07-23T13:36:38.168-07:002016-07-23T13:36:38.168-07:00Hi, the link for the Birdman article (5th?) doesn&...Hi, the link for the Birdman article (5th?) doesn't seem to be valid: http://dfreedman.cs.cornell.edu/IEEE_Computer_45_50.pdf<br />What is the title of that article, by chance?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8899645800948009496.post-87214743043756168642012-11-19T14:18:49.247-08:002012-11-19T14:18:49.247-08:00Mark, thanks for the kind words. Your question abo...Mark, thanks for the kind words. Your question about R+W > N implying consistency is a common misconception, so I'm glad you brought it up.<br /><br />In their proof of CAP, Seth Gilbert and Nancy Lynch used the definition of atomic/linearizable consistency: “There must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time.”<br /><br />When you have R+W > N, all that is guaranteed is that reads return at least the latest complete write. However, this is weaker than the definition of consistency given above.<br /><br />For example, suppose you have 3 replicas A, B and C, and both R and W are equal to 2 (so 2+2 > 3). Let's say that a write is sent to A and B and A has completed the write while B is delayed before completing the write. Now a read comes and is sent to A and C. A has the more recent value, so this new value is returned (even though the write that resulted in this value has not yet "committed"). Now, another read comes and goes to B and C. Since neither one has the new value, the old value is read. If the two reads would execute on the same single server this would be impossible since the second read started after the first one completed.<br /><br />Of course, it is possible to guarantee higher levels of consistency in quorum systems, but just R+W >= N by itself is not sufficient to guarantee consistency.Daniel Abadihttps://www.blogger.com/profile/16753133043157018521noreply@blogger.comtag:blogger.com,1999:blog-8899645800948009496.post-30936535778703599082012-11-14T15:15:21.682-08:002012-11-14T15:15:21.682-08:00For some reason I didn't get PACELC when readi...For some reason I didn't get PACELC when reading your original blog post. I read the paper today and now I get it. Thanks for removing a lot of the confusion from future CAP discussions by explaining the source of the confusion and introducing PACELC.<br /><br />Can you provide more details on why "R+W >= N" isn't sufficient to provide C as defined by Gilbert and Lynch?Mark Callaghanhttps://www.blogger.com/profile/09590445221922043181noreply@blogger.com