From 44d7587940f842a343a64d9107601591bdfb1027 Mon Sep 17 00:00:00 2001 From: Michael Muré Date: Sun, 8 Nov 2020 17:53:11 +0100 Subject: lamport: match wikipedia algorithm --- util/lamport/clock_testing.go | 2 +- util/lamport/mem_clock.go | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'util/lamport') diff --git a/util/lamport/clock_testing.go b/util/lamport/clock_testing.go index fc59afb2..4bf6d2bf 100644 --- a/util/lamport/clock_testing.go +++ b/util/lamport/clock_testing.go @@ -11,7 +11,7 @@ func testClock(t *testing.T, c Clock) { val, err := c.Increment() assert.NoError(t, err) - assert.Equal(t, Time(1), val) + assert.Equal(t, Time(2), val) assert.Equal(t, Time(2), c.Time()) err = c.Witness(41) diff --git a/util/lamport/mem_clock.go b/util/lamport/mem_clock.go index ce6f2d4d..f113b501 100644 --- a/util/lamport/mem_clock.go +++ b/util/lamport/mem_clock.go @@ -62,7 +62,7 @@ func (mc *MemClock) Time() Time { // Increment is used to return the value of the lamport clock and increment it afterwards func (mc *MemClock) Increment() (Time, error) { - return Time(atomic.AddUint64(&mc.counter, 1) - 1), nil + return Time(atomic.AddUint64(&mc.counter, 1)), nil } // Witness is called to update our local clock if necessary after -- cgit From 8d63c983c982f93cc48d3996d6bd097ddeeb327f Mon Sep 17 00:00:00 2001 From: Michael Muré Date: Sun, 3 Jan 2021 23:59:25 +0100 Subject: WIP --- util/lamport/clock_testing.go | 4 ++-- util/lamport/mem_clock.go | 12 ++++++++++-- 2 files changed, 12 insertions(+), 4 deletions(-) (limited to 'util/lamport') diff --git a/util/lamport/clock_testing.go b/util/lamport/clock_testing.go index 4bf6d2bf..de66c5c9 100644 --- a/util/lamport/clock_testing.go +++ b/util/lamport/clock_testing.go @@ -14,11 +14,11 @@ func testClock(t *testing.T, c Clock) { assert.Equal(t, Time(2), val) assert.Equal(t, Time(2), c.Time()) - err = c.Witness(41) + err = c.Witness(42) assert.NoError(t, err) assert.Equal(t, Time(42), c.Time()) - err = c.Witness(41) + err = c.Witness(42) assert.NoError(t, err) assert.Equal(t, Time(42), c.Time()) diff --git a/util/lamport/mem_clock.go b/util/lamport/mem_clock.go index f113b501..d824d834 100644 --- a/util/lamport/mem_clock.go +++ b/util/lamport/mem_clock.go @@ -25,6 +25,14 @@ */ +// Note: this code originally originate from Hashicorp's Serf but has been changed since to fit git-bug's need. + +// Note: this Lamport clock implementation is different than the algorithms you can find, notably Wikipedia or the +// original Serf implementation. The reason is lie to what constitute an event in this distributed system. +// Commonly, events happen when messages are sent or received, whereas in git-bug events happen when some data is +// written, but *not* when read. This is why Witness set the time to the max seen value instead of max seen value +1. +// See https://cs.stackexchange.com/a/133730/129795 + package lamport import ( @@ -72,12 +80,12 @@ WITNESS: // If the other value is old, we do not need to do anything cur := atomic.LoadUint64(&mc.counter) other := uint64(v) - if other < cur { + if other <= cur { return nil } // Ensure that our local clock is at least one ahead. - if !atomic.CompareAndSwapUint64(&mc.counter, cur, other+1) { + if !atomic.CompareAndSwapUint64(&mc.counter, cur, other) { // CAS: CompareAndSwap // The CAS failed, so we just retry. Eventually our CAS should // succeed or a future witness will pass us by and our witness -- cgit