Crate sp_npos_elections

A set of election algorithms to be used with a substrate runtime, typically within the staking sub-system. Notable implementation include:

• seq_phragmen: Implements the Phragmén Sequential Method. An un-ranked, relatively fast election method that ensures PJR, but does not provide a constant factor approximation of the maximin problem.
• phragmms: Implements a hybrid approach inspired by Phragmén which is executed faster but it can achieve a constant factor approximation of the maximin problem, similar to that of the MMS algorithm.
• balance: Implements the star balancing algorithm. This iterative process can push a solution toward being more “balanced”, which in turn can increase its score.

Terminology

This crate uses context-independent words, not to be confused with staking. This is because the election algorithms of this crate, while designed for staking, can be used in other contexts as well.

Voter: The entity casting some votes to a number of Targets. This is the same as Nominator in the context of staking. Target: The entities eligible to be voted upon. This is the same as Validator in the context of staking. Edge: A mapping from a Voter to a Target.

The goal of an election algorithm is to provide an ElectionResult. A data composed of:

• winners: A flat list of identifiers belonging to those who have won the election, usually ordered in some meaningful way. They are zipped with their total backing stake.
• assignment: A mapping from each voter to their winner-only targets, zipped with a ration denoting the amount of support given to that particular target.

// the winners.
let winners = vec![(1, 100), (2, 50)];
let assignments = vec![
    // A voter, giving equal backing to both 1 and 2.
    Assignment {
		who: 10,
		distribution: vec![(1, Perbill::from_percent(50)), (2, Perbill::from_percent(50))],
	},
    // A voter, Only backing 1.
    Assignment { who: 20, distribution: vec![(1, Perbill::from_percent(100))] },
];

// the combination of the two makes the election result.
let election_result = ElectionResult { winners, assignments };

The Assignment field of the election result is voter-major, i.e. it is from the perspective of the voter. The struct that represents the opposite is called a Support. This struct is usually accessed in a map-like manner, i.e. keyed by voters, therefore it is stored as a mapping called SupportMap.

Moreover, the support is built from absolute backing values, not ratios like the example above. A struct similar to Assignment that has stake value instead of ratios is called an StakedAssignment.

More information can be found at: https://arxiv.org/abs/2004.12990

Re-exports

• pub use reduce::reduce;
• pub use traits::IdentifierT;
• pub use traits::PerThing128;
• pub use balancing::*;
• pub use helpers::*;
• pub use phragmen::*;
• pub use phragmms::*;
• pub use pjr::*;

Modules

• balancing
  Balancing algorithm implementation.
• helpers
  Helper methods for npos-elections.
• node
  (very) Basic implementation of a graph node used in the reduce algorithm.
• phragmen
  Implementation of the sequential-phragmen election method.
• phragmms
  Implementation of the PhragMMS method.
• pjr
  Implements functions and interfaces to check solutions for being t-PJR.
• reduce
  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.
• traits
  Traits for the npos-election operations.

Structs

• Assignment
  A voter’s stake assignment among a set of targets, represented as ratios.
• BalancingConfig
  Utility struct to group parameters for the balancing algorithm.
• Candidate
  A candidate entity for the election.
• Edge
  A vote being casted by a Voter to a Candidate is an Edge.
• ElectionResult
  Final result of the election.
• ElectionScore
  The score of an election. This is the main measure of an election’s quality.
• StakedAssignment
  A voter’s stake assignment among a set of targets, represented as absolute values in the scale of ExtendedBalance.
• Support
  A structure to demonstrate the election result from the perspective of the candidate, i.e. how much support each candidate is receiving.
• Voter
  A voter entity.

Enums

• Error
  The errors that might occur in this crate and frame-election-provider-solution-type.

Traits

• EvaluateSupport
  Extension trait for evaluating a support map or vector.

Functions

• setup_inputs
  Converts raw inputs to types used in this crate.
• to_support_map
  Build the support map from the assignments.
• to_supports
  Same as to_support_map except it returns a flat vector.

Type Definitions

• BoundedSupports
  Same as Supports but bounded by B.
• CandidatePtr
  A pointer to a candidate struct with interior mutability.
• ExtendedBalance
  A type in which performing operations on vote weights are safe.
• SupportMap
  Linkage from a winner to their Support.
• Supports
  A target-major representation of the the election outcome.
• VoteWeight
  A type which is used in the API of this crate as a numeric weight of a vote, most often the stake of the voter. It is always converted to ExtendedBalance for computation.