cockroachdb/cockroach — pull request #102 by embark (2014-10-03 02:15:42+00:00)
Title: Simple clock offset measurement between two connected nodes

The beginnings of measuring a node's clock offset compared to the rest of it's connected nodes.

This change enables the client connections between two nodes to estimate their relative offset. Note that if node A has a client connection to node B, then it is likely that node B will not establish a connection with node A because their communication is already covered by A's client. Thus the next step might be to have A send its offset measurement to B. Then B will be updated on the latest offset measurement, though this requires the heartbeat to have three messages.

What I plan to do from here is largely based on the NTP algorithm:
* Have clients keep track of the more accurate offset measurement among the last x samples (the most accurate should be the offset with the smallest round-trip delay time). This will help to reduce noise in measurements (https://www.eecis.udel.edu/~mills/ntp/html/filter.html)
* Have a routine that collects all the active offset interval measurements from the heartbeat service and use an intersection algorithm to find the most likely interval for the true offset (https://www.eecis.udel.edu/~mills/ntp/html/select.html)
* There are more statistical techniques to clean up the data even more, but I'm not sure yet if it is necessary.

Please let me know if my plan seems reasonable! Sorry I got to this later than I expected, but I have been blocked until recently.