Which properties of the CAP theorem are satisfied by TON

[alfredonodo]

In theoretical computer science, the CAP theorem states that any distributed data store can only provide two of the following three guarantees: Consistency, Availability and Partition tolerance. A comparison of various distributed databases is available here. According to wikipedia, blockchain often sacrifices immediate consistency for availability and partition tolerance. By requiring a specific number of "confirmations", blockchain consensus algorithms bare basically reduced to eventual consistency. This should be true for all blockchains that allow forks and require a certain number of confirmations for a block before it is final i.e. for blockchains where a new block is taken from the fork with the longest chain. There are other blockchains, such as TON, that are considered "forkless" and do not have this problem i.e. a new block does not need any confirmation and is immediately final once consensus is reached. So it would seem that forkless blockchains like TON are also able to guarantee consistency in addition to the other two properties, but this is not possible given the CAP theorem. This is why I am wondering which of the two properties of the CAP theorem are met by TON. Thank you

[alfredonodo]

Hi, I have studied this question in depth and I think I have found the answer. In computer science, there are several databases that fall into various categories of the CAP theorem:

AP: Cassandra, CouchDB, Elastic Search, Blockchain (Nakamoto-based consensus). CP: MongoDB, HBase, Redis, Memcached, Blockchain (BFT-based consensus). CA: PostgreSQL, MySQL (non-distributed databases).

A blockchain is a distributed database without a central authority establishing the truth; in fact, nodes reach consensus through algorithms such as Proof-of-Work (PoW) or Proof-of-Stake (PoS). Once nodes agree on the validity of a block, they add it to the chain. A blockchain is fault-tolerant, i.e. it can handle node failure and even the presence of nodes acting maliciously. The number of failures it can handle depends on the consensus algorithm. In general, to attack the network and alter blocks production, an attacker would need to control 51% of the computing power in PoW (Nakamoto-based consensus), 51% of the participation in PoS (Nakamoto-based consensus) or 67% of the participation in PoS (BFT-based consensus) (in the latter case, 33% of the participation is needed to halt consensus and blocks production). Since the CAP theorem states that a distributed system cannot simultaneously provide consistency, availability and partition tolerance, a blockchain cannot be live in the case of dynamic participation and safe in the case of temporary network partitions, so there is a availability-consistency (finality) dilemma. For a blockchain, consistency is linked to finality, which can be probabilistic or absolute. In the first case, the Nakamoto-based consensus (e.g. Bitcoin, Cardano, Mina), the chain admits forks and confirmation blocks are required to achieve finality, i.e. the deeper a transaction is in the chain, the less likely it is that there will be a change (the longest or heaviest chain wins). In the second case, the BFT-based consensus (e.g. Algorand, Cosmos, Everscale, ICP, TON, probabilistic BFT e.g. Avalanche or mixed i.e. it allows forks, but has BFT-finality e.g. EOS, Ethereum, MultiversX, Near, Polkadot, Solana), there are no forks (forkless) and a transaction is considered immediately final as soon as it is included in a block and added to the chain. AP blockchains choose availability over consistency and are designed to operate with dynamic participation; in fact, they favour liveness over safety to provide (dynamic) availability, i.e. the network continues to make decisions even during periods of low participation. CP blockchains choose consistency over availability and are designed to operate under conditions of partial synchrony; in fact, they favour safety over liveness and provide finality, i.e. once consensus is reached the decision is final and cannot be reverted. In order to improve (dynamic) availability, many BFT-based PoS blockchains (Ethereum, Everscale, Polkadot, TON) provide a mechanism that penalises nodes with low participation, i.e. which are inactive or have low performance. For example, on Bitcoin users have to wait 6 confirmation blocks (10 minutes per block ~ 60 minutes) before their transaction is considered final and the blockchain reaches consistency. While on Ethereum users have to wait 70-80 confirmation blocks (12 seconds per block ~ 768-960 seconds) before their transaction is considered final. Finally, on TON, 1 block is enough (5-6 seconds per block) and consistency is immediate. Therefore, forkless blockchains such as TON are distributed databases of the CP category that prioritise safety over liveness and prefer to be consistent rather than available. To improve liveness and availability, TON provides a slashing mechanism that penalises nodes with low participation and performance. The recent public performance test where TON broke the TPS world record shows the effectiveness and goodness of its design.