Attack-Resilient Multitree Data Distribution Topologies

We consider a scenario of information broadcast where a source node distributes data in parallel over a fixed number of trees spanning over a large audience of nodes. The trees used for data dissemination are called distribution topology. Particular implementations of this scenario are peer-to-peer live streaming systems. Encoding data partially redundant, nodes are satisfied as long as they receive packets in at least a certain portion of trees. Otherwise, they are called isolated. We study distribution topologies limiting the worst-case consequences of attacks suddenly removing nodes from the trees. In particular, we aim to minimize the maximum possible number of isolated nodes for each number of removed nodes. We show necessary conditions on distribution topologies closely approximating this goal. Then, we demonstrate that the attack-resilience of topologies adhering to these conditions is characterized by specific matrices that have to be Orthogonal Arrays of maximum strength. The computational complexity of finding such matrices for arbitrary dimensions is a long-standing research problem. Our results show that finding representatives of the studied distribution topologies is at least as hard as this problem.