2
$\begingroup$

Imagine a chord-like network $N$. each machine $m \in N$ is directly connected to $N_m \subset N$.

Without relying on official timeservers, I want all machines to synchronize to some time with millisecond precision.

my algorithm is executed some time after a machine joined the network, and works as follows:

  1. the machine asks each machine it is directly adjacent to what it thinks the network time is, adjust for latency and subtract local time from that
  2. take the median delta of that list, and apply that to the local time as the network time.

Intuitively I think that this method is self-stabilizing because the deviation, and its error should be normally distributed around a consensus, and the $\sigma$ of the delta should decrease over time.

Problem is, I think that a relatively small number of bad actors can poison the network: if only $|N_{m_0}|/2 +1$ of the machines in $N_{m_0}$ don't abide by the protocol and report a doctored time, $m_0$ becomes poisoned and starts trying to poison other innocent nodes in $N_{m_0}$, and so forth, until all of $N$ is poisoned.

I was wondering whether I was correct, and if you know of any papers on the topic, because this seems more complex than I originally thought. Is a blockchain really required?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ You could disregard outliers from influencing other machines on the network, perhaps? $\endgroup$ – Badr B Jun 6 '18 at 5:05
  • $\begingroup$ @BadrB taking the median would generally assure that... but actually I think that it might be the case the infection can't spread in a chord, because the machines one machine sees should mostly be invisible to any other machine it's connected to, therefore a majority won't be reached.. hm. $\endgroup$ – option 12 Jun 6 '18 at 5:58
  • $\begingroup$ You may do some internet search, afaik Google has developed some good algorithms to globally synchronise events, that is everyone agrees about the order of events. That’s more important to many than estimating time. Not quite sure why you want to avoid time servers. $\endgroup$ – gnasher729 Jun 6 '18 at 7:27
  • $\begingroup$ @gnasher729 no service is guaranteed to be online, available, or true, all the time. You can agree on orders of events if you use a hash chain, but a hash chain requires everyone to be aware of every event at all times before posting a new one. I don't see how you can implement this otherwise without a synchronized clock. also, please link a resource, or keywords you know of. $\endgroup$ – option 12 Jun 6 '18 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.