Skip to content

Implement weighted voting

Patrick Steinhardt requested to merge pks-tx-weighted-voting into master

In order to make better use of reference transactions, it's essential to have a voting mechanism that is able to reach a quorum even if a subset of voters failed to show up or disagreed with the result. This is most helpful e.g. in our concept of primary/secondaries, where we can for example establish the policy that only the primary has a voting right while all the others don't or that at least primary and another node need to agree on the result. This is now made possible by introducing weighted voting to the transaction manager.

The mechanism is quite simple: given a set of voters, each voter is assigned a weight in the range [0,maxInt]. Only when the accumulated weight of all voters for a given item exceeds a certain threshold will the transaction be committed. If the threshold is lower than the accumulated weight or if any node has a zero weight, then a certain subset of nodes may fail in the process and will get an "abort" message, while the others get a "commit" message.

In order to enable somewhat flexible strategies, the caller is allowed to choose a threshold. There are two important limitations, though:

- The threshold may not exceed the accumulated weight of all nodes.
  If it did, then no matter how the voters vote, the transaction
  would always be aborted.

- The threshold always needs to be at least `ceil(weight(nodes)/2)`.
  If it's lower than that, then a transaction may reach multiple
  quorums and thus commit different results.

Note that the resulting voting code is quite complex, which mostly stems from the fact that we need to make sure that the channel signaling that the transaction has reached quorum doesn't get closed twice. We thus need to ensure two properties:

- The first voter casting a vote that causes it to exceed the
  threshold will close the channel. All the other voters will check
  whether any vote exists that exceeds the threshold already, in
  which case they know not to close the channel.

- In case no quorum is reached, the last node to cast its vote will
  close the channel to signal that all participants are done with
  the process. As no voter is allowed to cast votes multiple times,
  this is safe.

Together, these two conditions suffice to make sure that there's no way the channel can be closed twice.

Merge request reports