New Proof Settles Decades-Old Bet About Connected Networks

Might be fruitful to apply this on p2p mesh networks. I suppose you should be able to make a model describing how the relationship between the fraction of byzantine nodes affects the probability distribution of connectedness. Then you could figure out what algorithm parameters would put you within desired bounds for tolerated ratios of byzantine.

Byzantine has I think been misused. It’s the least number of good members you need to be successful, not the best number. I think there’s a reason parliamentary systems have a supermajority rule for making certain kinds of changes and a simple majority for others and we should probably be doing the same when we model systems.

It is simple enough for an adversarial system to subvert some members via collusion and others via obstruction. Take something like Consul which can elect new members and remove old ones (often necessary in modern cloud architectures). What does 50.1% mean when the divisor can be changed?

And meshes are extremely weird because the whole point is to connect nodes that cannot mutually see each other. It is quite difficult to know for sure if you’re hallucinating the existence of a node two hops away from yourself. You’ve never seen each other, except maybe when the weather was just right one day months ago.

> Byzantine has I think been misused. It’s the least number of good members you need to be successful, not the best number.

Could you elaborate? It sounds like you are talking more about challenges of distributed consensus (elections, raft). What I have in mind is distributed peering algorithms for decentralized networks. No consensus, elections, or quorum required. You may wish to run consensus algos on top of such networks but that's one layer up, if you will.

Byzantine in the context of unpermissioned networks is often explained as the sybil problem, which maps to the issues you mention.

Applying OP to this setting wouldn't mitigate that but I'm thinking it can be used as a framework to model and reason about these systems. Perhaps even prove certain properties (assuming some form of sybil resistance mechanism, I guess).

A distributed network still needs to figure out either the best route or best routes to get packets into and out of the network. Even if you assume cryptography to deal with the MITM issue.

Think about how BGP makes the front page news about once every couple of years.