The article seemed well done, the problem (from a information theory / network graph) though seemed weighted towards blockchain-like assumptions. This is fine, as more information needs to be seeded on this.
For those interested in the title's question:
Coordination might seem like the hard problem, but it is only hard because the majority of us in this community made it hard by using immutable data structures. If we use mutable data structures (you know my bias, but it is possible with https://github.com/amark/gun , proof: Mitra at Internet Archive integrated it in 1 week, now decentralized IA runs on GUN), we get some other problems but they are less than O(log N) in complexity.
Here is why coordination on immutability is hard:
O(N^2)
Just sit and think about it.
Intuitively it makes sense:
If I have an index to make something fast, and if it is immutable.
When I "update" the index, I have to create a new index.
Now the old index can't find the new index.
Therefore, I need to index the index, etc.
Repeat.
Therefore, as long as the web never changes, a decentralized immutable web will eventually be fast, but it must be true that if while the decentralized web changes, it will be hard.
This is not true if you can do decentralized mutable data. Check out our work! I hope this comment added novel insight to your day. :) If it did, let me buy you coffee next time you are in town. Cheers!