Crate tp_npos_elections[−][src]
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 morebalances
, 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 |
Structs
Assignment | A voter’s stake assignment among a set of targets, represented as ratios. |
Candidate | A candidate entity for the election. |
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 |
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_staked_to_ratio | Converts a vector of staked assignments into ones with ratio values. |
assignment_staked_to_ratio_normalized | Same as |
balance | Balance the weight distribution of a given |
is_score_better | Compares two sets of election scores based on desirability and returns true if |
phragmms | Execute the phragmms method. |
reduce | Reduce the given |
seq_phragmen | Execute sequential phragmen with potentially some rounds of |
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_without_backing | consumes a vector of winners with backing stake to just winners. |
Type Definitions
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
|
ExtendedBalance | A type in which performing operations on vote weights are safe. |
SupportMap | Linkage from a winner to their |
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 |
WithApprovalOf | A winner, with their respective approval stake. |