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.