Merge pull request #532 from MichaelMure/dag-entity

Work towards a reusable entity datastructure + commit signature

2 files changed, 14 insertions, 6 deletions

diff --git a/util/lamport/clock_testing.go b/util/lamport/clock_testing.go
index fc59afb2..de66c5c9 100644
--- a/util/lamport/clock_testing.go
+++ b/util/lamport/clock_testing.go
@@ -11,14 +11,14 @@ 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)
+	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 ce6f2d4d..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 (
@@ -62,7 +70,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
@@ -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