Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #1693 > unrolled thread

Marzullo's Algorithm

Back to article view | Back to comp.programming

Contents

  Marzullo's Algorithm bob <bob@coolfone.comze.com> - 2012-06-01 08:25 -0700
    Re: Marzullo's Algorithm Ike Naar <ike@iceland.freeshell.org> - 2012-06-01 15:38 +0000
      Re: Marzullo's Algorithm Robert Wessel <robertwessel2@yahoo.com> - 2012-06-01 10:58 -0500
    Re: Marzullo's Algorithm "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2012-06-01 18:29 +0200

#1693 — Marzullo's Algorithm

Let's say I have one computer that is synchronized to an atomic clock.

Then I have, say 5 other computers, that need the correct time and will attempt to get it by talking to the timekeeper computer.  Those 5 computers are all connected to the timekeeper by Wifi, so there can be a bit of latency (although the latency tends to vary).

What is the best way to get the 5 computers synced to the timekeeper?

I am thinking Marzullo's Algorithm is a good way.  However, there may be something slightly simpler.  In Marzullo's Algorithm, it is for talking to multiple timekeepers usually.  If we are only talking to one, we can simplify Marzullo's Algorithm:

Simply have each computer ask for the time from the timekeeper 100 times or so.  Then use the time that came back with the lowest Round Trip Time (RTT).

Can someone let me know if this is a correct simplification of Marzullo's Algorithm for one timekeeper?

[toc] | [next] | [standalone]

#1694

On 2012-06-01, bob <bob@coolfone.comze.com> wrote:
> Let's say I have one computer that is synchronized to an atomic clock.
>
> Then I have, say 5 other computers, that need the correct time and
> will attempt to get it by talking to the timekeeper computer.  Those
> 5 computers are all connected to the timekeeper by Wifi, so there can
> be a bit of latency (although the latency tends to vary).
>
> What is the best way to get the 5 computers synced to the timekeeper?

Have you looked at NTP (http://www.ntp.org) ?

[toc] | [prev] | [next] | [standalone]

#1695

On Fri, 1 Jun 2012 15:38:05 +0000 (UTC), Ike Naar
<ike@iceland.freeshell.org> wrote:

>On 2012-06-01, bob <bob@coolfone.comze.com> wrote:
>> Let's say I have one computer that is synchronized to an atomic clock.
>>
>> Then I have, say 5 other computers, that need the correct time and
>> will attempt to get it by talking to the timekeeper computer.  Those
>> 5 computers are all connected to the timekeeper by Wifi, so there can
>> be a bit of latency (although the latency tends to vary).
>>
>> What is the best way to get the 5 computers synced to the timekeeper?
>
>Have you looked at NTP (http://www.ntp.org) ?


I was going to suggest using NTP, either directly to set the time
(since they've spent decades dealing with these issues), or as a
source.

In any event NTP uses an improved version of Marzullo's Algorithm to
do its thing.

[toc] | [prev] | [next] | [standalone]

#1696

On Fri, 1 Jun 2012 08:25:05 -0700 (PDT), bob wrote:

> Let's say I have one computer that is synchronized to an atomic clock.
> 
> Then I have, say 5 other computers, that need the correct time and will
> attempt to get it by talking to the timekeeper computer.  Those 5
> computers are all connected to the timekeeper by Wifi, so there can be a
> bit of latency (although the latency tends to vary).
> 
> What is the best way to get the 5 computers synced to the timekeeper?
> 
> I am thinking Marzullo's Algorithm is a good way.

Maybe, however you have only one time source. There are other ways.

> Simply have each computer ask for the time from the timekeeper 100 times
> or so.  Then use the time that came back with the lowest Round Trip Time
> (RTT).

The real problem is clock deviation, which could be about 5us/s. So, you
do have to synchronize clocks all the time.

Instead of sorting time measures you just use weighted running averaging of
the time skew, where the weight is decreases when RTT increases and also
decreases with the time.

There could be further requirements, like monotonic changes, which may
apply in your case. Then you would add a layer on top of that, which would
prevent backward jumps. Same, when clock acceleration must be limited from
above, etc.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web