The event graph represents sequential events in an asynchronous environment.
Events can form small forks which should be quickly reconciled as new nodes are added to the structure and pull them in.
Ties are broken using the timestamps inside the events.
The main purpose of the graph is synchronization. This allows nodes in the network maintain a fully synced store of objects. How those objects are interpreted is up to the application.
We add a little more information about the objects which is that they are events with a timestamp, which allows our algorithm to be more intelligent.
Each node is read-only and this is an append-only data structure. However the application may wish to prune old data from the store to conserve memory.
Nodes in the event graph are active, whereas nodes not yet in the graph are orphans.
When node A receives an event from node B, it will check whether all parents are in the active pool. If there are missing parents then:
- Check whether the missing parents exist in the orphans pool.
- If they have missing parents (they should), then request their missing parent events from node B.
- If the missing parents are not in the orphans pool:
- Add this event to the orphans pool.
- Request the missing parent events from node B.
Once a node is successfully added to the active pool, and linked in the event graph, then
reorganize(). This function loops through all the orphans, and tries to relink
them with the active pool. If there are any missing parents, then they are added back to
the orphan pool.
Creating an Event
In this example A creates a new event. Since the event is new, it is impossible for
any nodes in the network to possess it, so A does not need to send an
- A creates a new event.
- A sends
- For each in :
- Create an
invrepresenting the event.
- Broadcast to all connected nodes
- Create an
- A waits for 3 nodes to respond back with the
invconfirming they received it.
- Until A receives the
invconfirms, it will wait for 1 minute and then resend the
Upon receiving an
- Check if we already have the event. If not then reply back with
- The node receives
getevent, and sends
So in this diagram, A will send
event to . Each will respond
back to A with
inv, and A will stop sending
event. Each one of
inv, and since they don't have the event, they will send back to ,
getevent message. will send them the
All nodes start with a single hardcoded genesis event in their graph. The application layer should ignore this event. This serves as the origin event for synchronization.