The one-out-of-k retrieval problem and linear network coding
Giuseppe Bianchi - Dipartimento di Ingegneria Elettronica, Università degli Studi di Roma - Tor Vergata, Via del Politecnico, 1 00133 - Roma, Italy (email)
Abstract: In this paper we show how linear network coding can reduce the number of queries needed to retrieve one specific message among $k$ distinct ones replicated across a large number of randomly accessed nodes storing one message each. Without network coding, this would require $k$ queries on average. After proving that no scheme can perform better than a straightforward lower bound of $0.5k$ average queries, we propose and asymptotically evaluate, using mean field arguments, a few example practical schemes, the best of which attains $0.794k$ queries on average. The paper opens two complementary challenges: a systematic analysis of practical schemes so as to identify the best performing ones and design guideline strategies, as well as the need to identify tighter, nontrivial, lower bounds.
Keywords: Delay tolerant network, linear network coding, fluid approximations, lower bounds, mean field arguments.
Received: December 2014; Revised: December 2015; Available Online: March 2016.
2015 Impact Factor.631