Apparaît dans la collection : 2016 - T1 - WS1 - Distributed computation and communication theme

In many practical settings, a group of clients needs to exchange data over a shared broadcast channel. The goal of cooperative data exchange problem is to find a schedule and an encoding scheme that minimize the total number of transmissions. We focus a wide range of practical settings in which the communication is performed in the presence of unreliable clients as well as in the presence of active and passive adversaries. In such settings, the problem of finding an efficient code is computationally intractable (NP-hard). Accordingly, we present approximation schemes with provable performance guarantees. We also focus on the design of coding schemes that achieve weak security, i. e. , prevent the adversary from being able to obtain information about any individual file in the system. The weak security is a low-overhead light-weight approach for protecting users’ data. In contrast to traditional information-theoretic and cryptographic tools, it does not require an exchange of secure keys and does not reduce the capacity of the network. We conjecture that it is possible to linearly transform a Vandermonde matrix to obtain a weakly secure code over a small field. This conjecture admits a number of reformulations that lead to interesting conjectures in algebraic geometry, abstract algebra and number theory.