  Redundancy is commonly used to guarantee continued functionality in networked
systems. However, often many nodes are vulnerable to the same failure or
adversary. A "backup" path is not sufficient if both paths depend on nodes
which share a vulnerability.For example, if two nodes of the Internet cannot be
connected without using routers belonging to a given untrusted entity, then all
of their communication-regardless of the specific paths utilized-will be
intercepted by the controlling entity.In this and many other cases, the
vulnerabilities affecting the network are disjoint: each node has exactly one
vulnerability but the same vulnerability can affect many nodes. To discover
optimal redundancy in this scenario, we describe each vulnerability as a color
and develop a "color-avoiding percolation" which uncovers a hidden
color-avoiding connectivity. We present algorithms for color-avoiding
percolation of general networks and an analytic theory for random graphs with
uniformly distributed colors including critical phenomena. We demonstrate our
theory by uncovering the hidden color-avoiding connectivity of the Internet. We
find that less well-connected countries are more likely able to communicate
securely through optimally redundant paths than highly connected countries like
the US. Our results reveal a new layer of hidden structure in complex systems
and can enhance security and robustness through optimal redundancy in a wide
range of systems including biological, economic and communications networks.
