DAWN-665 ⁃ An algorithm and a coordination mechanism are needed for BPs to schedule each round

[blockone-syncclient]

Within each round the BPs need soft consensus on whose turn comes when. Solving this requires two goals be served:

1. a good-enough Traveling Salesman Problem solution that minimizes latency
2. pseudo randomness to reduce attack vector

The inputs to this will be the latencies between the 21 block producers with respect to each other, or, a list from each BP to the 3 - 5 other BPs that are closest, or, some other input that we find useful.

There also may need to be some 'short term memory' so we can verify that a new schedule is different from the last N recent prior schedules, where N is probably 5 to 25.

This can be implemented by a daemon separate from the 'eosiod' - it would do something like this:

1. Consult the chain or mongo and get a list of the top N (121?) BP candidates
2. Maintain a list of those candidates and the latencies between me and them
3. Publish this list to other daemons who ask
4. When I am 'tapped' and told I'll be a BP in the NEXT round (or some future round), I am also told who my 20 BP partners will be in that round.
5. Having been 'tapped' I create a matrix of 21-x-21 latencies between all the BPs in that future round
6. I use that matrix to determine 20 possible Traveling Salesman Problem routes (probably a mix of 'clockwise' and 'counterclockwise' as one looks at the Earth downward from the North Pole)
7. I arrange the list of 20 routes in a pseudo-random order using a known algorithm and seeded by the hash of the next-to-last irreversible block (or something deterministic but unanticipatable)
8. I publish the list of 20 routes to my 20 BP partners for the coming round, and we achieve agreement and push these into the blockchain so it's known for a given round who is supposed to do what when
9. We use each of those routes one after another, round after round, until round 18
10. With 2 rounds to go, we 'tap' another BP who we know will be making blocks in future, and he has 2 rounds of time to get his 20 routes created

Something like the above should work.

[abourget]

I propose something along those lines:

1. A separate daemon measures latencies of incoming blocks for each other BPs. I would assume that if you're close to a node, you will receive its blocks faster than the nodes you're further from. This also means that BP operators will want to have good connectivity to other block producers. My understanding is that this will be done manually (no peer discovery), at least for the June release (through /v1/net/connect or explicit config.ini remote-peer statements).
2. From time to time, the BP would sign a transaction with a map of "other_bp": latency_in_ms. Ideally that transaction would have a different permission than active, so you can have less important keys manage that system.
3. That would be saved on-chain.
4. Each round, a traveling salesman would run with the on-chain data, adding a small dose of fuzziness to the weights/latencies (e.g. based on previous blocks' hash), which would determine the next schedule for everyone.

This would allow a much simpler setup, would make sure the agreement doesn't need to be made off-chain and some third-party consensus algorithms implemented. It wouldn't require the latency tool to even query the blockchain, simply to push transactions. It would allow any block producer that is voted in to know the schedule directly. It wouldn't provide for schedules in advance, but we're sure we'd always have a schedule on-demand, directly on chain, perhaps starting a little stretched, but after a few minutes (with incoming latencies reports), better routes would emerge.

I would also assume that if a block producer never publishes latencies.. then it could be deemed less "capable", and potentially be downvoted.

We could monitor the published latencies, and see if one always says he's close to everyone, while everyone else says he's far.. I'd be curious to see such data.. see if one tries to trick the system.. but at the same time, if you're part of the 21, you don't really have an incentive to be first or last.. you'll be in the round in any case. Anyone sees opportunities to game such a system ?

[jgiszczak]

Note that the existing P2P protocol includes time_message that can be exchanged between any two directly connected full nodes to calculate their latency. It uses the std::chrono timestamp format, which in all current implementations is at least 64 bits, allowing nanosecond resolution.

[abourget]

ok, very nice!

[abourget]

@jgiszczak I see that time_message is sent .. but can it be requested ? Like in a ping/pong fashion?

Otherwise, this would imply NTP/wall-clock to be in sync like crazy.

Has the thinking evolved on that front ? We have implemented the P2P layer in Go, so we can build a proxy that would handle pinging and signing of tx to the chain with a map of latencies.. Having a contract on-chain to handle the shuffling based on such latencies is up for grabs right now. But since it's pretty core, I'd like to let B1 decide on it..

[jgiszczak]

Sending a time_message is effectively sending a ping. It will trigger a return time_message any time the origin timestamp is zero.

[brianjohnson5972]

@wanderingbort @heifner This looks like a completed or OBE issue. If I don't hear from you I will close it.

[brianjohnson5972]

The code changed considerably from this point, so it is OBE (Overcome By Events).