Bitcoin Forum
December 02, 2016, 10:38:15 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Why doesn't the CAP theorem kill BitCoin?  (Read 6053 times)
jabowery
Newbie
*
Offline Offline

Activity: 15


View Profile
May 22, 2011, 08:58:46 PM
 #1

CAP theorem
From Wikipedia, the free encyclopedia

The CAP theorem, also known as Brewer's theorem, states that it is impossible for a distributed computer system to simultaneously provide all three of the following guarantees:[1][2]

Consistency (all nodes see the same data at the same time)
Availability (node failures do not prevent survivors from continuing to operate)
Partition tolerance (the system continues to operate despite arbitrary message loss)
According to the theorem, a distributed system can satisfy any two of these guarantees at the same time, but not all three.[3]

History
The theorem began as a conjecture made by University of California, Berkeley computer scientist Eric Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC).[4] In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's conjecture, establishing it as a theorem.[1]

References
[1] a b Nancy Lynch and Seth Gilbert, “Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services”, ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59.
[2] "Brewer's CAP Theorem", julianbrowne.com, Retrieved 02-Mar-2010
[3] "Brewers CAP theorem on distributed systems", royans.net
[4] Eric Brewer, "Towards Robust Distributed Systems"

External links
"Problems with CAP, and Yahoo's little known NoSQL system" by Daniel Abadi
"CAP equivalent for analytics"


P ≟ NP    This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.
1480718295
Hero Member
*
Offline Offline

Posts: 1480718295

View Profile Personal Message (Offline)

Ignore
1480718295
Reply with quote  #2

1480718295
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480718295
Hero Member
*
Offline Offline

Posts: 1480718295

View Profile Personal Message (Offline)

Ignore
1480718295
Reply with quote  #2

1480718295
Report to moderator
1480718295
Hero Member
*
Offline Offline

Posts: 1480718295

View Profile Personal Message (Offline)

Ignore
1480718295
Reply with quote  #2

1480718295
Report to moderator
1480718295
Hero Member
*
Offline Offline

Posts: 1480718295

View Profile Personal Message (Offline)

Ignore
1480718295
Reply with quote  #2

1480718295
Report to moderator
error
Hero Member
*****
Offline Offline

Activity: 574



View Profile
May 22, 2011, 09:04:20 PM
 #2

Because Bitcoin is designed to deal with it. This is done through occasional block chain reorganizations, most of which happen automatically behind the scenes.

15UFyv6kfWgq83Pp3yhXPr8rknv9m6581W
jabowery
Newbie
*
Offline Offline

Activity: 15


View Profile
May 22, 2011, 09:12:11 PM
 #3

Because Bitcoin is designed to deal with it. This is done through occasional block chain reorganizations, most of which happen automatically behind the scenes.

Doing a web search I find nothing mentioning both BitCoin and the CAP theorem.  Is there a report on this topic somewhere offline?
cuddlefish
Full Member
***
Offline Offline

Activity: 126



View Profile
May 22, 2011, 09:16:30 PM
 #4

Bitcoin doesn't get P.

However, the block chain can fork and be rejoined.

davout
Legendary
*
Offline Offline

Activity: 1358


1davout


View Profile WWW
May 22, 2011, 09:20:49 PM
 #5

Consistency (all nodes see the same data at the same time)
Bitcoin does not guarantee this.

error
Hero Member
*****
Offline Offline

Activity: 574



View Profile
May 22, 2011, 09:25:26 PM
 #6

Because Bitcoin is designed to deal with it. This is done through occasional block chain reorganizations, most of which happen automatically behind the scenes.

Doing a web search I find nothing mentioning both BitCoin and the CAP theorem.  Is there a report on this topic somewhere offline?

Hi. You need to start by reading the Bitcoin paper, especially section 5. Smiley

15UFyv6kfWgq83Pp3yhXPr8rknv9m6581W
martin
Full Member
***
Offline Offline

Activity: 150



View Profile WWW
May 22, 2011, 11:34:21 PM
 #7

Bitcoin doesn't get P.

However, the block chain can fork and be rejoined.

Bitcoin gets Partition Tolerance, davout was right in saying bitcoin doesn't get consistency.

In the event of a partition both halves will continue working separately (and thus the state is inconsistent in those two halves). Then when the two halves connect the partition is sorted out (arguably not in the best way possible, but it does restore the system to a sensible state).

cuddlefish
Full Member
***
Offline Offline

Activity: 126



View Profile
May 22, 2011, 11:35:18 PM
 #8

Bitcoin doesn't get P.

However, the block chain can fork and be rejoined.

Bitcoin gets Partition Tolerance, davout was right in saying bitcoin doesn't get consistency.

In the event of a partition both halves will continue working separately (and thus the state is inconsistent in those two halves). Then when the two halves connect the partition is sorted out (arguably not in the best way possible, but it does restore the system to a sensible state).
I see the p2p network as independent from the block chain.

martin
Full Member
***
Offline Offline

Activity: 150



View Profile WWW
May 22, 2011, 11:41:51 PM
 #9

Well the CAP doesn't really apply to the p2p network since the network doesn't have any state (except the blockchain) :/

davout
Legendary
*
Offline Offline

Activity: 1358


1davout


View Profile WWW
May 23, 2011, 08:37:55 AM
 #10

I see the p2p network as independent from the block chain.
What ?

As I said no consistency is guaranteed by design, so the question of the OP is answered.

"Why doesn't the CAP theorem kill Bitcoin ?" :
1. Because theorems don't kill things
2. Because bitcoin does not guarantee consistency.

Bitcoin only guarantees that it will try its best to make any inconsistency be solved eventually.

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!