-
Notifications
You must be signed in to change notification settings - Fork 0
/
median_time.go
84 lines (72 loc) · 2.41 KB
/
median_time.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package vecmt
import (
"fmt"
"sort"
"github.com/corex-mn/corex-base/hash"
"github.com/corex-mn/corex-base/inter/idx"
"github.com/corex-mn/corex-base/inter/pos"
"github.com/corex-mn/go-corex/inter"
)
// medianTimeIndex is a handy index for the MedianTime() func
type medianTimeIndex struct {
weight pos.Weight
creationTime inter.Timestamp
}
// MedianTime calculates weighted median of claimed time within highest observed events.
func (vi *Index) MedianTime(id hash.Event, defaultTime inter.Timestamp) inter.Timestamp {
vi.Engine.InitBranchesInfo()
// Get event by hash
_before := vi.Engine.GetMergedHighestBefore(id)
if _before == nil {
vi.crit(fmt.Errorf("event=%s not found", id.String()))
}
before := _before.(*HighestBefore)
honestTotalWeight := pos.Weight(0) // isn't equal to validators.TotalWeight(), because doesn't count cheaters
highests := make([]medianTimeIndex, 0, len(vi.validatorIdxs))
// convert []HighestBefore -> []medianTimeIndex
for creatorIdxI := range vi.validators.IDs() {
creatorIdx := idx.Validator(creatorIdxI)
highest := medianTimeIndex{}
highest.weight = vi.validators.GetWeightByIdx(creatorIdx)
highest.creationTime = before.VTime.Get(creatorIdx)
seq := before.VSeq.Get(creatorIdx)
// edge cases
if seq.IsForkDetected() {
// cheaters don't influence medianTime
highest.weight = 0
} else if seq.Seq == 0 {
// if no event was observed from this node, then use genesisTime
highest.creationTime = defaultTime
}
highests = append(highests, highest)
honestTotalWeight += highest.weight
}
// it's technically possible honestTotalWeight == 0 (all validators are cheaters)
// sort by claimed time (partial order is enough here, because we need only creationTime)
sort.Slice(highests, func(i, j int) bool {
a, b := highests[i], highests[j]
return a.creationTime < b.creationTime
})
// Calculate weighted median
halfWeight := honestTotalWeight / 2
var currWeight pos.Weight
var median inter.Timestamp
for _, highest := range highests {
currWeight += highest.weight
if currWeight >= halfWeight {
median = highest.creationTime
break
}
}
// sanity check
if currWeight < halfWeight || currWeight > honestTotalWeight {
vi.crit(fmt.Errorf("median wasn't calculated correctly, median=%d, currWeight=%d, totalWeight=%d, len(highests)=%d, id=%s",
median,
currWeight,
honestTotalWeight,
len(highests),
id.String(),
))
}
return median
}