Defect tolerance: fundamental limits and examples

This paper addresses the question of how to add redundancy to a collection of physical objects so that the overall system is more robust to failures. Physical redundancy can (generally) only be achieved by employing copy/substitute procedures. This is fundamentally different from information redundancy, where a single parity check simultaneously protects a large number of data bits against a single erasure. We propose a bipartite graph model of designing defect-tolerant systems where defective objects are repaired by reconnecting them to strategically placed redundant objects. The fundamental limits of this model are characterized under various asymptotic settings and both asymptotic and finite-size optimal systems are constructed. Mathematically, we say that a k by m bipartite graph corrects t defects over alphabet of size q if for every q-coloring of k left vertices there exists a coloring of m right vertices such that every left vertex is connected to at least t same-colored right vertices. We study the tradeoff between redundancy m/k and the total number of edges in the graph divided by k. The question is trivial when q ≥ k: the optimal solution is a simple t-fold replication. However, when q < k some non-trivial savings are possible by leveraging the inherent repetition of colors.