It’s an interesting idea, and zero-coordination is a nice property, but problems immediately spring to my mind, which is why I haven’t suggested something like that:
- There seems to be a real possibility for some buckets to never be processed by any service provider. Especially for a small network.
- There is still potentially a lot of duplication of work between service providers because (a) providers can’t coordinate buckets, and (b) bucket sizes do not take into account the number of providers which is also dynamic. This means the network will still not be optimally processing upgrades, which means the attack is lower-cost than it could be.
So I would turn this around and ask: what is wrong with the simple coordination approach I proposed above, that seemingly should result in near optimal coordinaton. I quote it here:
A simple improvement would be to add a message so that a prover can tell other peers “hey I’m working on Transaction X”, so they can ignore transaction X for some time, perhaps something like 10 minutes or 2 more blocks. After that if the transaction is still in their mempool (has not been included in a block) they might consider it again.
To answer my own question: there is a possibility that two or more providers begin working on an update before receiving the peer’s “I’m working on it message”. So if a given node is already working on an upgrade and receive’s notice that peer is also, the protocol would ideally have a way for those peers to further coordinate such that one of them abandons the upgrade and the other does not. However in practice, this may not be a common occurence, so I would say the situation could simply be logged initially, and then we could collect some data to see if it happens enough to be worth mitigating or not. And/or simulations could inform. Anyway, I believe there are various papers written about solving this class of problem.