A network-wide clock at the expense of 8 extra bytes in the message headers.
And another 8 bytes for in-group messages, and the same for our list of close group members.
The idea of timekeeping came up multiple times, but it was deemed impossible without having to rely on external references. For most practical purposes*, however, it would be enough to establish the order of events. I believe we may achieve this entirely within the network by exploiting that information can propagate through the network only with a finite speed.
The method I’m proposing is very simple:
- Network messages will have a field for the time, which is a simple counter.
- When a node receives a message from outside its close group, it will update its idea of the current time.
- This is not the time the node uses when sending a message; that is coming from the close group’s agreement, for which its idea of time is used as one of the inputs.
- When a node sends a message, it will send the time that its close group decided based on these rules:
- When more than half of the nodes agree on the time, all nodes in the group start using it.
- When an actual quorum is achieved, the time is incremented.
I think this method will provide a way to establish an approximate order of events, with higher and higher reliability as the difference between two timestamps grows. It would be lovely to run an actual simulation though.
* What these purposes should be is outside the scope of this post.