1 files changed, 211 insertions, 0 deletions
diff --git a/vendor/github.com/dexon-foundation/dexon-consensus/core/negative-ack.go b/vendor/github.com/dexon-foundation/dexon-consensus/core/negative-ack.go
new file mode 100644
index 000000000..417862912
--- /dev/null
+++ b/vendor/github.com/dexon-foundation/dexon-consensus/core/negative-ack.go
@@ -0,0 +1,211 @@
+// Copyright 2018 The dexon-consensus Authors
+// This file is part of the dexon-consensus library.
+//
+// The dexon-consensus library is free software: you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public License as
+// published by the Free Software Foundation, either version 3 of the License,
+// or (at your option) any later version.
+//
+// The dexon-consensus library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the dexon-consensus library. If not, see
+// <http://www.gnu.org/licenses/>.
+
+package core
+
+import (
+	"time"
+
+	"github.com/dexon-foundation/dexon-consensus/core/types"
+)
+
+type negativeAck struct {
+	// owner is the ID of proposer itself, this is used when deciding
+	// a node to be restricted or not.
+	owner types.NodeID
+
+	numOfNodes int
+
+	// timeDelay and timeExpire are for nack timeout.
+	timeDelay  time.Duration
+	timeExpire time.Duration
+
+	// restricteds stores nodes which has been restricted and the time it's
+	// restricted.
+	restricteds map[types.NodeID]time.Time
+
+	// lastVotes and lockedVotes store the votes for nack. lastVotes[nid1][nid2]
+	// and lockedVotes[nid1][nid2] both mean that nid2 votes nid1. The difference
+	// is lockedVotes works only when nid1 is restricted, so that the votes are
+	// needed to be locked.
+	lastVotes   map[types.NodeID]map[types.NodeID]struct{}
+	lockedVotes map[types.NodeID]map[types.NodeID]struct{}
+
+	// timeDiffs is the cache for last time stamps. timeDiffs[nid1][nid2] means
+	// the last updated timestamps nid1 sees nid2.
+	timeDiffs map[types.NodeID]map[types.NodeID]map[types.NodeID]time.Time
+}
+
+// newNegativeAck creates a new negaticeAck instance.
+func newNegativeAck(nid types.NodeID) *negativeAck {
+	n := &negativeAck{
+		owner:       nid,
+		numOfNodes:  0,
+		restricteds: make(map[types.NodeID]time.Time),
+		lastVotes:   make(map[types.NodeID]map[types.NodeID]struct{}),
+		lockedVotes: make(map[types.NodeID]map[types.NodeID]struct{}),
+		timeDiffs:   make(map[types.NodeID]map[types.NodeID]map[types.NodeID]time.Time),
+	}
+	n.addNode(nid)
+	return n
+}
+
+// processNewVote is called when a new "vote" occurs, that is, a node
+// sees that other 2f + 1 nodes think a node is slow. "nid" is the
+// node which propesed the block which the timestamps votes and "h" is
+// the node been voted to be nacked.
+func (n *negativeAck) processNewVote(
+	nid types.NodeID,
+	h types.NodeID,
+) []types.NodeID {
+
+	nackeds := []types.NodeID{}
+	if _, exist := n.restricteds[h]; exist {
+		n.lockedVotes[h][nid] = struct{}{}
+		if len(n.lockedVotes[h]) > 2*(n.numOfNodes-1)/3 {
+			nackeds = append(nackeds, h)
+			delete(n.restricteds, h)
+		}
+	} else {
+		if n.owner == nid {
+			n.restrict(h)
+		} else {
+			n.lastVotes[h][nid] = struct{}{}
+			if len(n.lastVotes[h]) > (n.numOfNodes-1)/3 {
+				n.restrict(h)
+			}
+		}
+	}
+	return nackeds
+}
+
+// processTimestamps process new timestamps of a block which is proposed by
+// node nid, and returns the nodes being nacked.
+func (n *negativeAck) processTimestamps(
+	nid types.NodeID,
+	ts map[types.NodeID]time.Time,
+) []types.NodeID {
+
+	n.checkRestrictExpire()
+
+	nackeds := []types.NodeID{}
+	for h := range n.timeDiffs {
+		if n.timeDiffs[nid][h][h].Equal(ts[h]) {
+			votes := 0
+			for hh := range n.timeDiffs {
+				if ts[hh].Sub(n.timeDiffs[nid][h][hh]) >= n.timeDelay {
+					votes++
+				}
+			}
+			if votes > 2*((n.numOfNodes-1)/3) {
+				n.lastVotes[h][nid] = struct{}{}
+				nack := n.processNewVote(nid, h)
+				for _, i := range nack {
+					nackeds = append(nackeds, i)
+				}
+			} else {
+				delete(n.lastVotes[h], nid)
+			}
+		} else {
+			for hh := range n.timeDiffs {
+				n.timeDiffs[nid][h][hh] = ts[hh]
+			}
+			delete(n.lastVotes[h], nid)
+		}
+	}
+	return nackeds
+}
+
+func (n *negativeAck) checkRestrictExpire() {
+	expired := []types.NodeID{}
+	now := time.Now()
+	for h, t := range n.restricteds {
+		if now.Sub(t) >= n.timeExpire {
+			expired = append(expired, h)
+		}
+	}
+	for _, h := range expired {
+		delete(n.restricteds, h)
+	}
+}
+
+func (n *negativeAck) restrict(nid types.NodeID) {
+	if _, exist := n.restricteds[nid]; !exist {
+		n.restricteds[nid] = time.Now().UTC()
+		n.lockedVotes[nid] = map[types.NodeID]struct{}{}
+		for h := range n.lastVotes[nid] {
+			n.lockedVotes[nid][h] = struct{}{}
+		}
+	}
+}
+
+func (n *negativeAck) getRestrictedNodes() map[types.NodeID]struct{} {
+	n.checkRestrictExpire()
+	ret := map[types.NodeID]struct{}{}
+	for h := range n.restricteds {
+		ret[h] = struct{}{}
+	}
+	return ret
+}
+
+func (n *negativeAck) setTimeDelay(t time.Duration) {
+	n.timeDelay = t
+}
+
+func (n *negativeAck) setTimeExpire(t time.Duration) {
+	n.timeExpire = t
+}
+
+func (n *negativeAck) addNode(nid types.NodeID) {
+	n.numOfNodes++
+	n.lastVotes[nid] = make(map[types.NodeID]struct{})
+	n.lockedVotes[nid] = make(map[types.NodeID]struct{})
+
+	newTimeDiff := make(map[types.NodeID]map[types.NodeID]time.Time)
+	for h := range n.timeDiffs {
+		newTimeDiff2 := make(map[types.NodeID]time.Time)
+		for hh := range n.timeDiffs {
+			newTimeDiff2[hh] = time.Time{}
+		}
+		newTimeDiff[h] = newTimeDiff2
+	}
+	n.timeDiffs[nid] = newTimeDiff
+	for h := range n.timeDiffs {
+		n.timeDiffs[h][nid] = make(map[types.NodeID]time.Time)
+	}
+}
+
+func (n *negativeAck) deleteNode(nid types.NodeID) {
+	n.numOfNodes--
+
+	delete(n.timeDiffs, nid)
+
+	for h := range n.lastVotes {
+		delete(n.lastVotes[h], nid)
+	}
+	delete(n.lastVotes, nid)
+	delete(n.lockedVotes, nid)
+
+	for h := range n.timeDiffs {
+		delete(n.timeDiffs[h], nid)
+		for hh := range n.timeDiffs[h] {
+			delete(n.timeDiffs[h][hh], nid)
+		}
+	}
+
+	delete(n.restricteds, nid)
+}