doi: 10.3934/amc.2022037
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Optimal data placements for triple replication in distributed storage systems

School of Mathematics and Statistics, Beijing Jiaotong University, Beijing 100044, China

*Corresponding author: Junling Zhou

Received  February 2022 Early access May 2022

Fund Project: This work was supported by Beijing Natural Science Foundation (Grant No. 1222013) and National Natural Science Foundation of China (Grant No. 12171028, 11971053)

In distributed storage systems it is essential to store files (data) in replication to ensure reliability and fault-tolerance. Given a set $ V $ of $ v $ servers along with $ b $ files, each file is replicated (placed) on exactly $ k $ servers and thus a file can be represented by a set of $ k $ servers. Then we produce a data placement consisting of $ b $ subsets of $ V $ called blocks, each of size $ k $. Each server has some probability to fail and we want to find an optimal data placement that minimizes the variance of the number of available files for any value of the probability of failure. An optimal data placement with $ b $ blocks of size three on a $ v $-set was proved to exist by Wei et al. [J. Combin. Des. 24 (2016) 77-100] if $ v $ and $ b $ meet some conditions. We observe that there is as yet no complete solution to the existence problem of optimal data placements for triple replication. Hence this article concentrates on those missing parameters by former research and we characterize the combinatorial properties of the corresponding optimal data placements. Nearly well-balanced triple systems (NWBTSs) are defined to produce optimal data placements. Many constructions for NWBTSs are developed, mainly by constructing candelabra systems with various desirable partitions. The main result of this article is that there always exist optimal data placements for triple replication with $ b $ blocks on a $ v $-set for all positive integers $ v, b $ with $ v \equiv 0, 1, 3, 5 $ (mod 6).

Citation: Ruijing Liu, Junling Zhou. Optimal data placements for triple replication in distributed storage systems. Advances in Mathematics of Communications, doi: 10.3934/amc.2022037
References:
[1]

R. J. R. Abel, C. J. Colbourn and J. H. Dinitz, Mutually orthogonal Latin squares (MOLS), The CRC Handbook of Combinatorial Designs, (eds. C. J. Colbourn, J. H. Dinitz, 2nd edn.), CRC Press, Boca Raton, FL, (2007), 160–193.

[2]

A.-E. Baert, V. Boudet and A. Jean-Marie, Performance analysis of data replication in grid delivery networks, International Conference on Complex Intelligent and Software Intensive Systems, Barcelona, (2008), 369–374.

[3]

A.-E. Baert, V. Boudet, A. Jean-Marie and X. Roche, Minimization of download times in a distributed VOD system, The International Conference on Parallel Processing, IEEE, Los Alamitos, CA, (2008), 173–180.

[4]

A.-E. BaertV. BoudetA. Jean-Marie and X. Roche, Minimization of download time variance in a distributed VOD system, Scalable Comput. Pract. Exp., West University of Timisoara, 10 (2009), 75-86. 

[5]

J.-C. BermondA. Jean-MarieD. Mazauric and J. Yu, Well-balanced designs for data placement, J. Combin. Des., 24 (2016), 55-76.  doi: 10.1002/jcd.21506.

[6]

H. CaoL. Ji and L. Zhu, Large sets of disjoint packings on $6k + 5$ points, J. Combin. Theory Ser. A, 108 (2004), 169-183.  doi: 10.1016/j.jcta.2004.06.007.

[7]

D. ChenC. C. Lindner and D. R. Stinson, Further results on large sets of disjoint group-divisible designs, Discrete Math., 110 (1992), 35-42.  doi: 10.1016/0012-365X(92)90698-F.

[8]

C.-M. K. Fu, The Intersection Problem for Pentagon Systems, Ph.D thesis, Auburn University, 1987.

[9]

A. Jean-Marie, X. Roche, V. Boudet and A.-E. Baert, Combinatorial Designs and Availability, Research Report RR-7119 INRIA, 2009.

[10]

L. Ji, A new existence proof for large sets of disjoint Steiner triple systems, J. Combin. Theory Ser. A, 112 (2005), 308-327.  doi: 10.1016/j.jcta.2005.06.005.

[11]

L. Ji, Partition of triples of order $6k + 5$ into $6k + 3$ optimal packings and one packing of size $8k + 4$, Graph Combin., 22 (2006), 251-260.  doi: 10.1007/s00373-005-0632-1.

[12]

