Event Graph
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.
Synchronization
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
we call 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 inv
.
- A creates a new event.
- A sends
event
to - For each in :
- Create an
inv
representing the event. - Broadcast to all connected nodes
p2p.broadcast(inv)
.
- Create an
Upon receiving an inv
:
- Check if we already have the event. If not then reply back with
getevent
. - The node receives
getevent
, and sendsevent
back.
So in this diagram, A will send event
to . Each will respond
back to A with inv
. Each one of also receive inv
,
and since they don't have the event, they will send back to ,
a getevent
message. will send them the event
.
Genesis Event
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.