sp-npos-elections

一组用于 Substrate 运行时的选举算法，通常在质押子系统中使用。显著的实现包括

• seq_phragmen：实现了 Phragmén 顺序方法。一种无等级、相对较快的选举方法，确保了 PJR，但并不提供最大最小问题的常数因子近似。
• phragmms：实现了受Phragmén启发的混合方法，执行速度更快，但它可以实现对最大最小问题的常数因子近似，类似于MMS算法。
• balance_solution：实现了星形平衡算法。这个迭代过程可以将解决方案推向更加平衡，从而提高其分数。

术语

此crate使用与上下文无关的单词，不要与抵押混淆。这是因为该crate的选举算法虽然为抵押而设计，但也可以用于其他上下文。

Voter：对多个Targets投出一些选票的实体。在抵押的上下文中，这与Nominator相同。Target：有资格被投票的实体。在抵押的上下文中，这与Validator相同。Edge：从Voter到Target的映射。

选举算法的目的是提供ElectionResult。由以下组成的数据

• winners：获胜者的标识符的扁平列表，通常按某种有意义的顺序排列。它们与它们的总支持股份一起压缩。
• assignment：将每个投票者映射到他们的仅获胜者目标，与表示对该特定目标所提供支持的比率一起压缩。

// 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 };

选举结果的Assignment字段是投票者多数的，即它从投票者的角度来看。表示相反的结构的struct称为Support。这个struct通常以类似映射的方式访问，即以投票者为键，因此它存储为名为SupportMap的映射。

此外，支持是从绝对支持值构建的，而不是像上面示例中那样的比率。具有股份值而不是比率的类似于Assignment的struct称为StakedAssignment。

更多信息请参阅： https://arxiv.org/abs/2004.12990

许可证：Apache-2.0