Network partitioning

Hi there.

I have a question about network partitioning. I read the white paper but I couldn’t understand how Algorand resists on Network partitioning .

Imagine after Bn the network become totally partitioned. Then probably we will have two different committees for both partitions and that might result to a fork.

Whitepaper talks bout it at section 7.4 under “Getting stuck”. The whitepaper assumes that: “Neither group is large enough to gather enough votes on their own”

Could you please explain more about this assumption. Considering that some offline accounts might become online and start doing Sortition in both partitions.

1 Like

That is a very good question.
The short answer is that there is no risk of forking in that case. The only thing that may happen is that the blockchain stalls until the network recovers.
Here are some more details.

To participate in consensus, an account needs to be marked online.
This is done by sending a special transaction, called a key registration transaction - Algorand Developer Docs).
The account is marked online 320 rounds after the key registration transaction is sent to the blockchain.

The sortition algorithm randomly selects a committee of online accounts.
To understand how things work, let’s make the following simplifying assumptions

  • the committee is composed of 1,000 parties
  • a block is committed if at least 700 of these parties vote for it
  • each account on the blockchain has exactly 1 Algo. (Accounts with more Algos can be selected multiple times in a committee, as if each Algo of the account was selected individually.)
  • there are X online Algos

Each online account (with 1 Algo) will be selected in the committee with probability 1,000 / X.
Note that the blockchain knows X because it knows the list of online accounts.

Now, if the network is partitioned, say 50% / 50%, with high probability, each group in the partition will have 500 selected parties in the committee. This is not enough to get 700 votes for the same block. Thus the blockchain stalls.

Note that since no blocks can be committed, in particular no key registration can be made, so no new party can vote in the consensus.
This really means that the blockchain just stalls until the network recovers.

A few remarks:

  • The fact that the blockchain stalls in case of a 50/50 partition is unavoidable. It is essentially a consequence of the CAP theorem: Algorand is network tolerant and consistent, so it cannot be available in case of some network partitions.
  • One great feature is that after the network recovers, the Algorand blockchain commits new blocks almost immediately. There is no long process to fix the network recovery.
  • If the network is partitioned 90/10, then the largest group will grow the blockchain while the smaller group will just not see the new blocks. This is perfectly fine. There will still be no fork: the smallest group cannot commit to new block by itself.
5 Likes

@fabrice

Thanks for the explanation. The “key registration transaction” is a good mechanism to protect malicious voting.

It seems to me that the key registration has nothing to do with partition resilience or recovery or preventing blockchain from forking…

It’s just a way to make sure that we can still collect 2/3 votes, in case many users are not participating in the consensus.

@fabrice

What happens if the network remains partitioned for a long time, and the rounds come to a end?

Could not happen that both networks convince themselves that all their participants are online?

In that case, the blockchain would stall and not produce any block.

Since the only way for an account to be marked online or offline is to commit a key registration in a block and since no blocks are generated, the set of online accounts remain the same and there is no risk of fork.

1 Like

As @fabrice suggested, once the networks get partitioned, there is no further progress on the network ( for good or bad - depending on your position ). ( you might be able to convince me that a given participant is online or not), but if the participant’s votes could not reach the rest of the network, that participant would be effectively offline.

The network would recover once there are enough online voting participants.