agreement.go 2.45 KB
Newer Older
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
1
2
3
package election

import (
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
4
	"errors"
5
	"fmt"
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
6
	"log"
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
7
8
	"sync"

Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
9
	"github.com/gonum/stat/combin"
Anders Jensen Løvig's avatar
Merge    
Anders Jensen Løvig committed
10
	"github.com/google/uuid"
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
11
12
)

13
14
15
16
17
18
19
20
type BallotList map[string]uuid.UUID

type Agreement struct {
	sync.Mutex

	// The minimum servers required for being able to tally
	required int
	// Map of ballot lists receveid from servers
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
21
	ourList     BallotList
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
	ballotLists map[UniqueID]BallotList
}

func NewAgreement(required int) *Agreement {
	return &Agreement{
		Mutex:       sync.Mutex{},
		required:    required,
		ballotLists: make(map[UniqueID]BallotList),
	}
}

func (a *Agreement) AddList(serverID UniqueID, ballotList map[string]uuid.UUID) error {
	a.Lock()
	defer a.Unlock()

	if _, ok := a.ballotLists[serverID]; ok {
		return fmt.Errorf("server %s already sent ballot list", serverID)
	}

	a.ballotLists[serverID] = ballotList
	return nil
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
45
46
47
func (a *Agreement) TallyList() ([]uuid.UUID, error) {
	a.Lock()
	defer a.Unlock()
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
48
49

	// First create a list of received ballot lists
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
50
51
52
	bls := make([]BallotList, 0, len(a.ballotLists))
	for _, b := range a.ballotLists {
		bls = append(bls, b)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
53
54
	}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
55
	// Find the maximum subset
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
56
	hashes := MaxSubset(a.required, bls)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
57
58
59
	if len(hashes) == 0 {
		return nil, errors.New("cannot agree on ballots")
	}
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
60

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
61
	// We know create a list of ballots we have in the subset.
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
62
63
64
65
	list := make([]uuid.UUID, 0, len(a.ourList))
	for h := range hashes {
		if id, ok := a.ourList[h]; ok {
			list = append(list, id)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
66
			delete(hashes, h) // Delete hashes that we have.
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
67
68
69
		}
	}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
70
	// If hashes is non-empty then we are not part of the max-subset.
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
71
72
	if len(hashes) != 0 {
		return nil, fmt.Errorf("missing %d ballots to tally", len(hashes))
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
73
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
74
75

	return list, nil
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
76
}
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
77

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
78
79
func MaxSubset(t int, ballotLists []BallotList) map[string]bool {
	n := len(ballotLists)
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
80
	combis := combin.Combinations(n, t)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
81
82
	log.Printf("N: %d, combis: %d\n", n, len(combis))
	subsets := make([]map[string]bool, len(combis), n)
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
83
	for i, ls := range combis {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
84
		sets := make([]BallotList, 0, len(ls))
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
85
		for _, i := range ls {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
86
			sets = append(sets, ballotLists[i])
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
87
88
89
90
91
92
93
94
95
96
97
98
		}
		subsets[i] = Intersection(sets)
	}
	max := 0
	for i := 0; i < len(subsets); i++ {
		if len(subsets[i]) > max {
			max = i
		}
	}
	return subsets[max]
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
99
100
func Intersection(superset []BallotList) map[string]bool {
	section := make(map[string]int, len(superset[0]))
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
101
	for _, set := range superset {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
102
103
		for hash := range set {
			section[hash]++
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
104
105
		}
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
106
107
	set := make(map[string]bool)
	for hash, num := range section {
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
108
		if num >= len(superset) {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
109
			set[hash] = true
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
110
111
		}
	}
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
112
	return set
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
113
}