Module sp_npos_elections::reduce

source ·
Expand description

Rust implementation of the Phragmén reduce algorithm. This can be used by any off chain application to reduce cycles from the edge assignment, which will result in smaller size.

Notions

  • m: size of the committee to elect.
  • k: maximum allowed votes (16 as of this writing).
  • nv ∈ E means that nominator n ∈ N supports the election of candidate v ∈ V.
  • A valid solution consists of a tuple (S, W) , where S ⊆ V is a committee of m validators, and W : E → R ≥ 0 is an edge weight vector which describes how the budget of each nominator n is fractionally assigned to n ’s elected neighbors.
  • E_w := { e ∈ E : w_e > 0 }.

Algorithm overview

We consider the input edge weight vector w as a directed flow over E_w , where the flow in each edge is directed from the nominator to the validator. We build w′ from w by removing circulations to cancel out the flow over as many edges as possible, while preserving flow demands over all vertices and without reverting the flow direction over any edge. As long as there is a cycle, we can remove an additional circulation and eliminate at least one new edge from E_w′ . This shows that the algorithm always progresses and will eventually finish with an acyclic edge support. We keep a data structure that represents a forest of rooted trees, which is initialized as a collection of singletons – one per vertex – and to which edges in E_w are added one by one, causing the trees to merge. Whenever a new edge creates a cycle, we detect it and destroy it by removing a circulation. We also run a pre-computation which is designed to detect and remove cycles of length four exclusively. This pre-computation is optional, and if we skip it then the running time becomes O (|E_w| ⋅ m), so the pre-computation makes sense only if m >> kand|E_w| >> m^2`.

Resources:

  1. https://hackmd.io/JOn9x98iS0e0DPWQ87zGWg?view

Functions