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.