`a`
Advances in Mathematics of Communications (AMC)
 

The one-out-of-k retrieval problem and linear network coding

Pages: 95 - 112, Volume 10, Issue 1, February 2016      doi:10.3934/amc.2016.10.95

 
       Abstract        References        Full Text (404.3K)       Related Articles       

Giuseppe Bianchi - Dipartimento di Ingegneria Elettronica, Università degli Studi di Roma - Tor Vergata, Via del Politecnico, 1 00133 - Roma, Italy (email)
Lorenzo Bracciale - Dipartimento di Ingegneria Elettronica, Università degli Studi di Roma - Tor Vergata, Via del Politecnico, 1 00133 - Roma, Italy (email)
Keren Censor-Hillel - Department of Computer Science, Technion, Haifa 32000, Israel (email)
Andrea Lincoln - 160 Sunrise Dr, Woodside, CA 94062, United States (email)
Muriel Médard - Room 36-512F, 77 Massachusetts Avenue, Cambridge, MA 02139, United States (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.
Mathematics Subject Classification:  Primary: 58F15, 58F17; Secondary: 53C35.

Received: December 2014;      Revised: December 2015;      Available Online: March 2016.

 References