-
Notifications
You must be signed in to change notification settings - Fork 13
/
fairness.go
103 lines (90 loc) · 3.49 KB
/
fairness.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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package distsys
import (
"fmt"
"math/rand"
)
// FairnessCounter is an abstraction over policies for MPCal's non-deterministic
// branch selection. See ArchetypeInterface.NextFairnessCounter.
type FairnessCounter interface {
// BeginCriticalSection will be called once per critical section, and should
// contain any necessary set-up for that critical section's execution.
BeginCriticalSection(pc string)
// NextFairnessCounter may be called repeatedly within a critical section,
// with distinct ids per distinct branching point.
NextFairnessCounter(id string, ceiling uint) uint
}
type FairnessCounterMaker func() FairnessCounter
type roundRobinFairnessCounterRecord struct {
id string
count, ceiling uint
}
type roundRobinFairnessCounter struct {
pc string
counterStack []roundRobinFairnessCounterRecord
counterIdx int
}
var _ FairnessCounter = &roundRobinFairnessCounter{}
// RoundRobinFairnessCounterMaker produces a FairnessCounter that follows a
// round-robin pattern.
// This process is similar to BigInt incrementation, but also tracking branch
// identifiers and trying to be robust to changes in the ceiling value (which
// may happen if we are exploring selections from a set whose cardinality
// changes).
func RoundRobinFairnessCounterMaker() FairnessCounterMaker {
return func() FairnessCounter {
return &roundRobinFairnessCounter{}
}
}
func (cnt *roundRobinFairnessCounter) BeginCriticalSection(pc string) {
cnt.counterIdx = 0
if pc != cnt.pc { // if different pc, reset everything
cnt.counterStack = cnt.counterStack[:0]
cnt.pc = pc
}
// "increment" the current counter, but make sure to explore the
// "furthest-along" state first this is important because not all execution
// paths will get "that far", so exploring "earlier" state first can skip
// branches.
counterStack := cnt.counterStack
var carry uint = 1
for idx := len(counterStack) - 1; idx >= 0; idx-- {
count, ceiling := counterStack[idx].count, counterStack[idx].ceiling
count += carry
carry = 0
if count >= ceiling {
carry = count / ceiling
count = count % ceiling
}
counterStack[idx].count = count
}
}
func (cnt *roundRobinFairnessCounter) NextFairnessCounter(id string, ceiling uint) uint {
idx := cnt.counterIdx
cnt.counterIdx++
if idx > len(cnt.counterStack) {
panic(fmt.Errorf("bad state: index %d is invalid for stack %v", idx, cnt.counterStack))
}
// if the id or ceiling don't match, drop the rest of the stack as we have
// shifted nested branches / changed cardinality.
// note: the cardinality part optimises a case where element selection is
// looped with element removal, or a set selection is otherwise
// "disturbed"; no sense in traversing more than the first element if
// the set has been "freshened" ... and it also makes increment logic
// conceptually simpler, as we can "trust" the stored ceiling value.
if idx < len(cnt.counterStack) && (cnt.counterStack[idx].id != id || cnt.counterStack[idx].ceiling != ceiling) {
cnt.counterStack = cnt.counterStack[:idx]
}
// if we are top of stack, initialise to a random value
if idx == len(cnt.counterStack) {
cnt.counterStack = append(cnt.counterStack, roundRobinFairnessCounterRecord{
id: id,
count: uint(rand.Uint32()) % ceiling,
ceiling: ceiling,
})
}
countToReturn := cnt.counterStack[idx].count
if countToReturn >= ceiling {
panic(fmt.Errorf("bad state: tried to return count %d, which doesn't fit ceiling %d", countToReturn, ceiling))
}
return countToReturn
}