Congratulations Pierre, Fraser, Qi Ma; I’ve been following development and have been using the example for a while to write this post. Really cool seeing this development happening out in the open and so actively and professionally.
The RFC and whitepaper explained parsec by starting with the fundamental building blocks and then combining them into the final result. In contrast, this post looks only at the high-level output of the algorithm and then picks out interesting details to investigate so we can better understand the inner workings of the algorithm from the top down.
Running the example simulation of parsec (thanks Fraser), there are some interesting talking points. Mostly I just wanted to explore the example so here it is. Hopefully it provokes some discussion and experiments.
Brief Description
The example creates a simulation with a specific number of undecided network events (eg vaults joining, departing etc) and a specific number of peers who must reach consensus on which events are genuine and their order.
In this simulation the term ‘round’ is used a lot and it means ‘a set of communications’ (ie gossips), as the comment in source code explains:
[In this round] Each peer will send a request and handle the corresponding response. For each peer, there is also a chance that they will vote for one of the transactions if they haven’t already done so.
Peers each vote for a random network event (ie declare they think that event is genuine) roughly every once every three rounds. In this simulation there are no malicious events to deal with or adversarial peers.
In each round every peer also engages in gossip to progress their current view of the overall voting.
I think the frequency of casting new votes is critical to the efficiency of the simulation, and in this example the average of one vote every 3 rounds is what dominates all the following results. In real life votes would be cast immediately upon validation, so this simulation is artificially slow in reaching consensus. But it gives interesting insights into the algorithm anyhow.
Initial Conditions
The following observations are from running the example with these settings:
cargo run --example=basic --features=dump-graphs -- --peers=5 --events=10
Using RNG seed: Some([3046582725, 1303372263, 4262207032, 2761586907])
First Partially Stable Block
Is ‘partially stable block’ the right phrase to use here? There’s a lot of definitions in RFC-0049 PARSEC Definitions but I wasn’t sure how to label the state when a block is stable in some peers but not all peers.
Gossip Round 011
================
Votes:
Alice: [hN1C4, Qv0uw, DbyK2, sYBgs, R79u1, SiiUl, 33aLa]
Bob: [Qv0uw, sYBgs, hN1C4, gV9OD, 33aLa, DbyK2]
Carol: [Qv0uw, 33aLa, R79u1, tbIMU, SiiUl, gV9OD]
Dave: [Qv0uw, hN1C4, DbyK2, gV9OD, R79u1]
Eric: [YvM0O, 33aLa, tbIMU, sYBgs, gV9OD]
Stable Blocks:
Alice: []
Bob: []
Carol: []
Dave: []
Eric: [Qv0uw]
Each client has between 5 and 7 votes for blocks that are not stable at this point. This is interesting because it gives some indication of the ‘uncertainty’ and how much ‘available but undecided territory’ there may be to manage in real life. I think in real life it will depend on the rate of new network events vs gossip rate, but it’s good to see there isn’t too much ‘ambiguous’ state needing to be managed.
Why does Eric have stable block Qv0uw but not have a vote for it? It’s not until seven rounds later in Round 018 that Eric has a vote for this block. The block as seen by Eric must have a supermajority of votes by other peers, so maybe Eric’s vote is unimportant regarding the stability of the block from Eric’s perspective. The idea of ‘perspective of each peer’ and how it may differ between peers is an important one.
First Fully Stable Block
Gossip Round 013
================
Votes:
Alice: [hN1C4, Qv0uw, DbyK2, sYBgs, R79u1, SiiUl, 33aLa, YvM0O, gV9OD]
Bob: [Qv0uw, sYBgs, hN1C4, gV9OD, 33aLa, DbyK2, tbIMU]
Carol: [Qv0uw, 33aLa, R79u1, tbIMU, SiiUl, gV9OD]
Dave: [Qv0uw, hN1C4, DbyK2, gV9OD, R79u1, 33aLa]
Eric: [YvM0O, 33aLa, tbIMU, sYBgs, gV9OD, hN1C4]
Stable Blocks:
Alice: [Qv0uw]
Bob: [Qv0uw]
Carol: [Qv0uw]
Dave: [Qv0uw]
Eric: [Qv0uw]
Two rounds later all nodes have one stable block. In the intervening Round 012 there are 3 nodes with stable blocks. Round 013 is the first one where all nodes have a stable block.
Additional Stable Blocks
Gossip Round 018
================
Votes:
Alice: [hN1C4, Qv0uw, DbyK2, sYBgs, R79u1, SiiUl, 33aLa, YvM0O, gV9OD]
Bob: [Qv0uw, sYBgs, hN1C4, gV9OD, 33aLa, DbyK2, tbIMU, YvM0O, SiiUl]
Carol: [Qv0uw, 33aLa, R79u1, tbIMU, SiiUl, gV9OD, hN1C4, YvM0O]
Dave: [Qv0uw, hN1C4, DbyK2, gV9OD, R79u1, 33aLa, sYBgs, tbIMU, SiiUl, YvM0O]
Eric: [YvM0O, 33aLa, tbIMU, sYBgs, gV9OD, hN1C4, SiiUl, Qv0uw]
Stable Blocks:
Alice: [Qv0uw, 33aLa, gV9OD, hN1C4]
Bob: [Qv0uw]
Carol: [Qv0uw]
Dave: [Qv0uw]
Eric: [Qv0uw]
The stable blocks don’t change for another 5 rounds, but in Round 018 Alice adds 3 stable blocks all at once. Then in the next round, Round 019, all the other nodes do too. This is a sudden increase in stable blocks, which is different to the idea of blockchain where each block generally is added sequentially one at a time.
It also means the concept of blockchain orphans is not directly applicable to the stable block list. It’s interesting to see the difference to blockchain and there’s a lot of work ahead to build a new vernacular around the behaviour of parsec blocks. Discussions will need to both pull from existing blockchain language and at the same time push away from blockchain ideas. It’s going to be interesting seeing that unfold.
Final Outcome
Gossip Round 026
================
Votes:
Alice: [hN1C4, Qv0uw, DbyK2, sYBgs, R79u1, SiiUl, 33aLa, YvM0O, gV9OD, tbIMU]
Bob: [Qv0uw, sYBgs, hN1C4, gV9OD, 33aLa, DbyK2, tbIMU, YvM0O, SiiUl, R79u1]
Carol: [Qv0uw, 33aLa, R79u1, tbIMU, SiiUl, gV9OD, hN1C4, YvM0O, sYBgs, DbyK2]
Dave: [Qv0uw, hN1C4, DbyK2, gV9OD, R79u1, 33aLa, sYBgs, tbIMU, SiiUl, YvM0O]
Eric: [YvM0O, 33aLa, tbIMU, sYBgs, gV9OD, hN1C4, SiiUl, Qv0uw, R79u1, DbyK2]
Stable Blocks:
Alice: [Qv0uw, 33aLa, gV9OD, hN1C4, sYBgs, tbIMU, SiiUl, YvM0O, DbyK2, R79u1]
Bob: [Qv0uw, 33aLa, gV9OD, hN1C4, sYBgs, tbIMU, SiiUl, YvM0O, DbyK2, R79u1]
Carol: [Qv0uw, 33aLa, gV9OD, hN1C4, sYBgs, tbIMU, SiiUl, YvM0O, DbyK2, R79u1]
Dave: [Qv0uw, 33aLa, gV9OD, hN1C4, sYBgs, tbIMU, SiiUl, YvM0O, DbyK2, R79u1]
Eric: [Qv0uw, 33aLa, gV9OD, hN1C4, sYBgs, tbIMU, SiiUl, YvM0O, DbyK2, R79u1]
The simulation takes 26 rounds to resolve and all nodes have all ten blocks stable and in the same order as each other. Very cool!
Scalability
When the number of events increases or the number of nodes increases, does the algorithm get slower or faster or stay the same?
For all these tests the seed used is --seed=1,1,1,1 where 1 is the test number.
Scaling Events
The prior test took an average of 2.6 rounds per stable block.
The tests are run with the following command:
cargo run --example=basic --features=dump-graphs -- --peers=5 --events=E --seed=N,N,N,N
and results in the average number of rounds per stable block (RPSB):
Peers Events Test1 2 3 4 5 | AvgRPSB
5 10 40 40 33 27 38 | 3.6
5 20 77 75 69 60 64 | 3.4
5 40 105 120 121 142 126 | 3.1
5 100 272 300 296 306 287 | 2.9
Having many blocks in limbo seems to improve the efficiency of each round, but is pretty-much about 3 rounds to create a stable block (for 5 peers). There’s a lot of room for further exploration here.
It’s worth pointing out that removing the artificial constraint of one vote every three rounds and replacing it with a vote every single round gave much faster consensus (~1.1 rounds per stable block instead of ~3 rounds).
Scaling Peers
Peers Events Test1 2 3 4 5 | AvgRPSB
5 10 40 40 33 27 38 | 3.56
10 10 42 34 33 38 35 | 3.64
20 10 37 37 37 39 38 | 3.76
There seems to be a small increase in the number of rounds per stable block as the number of peers increases. In SAFE this effect should be virtually unobservable since there’s a fairly low number of peers in each section. Again it’s around an average of 3 rounds to form each stable block.
Performance
In the Upcoming features there’s an item “Benchmark and optimise the code” so it’s not really something I will do in detail here just yet, but the average time per stable block on a stock 2018 intel i7-7700 @ 3.6 GHz is 1.6s (5 peers 10 events).
This is not a good indicator of real world performance for many reasons, but it’s at least some sort of comparison point for the future. I’m really excited to see what maidsafe do in this area. I’ve already noticed a bit of behaviour that indicates ‘pre-optimised-code’ so I know real life will be much more exciting than this simulation.
Summary
Stable blocks are formed reliably regardless of how many peers or how many events are involved. The rate of consensus is slower than expected in real life because of the artificial delay in casting votes, but is also very fast due to the efficiency of the gossip algorithm.
Once again, congratulations maidsafe for all the work on this awesome algorithm.
The light in the end of the tunnel is becoming brighter every second. This is a very happy day too celebrate this milestone. Keep on going super ants rock stars! 
