Optimize finality tracker to handle much longer period

[rphmeier]

After #1619

The finality tracker keeps track of what N recent block authors think the highest finalized block height was ("opinions"). If the median slips too far in the past, a callback to other modules is made.

Currently, all the recent opinions are kept in two Vec<Number> of length N in storage. One is sorted by recency, and the other is sorted by block number. This is very inefficient and doesn't scale to large N -- where we would probably want N to be 1,000 to 10,000 or even higher.

One approach for this optimization is to select a smaller number K (~100?) and split up the recent opinions into a doubly-linked list of Vec<Number> with length 0..2K. When a sub-list reaches length 2K, it is split into two smaller lists of length K. A combination of binary and linear search can be used to find the correct place to insert into the block number set.

[marcio-diaz]

Are we keeping recent block heights only to calculate the median? Is it possible to use an approximation of it? In this case, something like P2 Algorithm for Dynamic Statistical Computing Calculation of Quantiles may be used to approximate it (and work well with outliers).

[rphmeier]

I think it could be done with an approximation, as long as everyone is using roughly the same approximation. We should consult with @AlistairStewart about it first -- the main thing is to make sure that it's not gameable somehow -- if 50% or more of recent block authors are honest and the GRANDPA voters are online, the median heuristic should not reflect it as being far in the past.

[AlistairStewart]

I'd be wary of approximation algorithms that don't give robust enough guarantees. It'd definitely be better to use the actual median. Though maybe some heuristics would be useful in accelerating the obvious binary search of an unsorted list algorithm.

[AlistairStewart]

Ah I see the linked paper is not an approximation but gives a heuristic for calculating the median fast for an unsorted list, which is what we'd want.

[gavofyork]

This doesn't sound like 1.0 material at all.

[andresilva]

The finality tracker has been removed and we're triggering forced changes manually through governance instead.