H. Moh$\acute{a}$csy and D. K. Ray-Chaudhuri, Candelabra systems and designs, J. Statist. Plann. Inference, 106 (2002), 419-448.  doi: 10.1016/S0378-3758(02)00226-4.

[13]

H. WeiG. Ge and C. J. Colbourn, The existence of well-balanced triple systems, J. Combin. Des., 24 (2016), 77-100.  doi: 10.1002/jcd.21508.

show all references

References:
[1]

R. J. R. Abel, C. J. Colbourn and J. H. Dinitz, Mutually orthogonal Latin squares (MOLS), The CRC Handbook of Combinatorial Designs, (eds. C. J. Colbourn, J. H. Dinitz, 2nd edn.), CRC Press, Boca Raton, FL, (2007), 160–193.

[2]

A.-E. Baert, V. Boudet and A. Jean-Marie, Performance analysis of data replication in grid delivery networks, International Conference on Complex Intelligent and Software Intensive Systems, Barcelona, (2008), 369–374.

[3]

A.-E. Baert, V. Boudet, A. Jean-Marie and X. Roche, Minimization of download times in a distributed VOD system, The International Conference on Parallel Processing, IEEE, Los Alamitos, CA, (2008), 173–180.

[4]

A.-E. BaertV. BoudetA. Jean-Marie and X. Roche, Minimization of download time variance in a distributed VOD system, Scalable Comput. Pract. Exp., West University of Timisoara, 10 (2009), 75-86. 

[5]

J.-C. BermondA. Jean-MarieD. Mazauric and J. Yu, Well-balanced designs for data placement, J. Combin. Des., 24 (2016), 55-76.  doi: 10.1002/jcd.21506.

[6]

H. CaoL. Ji and L. Zhu, Large sets of disjoint packings on $6k + 5$ points, J. Combin. Theory Ser. A, 108 (2004), 169-183.  doi: 10.1016/j.jcta.2004.06.007.

[7]

D. ChenC. C. Lindner and D. R. Stinson, Further results on large sets of disjoint group-divisible designs, Discrete Math., 110 (1992), 35-42.  doi: 10.1016/0012-365X(92)90698-F.

[8]

C.-M. K. Fu, The Intersection Problem for Pentagon Systems, Ph.D thesis, Auburn University, 1987.

[9]

A. Jean-Marie, X. Roche, V. Boudet and A.-E. Baert, Combinatorial Designs and Availability, Research Report RR-7119 INRIA, 2009.

[10]

L. Ji, A new existence proof for large sets of disjoint Steiner triple systems, J. Combin. Theory Ser. A, 112 (2005), 308-327.  doi: 10.1016/j.jcta.2005.06.005.

[11]

L. Ji, Partition of triples of order $6k + 5$ into $6k + 3$ optimal packings and one packing of size $8k + 4$, Graph Combin., 22 (2006), 251-260.  doi: 10.1007/s00373-005-0632-1.

[12]

H. Moh$\acute{a}$csy and D. K. Ray-Chaudhuri, Candelabra systems and designs, J. Statist. Plann. Inference, 106 (2002), 419-448.  doi: 10.1016/S0378-3758(02)00226-4.

[13]

H. WeiG. Ge and C. J. Colbourn, The existence of well-balanced triple systems, J. Combin. Des., 24 (2016), 77-100.  doi: 10.1002/jcd.21508.

Figure 1.  Defect graphs with defect 1 for (C1)
Figure 2.  Defect graphs for (C2)
[1]

Yogiraj Mantri, Michael Herty, Sebastian Noelle. Well-balanced scheme for gas-flow in pipeline networks. Networks and Heterogeneous Media, 2019, 14 (4) : 659-676. doi: 10.3934/nhm.2019026

[2]

Boris Andreianov, Nicolas Seguin. Analysis of a Burgers equation with singular resonant source term and convergence of well-balanced schemes. Discrete and Continuous Dynamical Systems, 2012, 32 (6) : 1939-1964. doi: 10.3934/dcds.2012.32.1939

[3]

Laurent Gosse. Well-balanced schemes using elementary solutions for linear models of the Boltzmann equation in one space dimension. Kinetic and Related Models, 2012, 5 (2) : 283-323. doi: 10.3934/krm.2012.5.283

[4]

