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

Giuseppe  Bianchi; Lorenzo  Bracciale; Keren  Censor-Hillel; Andrea  Lincoln; Muriel  Médard

doi:10.3934/amc.2016.10.95

Article Contents

2016, Volume 10, Issue 1: 95-112. Doi: 10.3934/amc.2016.10.95

This issue Previous Article On skew polynomial codes and lattices from quotients of cyclic division algebras Next Article On applications of orbit codes to storage

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

1.
Dipartimento di Ingegneria Elettronica, Università degli Studi di Roma - Tor Vergata, Via del Politecnico, 1 00133 - Roma
2.
Department of Computer Science, Technion, Haifa 32000
3.
160 Sunrise Dr, Woodside, CA 94062
4.
Room 36-512F, 77 Massachusetts Avenue, Cambridge, MA 02139

Received: December 2014

Revised: December 2015

Published: February 2016

Abstract / Introduction Related Papers Cited by

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:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

References

[1]	F. M. Buckley and P. K. Pollett, Limit theorems for discrete-time metapopulation models, Probab. Surveys, 7 (2010), 53-83.doi: 10.1214/10-PS158.
[2]	L. Chen, T. Ho, S. H. Low, M. Chiang and J. C. Doyle, Optimization based rate control for multi-cast with network coding, in 26th IEEE Int. Conf. Comp. Commun. 2007, 1163-1171.
[3]	R. W. R. Darlings and J. R. Norris, Differential equation approximations for Markov chains, Probab. Surveys, 5 (2008), 37-79.doi: 10.1214/07-PS121.
[4]	F. De Pellegrini, R. El-Azouzi and F. Albini, Interplay of contact times, fragmentation and coding in DTNs, in 11th Int. Symp. Modeling Optim. Mobile Ad Hoc Wireless Networks, 2013, 580-587.
[5]	S. Deb, M. Medard and C. Choute, Algebraic gossip: a network coding approach to optimal multiple rumor mongering, IEEE Trans. Inf. Theory, 52 (2006), 2486-2507.doi: 10.1109/TIT.2006.874532.
[6]	A. G. Dimakis V. Prabhakaran and K. Ramchandran, Decentralized erasure codes for distributed networked storage, IEEE Trans. Inf. Theory, 52 (2006), 2809-2816.doi: 10.1109/TIT.2006.874535.
[7]	P. Erdős and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960), 17-61.
[8]	L. Keller, E. Atsan, K. Argyraki and C. Fragouli, SenseCode: Network coding for reliable sensor networks, ACM Trans. Sen. Netw., 9 (2013), #25.doi: 10.1145/2422966.2422982.
[9]	T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Probab., 7 (1970), 49-58.
[10]	Y. Lin, B. Li and B. Liang, Efficient network coded data transmissions in disruption tolerant networks, in The 27th IEEE Conf. Comp. Commun., 2008, 2180-2188.doi: 10.1109/INFOCOM.2008.210.
[11]	M. Luby, LT codes, in The 43rd Ann. IEEE Symp. Found. Comp. Sci., 2002, 271-280.doi: 10.1109/SFCS.2002.1181950.
[12]	A. Oppenheim, R. Schafer and J. Buck, Discrete-Time Signal Processing, Printice Hall Inc., New Jersey, 1989.
[13]	L. Sassatelli and M. Medard, Inter-session network coding in delay-tolerant networks under Spray-and-Wait routing, Model. Optim. Mob. Ad Hoc Wirel. Netw., 10 (2012), 103-110.
[14]	J. Widmer and J. Y. Le Boudec, Network coding for efficient communication in extreme networks, in ACM SIGCOMM Workshop Delay-Tolerant Networking, 2005, 284-291.
[15]	S. K. Yoon and Z. J. Haas, Application of linear network coding in delay tolerant networks, in Second Int. Conf. Ubiquitous Future Networks (ICUFN), 2010, 338-343.
[16]	X. Zhang, G. Neglia, J. Kurose, D. Towsley and H. Wang, Benefits of network coding for unicast application in disruption-tolerant networks, IEEE/ACM Trans. Networking, 21 (2013), 1407-1420.doi: 10.1109/TNET.2012.2224369.