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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[7]

P. Erdős and A. Rényi, On the evolution of random graphs,, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960), 17. Google Scholar

[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. Google Scholar

[9]

T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes,, J. Appl. Probab., 7 (1970), 49. Google Scholar

[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. Google Scholar

[11]

M. Luby, LT codes,, in The 43rd Ann. IEEE Symp. Found. Comp. Sci., (2002), 271. doi: 10.1109/SFCS.2002.1181950. Google Scholar

[12]

A. Oppenheim, R. Schafer and J. Buck, Discrete-Time Signal Processing,, Printice Hall Inc., (1989). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[7]

P. Erdős and A. Rényi, On the evolution of random graphs,, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960), 17. Google Scholar

[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. Google Scholar

[9]

T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes,, J. Appl. Probab., 7 (1970), 49. Google Scholar

[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. Google Scholar

[11]

M. Luby, LT codes,, in The 43rd Ann. IEEE Symp. Found. Comp. Sci., (2002), 271. doi: 10.1109/SFCS.2002.1181950. Google Scholar

[12]

A. Oppenheim, R. Schafer and J. Buck, Discrete-Time Signal Processing,, Printice Hall Inc., (1989). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (0)

[Back to Top]