François Bouchut, Vladimir Zeitlin. A robust well-balanced scheme for multi-layer shallow water equations. Discrete and Continuous Dynamical Systems - B, 2010, 13 (4) : 739-758. doi: 10.3934/dcdsb.2010.13.739

[5]

Hartmut Pecher. Almost optimal local well-posedness for the Maxwell-Klein-Gordon system with data in Fourier-Lebesgue spaces. Communications on Pure and Applied Analysis, 2020, 19 (6) : 3303-3321. doi: 10.3934/cpaa.2020146

[6]

Hayato Ushijima-Mwesigwa, MD Zadid Khan, Mashrur A. Chowdhury, Ilya Safro. Optimal Placement of wireless charging lanes in road networks. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1315-1341. doi: 10.3934/jimo.2020023

[7]

Alberto Bressan, Fabio S. Priuli. Nearly optimal patchy feedbacks. Discrete and Continuous Dynamical Systems, 2008, 21 (3) : 687-701. doi: 10.3934/dcds.2008.21.687

[8]

Hiroyuki Hirayama. Well-posedness and scattering for a system of quadratic derivative nonlinear Schrödinger equations with low regularity initial data. Communications on Pure and Applied Analysis, 2014, 13 (4) : 1563-1591. doi: 10.3934/cpaa.2014.13.1563

[9]

Saoussen Sokrani. On the global well-posedness of 3-D Boussinesq system with partial viscosity and axisymmetric data. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 1613-1650. doi: 10.3934/dcds.2019072

[10]

Nasim Ullah, Ahmad Aziz Al-Ahmadi. A triple mode robust sliding mode controller for a nonlinear system with measurement noise and uncertainty. Mathematical Foundations of Computing, 2020, 3 (2) : 81-99. doi: 10.3934/mfc.2020007

[11]

Pierluigi Colli, Gianni Gilardi, Elisabetta Rocca, Jürgen Sprekels. Well-posedness and optimal control for a Cahn–Hilliard–Oono system with control in the mass term. Discrete and Continuous Dynamical Systems - S, 2022, 15 (8) : 2135-2172. doi: 10.3934/dcdss.2022001

[12]

Belinda A. Batten, Hesam Shoori, John R. Singler, Madhuka H. Weerasinghe. Balanced truncation model reduction of a nonlinear cable-mass PDE system with interior damping. Discrete and Continuous Dynamical Systems - B, 2019, 24 (1) : 83-107. doi: 10.3934/dcdsb.2018162

[13]

Yuan Xu, Fujun Zhou, Weihua Gong. Global Well-posedness and Optimal Decay Rate of the Quasi-static Incompressible Navier–Stokes–Fourier–Maxwell–Poisson System. Communications on Pure and Applied Analysis, 2022, 21 (5) : 1537-1565. doi: 10.3934/cpaa.2022028

[14]

Toufik Bakir, Bernard Bonnard, Jérémy Rouot. A case study of optimal input-output system with sampled-data control: Ding et al. force and fatigue muscular control model. Networks and Heterogeneous Media, 2019, 14 (1) : 79-100. doi: 10.3934/nhm.2019005

[15]

Vanessa Barros, Felipe Linares. A remark on the well-posedness of a degenerated Zakharov system. Communications on Pure and Applied Analysis, 2015, 14 (4) : 1259-1274. doi: 10.3934/cpaa.2015.14.1259

[16]

Rinaldo M. Colombo, Mauro Garavello. A Well Posed Riemann Problem for the $p$--System at a Junction. Networks and Heterogeneous Media, 2006, 1 (3) : 495-511. doi: 10.3934/nhm.2006.1.495

[17]

Bilal Al Taki. Global well posedness for the ghost effect system. Communications on Pure and Applied Analysis, 2017, 16 (1) : 345-368. doi: 10.3934/cpaa.2017017

[18]

Liu Hui, Lin Zhi, Waqas Ahmad. Network(graph) data research in the coordinate system. Mathematical Foundations of Computing, 2018, 1 (1) : 1-10. doi: 10.3934/mfc.2018001

[19]

Cheng-Feng Hu, Hsiao-Fan Wang, Tingyang Liu. Measuring efficiency of a recycling production system with imprecise data. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 79-91. doi: 10.3934/naco.2021052

[20]

Chongyang Liu, Wenjuan Sun, Xiaopeng Yi. Optimal control of a fractional smoking system. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022071

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (105)
  • HTML views (44)
  • Cited by (0)

Other articles
by authors

[Back to Top]