Optimal data placements for triple replication in distributed storage systems
Ruijing Liu, Junling Zhou · Advances in Mathematics of Communications · 2022
In distributed storage systems it is essential to store files (data) in replication to ensure reliability and fault-tolerance. Given a set \begin{document}$ V $\end{document} of \begin{document}$ v $\end{document} servers along with \begin{document}$ b $\end{document} files, each file is replicated (placed) on exactly \begin{document}$ k $\end{document} servers and thus a file can be represented by a set of \begin{document}$ k $\end{document} servers. Then we produce a data placement consisting of \begin{document}$ b $\end{document} subsets of \begin{document}$ V $\end{document} called blocks, each of size \begin{document}$ k $\end{document} . 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 \begin{document}$ b $\end{document} blocks of size three on a \begin{document}$ v $\end{document} -set was proved to exist by Wei et al. [J. Combin. Des. 24 (2016) 77-100] if \begin{document}$ v $\end{document} and \begin{document}$ b $\end{document} 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 \begin{document}$ b $\end{document} blocks on a \begin{document}$ v $\end{document} -set for all positive integers \begin{document}$ v, b $\end{document} with \begin{document}$ v \equiv 0, 1, 3, 5 $\end{document} (mod 6).