State Graph Brainstorm #289
Description
Our current implementation of simplex is lacking the ability to sync and vote on any non-finalized chain. Nodes can receive notarizations and empty notarizations for any round, and in any order. Our current implementation usesthe first notarization/empty notarization message to go to the next round. Any messages for previous rounds get discarded. This is a problem because we do not know which "chain" will get accepted. Will it be the one with the notarization, or the empty notarization.
Ex. our nodes see messages in this order b_1 <- E <- b_3 while other nodes see messages in this order b_1 <- b_2 <- b_3. Because our node progressed the round due to an empty notarization in round 2, we will not be able to verify b_3(since we don't have the previous block for it). In round 3, other nodes may have similarly timed out and received an empty notarization for b_3 while others received the notarization. This causes the internal states of nodes to differ and unable to verify blocks.
There is a similar problem in replication as we only replicate rounds rather than chains. Maybe a node sends us an empty notarization, when in reality the rest of the nodes built of a notarization.
I think the solution is to allow our node to process old notarizations/blocks/empty notarizations for rounds > highest finalized round. We should keep track of chains using a graph structure, as well as replicate future blocks and request missing previous blocks for chains that we haven't finalized. This is safe, as long as we maintain the invariant of never voting for an empty block and a finalize block for the same round(unless we see a finalization for child in that chain). Doing this would eliminate a lot of edge cases regarding replication, and some potential bugs we may currently have)
Side Note: we can still keep the replicate for finalized sequences because they are final.