mosaicnetworks / babble

Distributed Consensus Middleware
MIT License
478 stars 95 forks source link

Sync topological order #129

Closed arrivets closed 5 years ago

arrivets commented 5 years ago

Imagine a hashgraph that started with node A, then B joined, and finally, C tries to join. Upon joining, node C gets a sync response from A, looking something like this:

   4
 / |
3  1
|
2
|
1 

A  B

C will receive the events in lamport-timestamp order (1,1,2,3,4), and will attempt to insert them in that order. So it will try to insert B's event before inserting the events that resulted in adding B to the validator set. This results in an error (unknown creator) being logged and returned by the core.Sync method. Ultimately, C continues attempting to sync and will gradually insert the other events that will let it insert B in the validator-set, and everything falls into place.

But we should find a way to avoid this scenario because:

1) it's inefficient 2) it creates confusing error messages 3) it could actually prevent a node from ever joining if the hashgraph is big enough

arrivets commented 5 years ago

Non-issue.

SyncResponse actually contains Events in topological order, not Lamport timestamp order.

Topological order is a local order corresponding to when Events were actually inserted into the hashgraph. It is local in the sense that every participants may have a slightly different topological ordering.