What is the difference between pallet_elections_phragmen and sp_npos_solution?

Question

Just breezing through the docs for both crates, I can see that they both provide an implementation of phragmen's election algorithm, where sp_npos_elections provides an additional PhragMMS and Balancing algorithms, which I assume are different ways of electing from a voter snapshot.

In the substrate code base, we can see that for election_provider_multi_phase config, it takes a Solver from frame_election_provider_support. I could only see pallet_election_phragmen however being used in the pallet_tips Config.

I am confused why two separate implementations of phragmen election would be provided. If I were to look at this code for the first time my guess would've been that the Solver type should be define like so type Solver = Elections where Elections -> pallet_election_phragmen. But apparently that's not the case.

So between frame_election_provider_support, sp_npos_elections, and pallet-elections-phragmen, which is appropriate for what scenario?

Answer 1

Here's an overview of all of the named crates, and how they relate to one another.

sp-npos-elections: This is a generic rust crate that just implements a bunch of algorithms, such as seq_phragmen, phragmms, and further optimizations like balancing.

frame-election-provider-support is the interface of using these elections within FRAME. it contains some types, traits, and abstractions around this. An important trait here is ElectionProvider. This is the trait that needs to be implemented for some type, so it can provide the NPoS election to pallet-staking, via type ElectionProvider.

election-provider-muli-phase is one opinionated implementation of ElectionProvider, which has extensive documentation in itself about what it does and how it does it. But end of the day, it can be plugged into pallet-staking as type ElectionProvider.

One of the details of election-provider-muli-phase is that it has miners that run on OffchainWorker threads of each block, and compute an election, under certain condition. type Solver will determine which algorithm we want to use for this case. The documentation for type Solver explains this further.

Alternatively, you can look into what other types implement ElectionProvider for more simpler ones.

Finally, pallet-elections-phragmen has nothing to do with any of this, and is a generic pallet capable of running onchain elections, and it is directly using sp-npos-elections::seq_phragmen. unlike election-provider-muli-phase which is quite complicated and has a lot of internal state, this one us quite simple. In reality, this can only be used for some small-scale election that happens onchain, like a council election in Polkadot.

This recent YouTube video is a great in-depth explanation of all of this.