Robustness means that things keep working even after parts break down. In graph theory terms, for a network to be robust we need to make sure that as many people as possible can still communicate once an edge or vertex drops off the network. I suppose that means that we can talk about two different kinds of robustness – worst case and average. The worst case deals with things like “how many people would have to drop off the network to divide it into make at least 20% of the addresses unreachable”. The average scenario asks questions like, “if failures are random, then how many failures does it date for there to be a 10% probability that 20% of the network is unreachable”. Questions of the first kind tend to be more answerable via traditional algorithms – there’s a right answer, and we just have to ge tthe computer to act like a malicious adversary. The second kind is a bit more wily.
Questions involving randomness are pretty hard for us to deal with in CS. Our first instinct is to calculate every data point, but that quickly becomes impossible, so we have to settle for some kind of sampling – but how much is required? As a field, we don’t have a good handle on what random means, or even continuous math at all.
