# American Institute of Mathematical Sciences

February  2016, 10(1): 95-112. doi: 10.3934/amc.2016.10.95

## 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, Italy, Italy 2 Department of Computer Science, Technion, Haifa 32000, Israel 3 160 Sunrise Dr, Woodside, CA 94062, United States 4 Room 36-512F, 77 Massachusetts Avenue, Cambridge, MA 02139, United States

Received  December 2014 Revised  December 2015 Published  March 2016

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.
Citation: Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95
##### References:
 [1] F. M. Buckley and P. K. Pollett, Limit theorems for discrete-time metapopulation models,, Probab. Surveys, 7 (2010), 53. 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, (2007), 1163. [3] R. W. R. Darlings and J. R. Norris, Differential equation approximations for Markov chains,, Probab. Surveys, 5 (2008), 37. 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. [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. 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. 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. [8] L. Keller, E. Atsan, K. Argyraki and C. Fragouli, SenseCode: Network coding for reliable sensor networks,, ACM Trans. Sen. Netw., 9 (2013). 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. [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. doi: 10.1109/INFOCOM.2008.210. [11] M. Luby, LT codes,, in The 43rd Ann. IEEE Symp. Found. Comp. Sci., (2002), 271. doi: 10.1109/SFCS.2002.1181950. [12] A. Oppenheim, R. Schafer and J. Buck, Discrete-Time Signal Processing,, Printice Hall Inc., (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. [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. [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. [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. doi: 10.1109/TNET.2012.2224369.

show all references

##### References:
 [1] F. M. Buckley and P. K. Pollett, Limit theorems for discrete-time metapopulation models,, Probab. Surveys, 7 (2010), 53. 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, (2007), 1163. [3] R. W. R. Darlings and J. R. Norris, Differential equation approximations for Markov chains,, Probab. Surveys, 5 (2008), 37. 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. [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. 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. 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. [8] L. Keller, E. Atsan, K. Argyraki and C. Fragouli, SenseCode: Network coding for reliable sensor networks,, ACM Trans. Sen. Netw., 9 (2013). 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. [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. doi: 10.1109/INFOCOM.2008.210. [11] M. Luby, LT codes,, in The 43rd Ann. IEEE Symp. Found. Comp. Sci., (2002), 271. doi: 10.1109/SFCS.2002.1181950. [12] A. Oppenheim, R. Schafer and J. Buck, Discrete-Time Signal Processing,, Printice Hall Inc., (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. [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. [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. [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. doi: 10.1109/TNET.2012.2224369.
 [1] Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577 [2] Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145 [3] Easton Li Xu, Weiping Shang, Guangyue Han. Network encoding complexity: Exact values, bounds, and inequalities. Advances in Mathematics of Communications, 2017, 11 (3) : 567-594. doi: 10.3934/amc.2017044 [4] András Bátkai, Istvan Z. Kiss, Eszter Sikolya, Péter L. Simon. Differential equation approximations of stochastic network processes: An operator semigroup approach. Networks & Heterogeneous Media, 2012, 7 (1) : 43-58. doi: 10.3934/nhm.2012.7.43 [5] Ángela Jiménez-Casas, Aníbal Rodríguez-Bernal. Linear model of traffic flow in an isolated network. Conference Publications, 2015, 2015 (special) : 670-677. doi: 10.3934/proc.2015.0670 [6] Michael Herty, Mattia Zanella. Performance bounds for the mean-field limit of constrained dynamics. Discrete & Continuous Dynamical Systems - A, 2017, 37 (4) : 2023-2043. doi: 10.3934/dcds.2017086 [7] Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 [8] Reimund Rautmann. Lower and upper bounds to the change of vorticity by transition from slip- to no-slip fluid flow. Discrete & Continuous Dynamical Systems - S, 2014, 7 (5) : 1101-1109. doi: 10.3934/dcdss.2014.7.1101 [9] Maria Schonbek, Tomas Schonbek. Moments and lower bounds in the far-field of solutions to quasi-geostrophic flows. Discrete & Continuous Dynamical Systems - A, 2005, 13 (5) : 1277-1304. doi: 10.3934/dcds.2005.13.1277 [10] Katrin Gelfert. Lower bounds for the topological entropy. Discrete & Continuous Dynamical Systems - A, 2005, 12 (3) : 555-565. doi: 10.3934/dcds.2005.12.555 [11] Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial & Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71 [12] Martino Bardi. Explicit solutions of some linear-quadratic mean field games. Networks & Heterogeneous Media, 2012, 7 (2) : 243-261. doi: 10.3934/nhm.2012.7.243 [13] Kai Du, Jianhui Huang, Zhen Wu. Linear quadratic mean-field-game of backward stochastic differential systems. Mathematical Control & Related Fields, 2018, 8 (3&4) : 653-678. doi: 10.3934/mcrf.2018028 [14] Chjan C. Lim. Extremal free energy in a simple mean field theory for a coupled Barotropic fluid - rotating sphere system. Discrete & Continuous Dynamical Systems - A, 2007, 19 (2) : 361-386. doi: 10.3934/dcds.2007.19.361 [15] Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial & Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251 [16] Fang Han, Bin Zhen, Ying Du, Yanhong Zheng, Marian Wiercigroch. Global Hopf bifurcation analysis of a six-dimensional FitzHugh-Nagumo neural network with delay by a synchronized scheme. Discrete & Continuous Dynamical Systems - B, 2011, 16 (2) : 457-474. doi: 10.3934/dcdsb.2011.16.457 [17] Hong Il Cho, Gang Uk Hwang. Optimal design and analysis of a two-hop relay network under Rayleigh fading for packet delay minimization. Journal of Industrial & Management Optimization, 2011, 7 (3) : 607-622. doi: 10.3934/jimo.2011.7.607 [18] Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics & Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016 [19] Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149 [20] T. S. Evans, A. D. K. Plato. Network rewiring models. Networks & Heterogeneous Media, 2008, 3 (2) : 221-238. doi: 10.3934/nhm.2008.3.221

2017 Impact Factor: 0.564