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

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

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

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

Giuseppe Bianchi ^1, , Lorenzo Bracciale ^1, , Keren Censor-Hillel ^2, , Andrea Lincoln ^3, and Muriel Médard ^4,

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

Abstract
Related Papers

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: linear network coding, lower bounds, Delay tolerant network, mean field arguments., fluid approximations.

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

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

show all references

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.

[1]	Ghislain Fourier, Gabriele Nebe. Degenerate flag varieties in network coding. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021027
[2]	Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577
[3]	Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete and Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145
[4]	Joachim Crevat. Mean-field limit of a spatially-extended FitzHugh-Nagumo neural network. Kinetic and Related Models, 2019, 12 (6) : 1329-1358. doi: 10.3934/krm.2019052
[5]	Fabio Bagagiolo, Rosario Maggistro, Raffaele Pesenti. Origin-to-destination network flow with path preferences and velocity controls: A mean field game-like approach. Journal of Dynamics and Games, 2021, 8 (4) : 359-380. doi: 10.3934/jdg.2021007
[6]	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
[7]	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 and Heterogeneous Media, 2012, 7 (1) : 43-58. doi: 10.3934/nhm.2012.7.43
[8]	Á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
[9]	Michael Herty, Mattia Zanella. Performance bounds for the mean-field limit of constrained dynamics. Discrete and Continuous Dynamical Systems, 2017, 37 (4) : 2023-2043. doi: 10.3934/dcds.2017086
[10]	Reimund Rautmann. Lower and upper bounds to the change of vorticity by transition from slip- to no-slip fluid flow. Discrete and Continuous Dynamical Systems - S, 2014, 7 (5) : 1101-1109. doi: 10.3934/dcdss.2014.7.1101
[11]	Maria Schonbek, Tomas Schonbek. Moments and lower bounds in the far-field of solutions to quasi-geostrophic flows. Discrete and Continuous Dynamical Systems, 2005, 13 (5) : 1277-1304. doi: 10.3934/dcds.2005.13.1277
[12]	Katrin Gelfert. Lower bounds for the topological entropy. Discrete and Continuous Dynamical Systems, 2005, 12 (3) : 555-565. doi: 10.3934/dcds.2005.12.555
[13]	Ariel Salort. Lower bounds for Orlicz eigenvalues. Discrete and Continuous Dynamical Systems, 2022, 42 (3) : 1415-1434. doi: 10.3934/dcds.2021158
[14]	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
[15]	Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial and Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71
[16]	Zheng Chen, Liu Liu, Lin Mu. Solving the linear transport equation by a deep neural network approach. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 669-686. doi: 10.3934/dcdss.2021070
[17]	Martino Bardi. Explicit solutions of some linear-quadratic mean field games. Networks and Heterogeneous Media, 2012, 7 (2) : 243-261. doi: 10.3934/nhm.2012.7.243
[18]	Kai Du, Jianhui Huang, Zhen Wu. Linear quadratic mean-field-game of backward stochastic differential systems. Mathematical Control and Related Fields, 2018, 8 (3&4) : 653-678. doi: 10.3934/mcrf.2018028
[19]	Zhenghong Qiu, Jianhui Huang, Tinghan Xie. Linear-Quadratic-Gaussian mean-field controls of social optima. Mathematical Control and Related Fields, 2021 doi: 10.3934/mcrf.2021047
[20]	Chjan C. Lim. Extremal free energy in a simple mean field theory for a coupled Barotropic fluid - rotating sphere system. Discrete and Continuous Dynamical Systems, 2007, 19 (2) : 361-386. doi: 10.3934/dcds.2007.19.361

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Giuseppe Bianchi Lorenzo Bracciale Keren Censor-Hillel Andrea Lincoln Muriel Médard
on Google Scholar
Giuseppe Bianchi Lorenzo Bracciale Keren Censor-Hillel Andrea Lincoln Muriel Médard

[Back to Top]