Crate tp_npos_elections 

A set of election algorithms to be used with a tetcore 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 balances, 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, therefor 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

Macros

generate_solution_type

Generates a struct to store the election result in a small way. This can encode a structure which is the equivalent of a tp_npos_elections::Assignment<_>.

Structs

Assignment

A voter’s stake assignment among a set of targets, represented as ratios.

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.

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 the this crate and compact.

Traits

CompactSolution

A common interface for all compact solutions.

EvaluateSupport

Extension trait for evaluating a support map or vector.

FlattenSupportMap

Helper trait to convert from a support map to a flat support vector.

IdentifierT

an aggregator trait for a generic type of a voter/target identifier. This usually maps to tetcore’s account id.

PerThing128

Aggregator trait for a PerThing that can be multiplied by u128 (ExtendedBalance).

TupleRef

A common wrapper trait for both (&A, &B) and &(A, B).

Functions

assignment_ratio_to_staked

Converts a vector of ratio assignments into ones with absolute budget value.

assignment_ratio_to_staked_normalized

Same as assignment_ratio_to_staked and try and do normalization.

assignment_staked_to_ratio

Converts a vector of staked assignments into ones with ratio values.

assignment_staked_to_ratio_normalized

Same as assignment_staked_to_ratio and try and do normalization.

balance

Balance the weight distribution of a given voters at most iterations times, or up until the point where the biggest difference created per iteration of all stakes is tolerance. If this is called with tolerance = 0, then exactly iterations rounds will be executed, except if no change has been made (difference = 0).

is_score_better

Compares two sets of election scores based on desirability and returns true if this is better than that.

phragmms

Execute the phragmms method.

reduce

Reduce the given Vec<StakedAssignment<IdentifierT>>. This removes redundant edges from without changing the overall backing of any of the elected candidates.

seq_phragmen

Execute sequential phragmen with potentially some rounds of balancing. The return type is list of winners and a weight distribution vector of all voters who contribute to the winners.

seq_phragmen_core

Core implementation of seq-phragmen.

to_support_map

Build the support map from the winners and assignments.

to_supports

Same as to_support_map except it calls FlattenSupportMap on top of the result to return a flat vector.

to_without_backing

consumes a vector of winners with backing stake to just winners.

Type Aliases

CandidatePtr

A pointer to a candidate struct with interior mutability.

ElectionScore

The score of an assignment. This can be computed from the support map via EvaluateSupport::evaluate.

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.

WithApprovalOf

A winner, with their respective approval stake.