Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

 Citation:

•  [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.