Discrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational Science2658-46702658-7149Peoples' Friendship University of Russia named after Patrice Lumumba (RUDN University)8272ArticlesСтатьиResearch ArticleThe Problem of Data Placement in Distributed SystemsЗадача оптимизации размещения данных в распределённых системахZhipaA VЖипаА ВDepartment of Information TechnologyКафедра информационных технологий-Peoples’ Friendship University of RussiaРоссийский университет дружбы народов150220152NO2 (2015)№2 (2015)465408092016Copyright ©; 2015, Жипа А.В.2015Жипа А.В.http://creativecommons.org/licenses/by/4.0https://journals.rudn.ru/miph/article/view/8272Distributed system effectiveness depends dramatically on the way it manages incoming tasks and data against limited computational resources that are at its disposal. Due to ever-inreasing amount of incoming data distributed systems are required to efficiently manage the way its storage and processing are being made. Nowadays the distributed system design is significantly flounced by the manner it leverages high load scenarios, provides data storage functionality and uses the underlying resources. An effective distributed system’s resource management has to balance trade-offs between single node resource consumption and the overall loss of data locality, that is inevitable due to data fragmentation. In this article we will formalize the problem of data placement by maximizing data storage locality in distributed data systems, which as it turns out is a NP-complete task. We will later describe a polynomial-time algorithm that is capable of providing us a solution that is within an additive constant from the optimal one.Эффективность работы распределённых вычислительных систем основывается на способе распределения потоков вычислительных задач и данных относительно ограниченного количества вычислительных ресурсов. Из-за постоянного увеличения объёма данных таким системам необходимо решать вопрос их хранения и обработки наиболее эффективным образом. Между тем современные распределённые вычислительные системы уделяют все больше внимания таким своим характеристикам, как распределение вычислительной нагрузки, построение эффективной структуры хранилища данных, а также оптимальное использование вычислительных мощностей. Оптимальное управление имеющимися у вычислительной системы ресурсами вынуждено балансировать между использованием ресурсов каждого отдельно взятого узла и потерей локальности хранения данных, связанной с их неизбежной фрагментацией. В данной статье мы сформируем задачу оптимизации размещения данных путём максимизации локальности их хранения, а также покажем, что данная задача является NP-полной. Далее мы рассмотрим полиномиальный по времени алгоритм, дающий результат, отличающийся от оптимального на фиксированную константу. Для доказательства эффективности предложенного алгоритма нами будет доказан ряд вспомогательных утверждений, а также подробно описана основная операция в работе алгоритма, за свою схожесть с процессом обмена участками хромосом в клетках названная кроссинговером.fragmentationdistributed systemsNP-complete problemsbin-packing problemsdata storage localityфрагментацияраспределённые вычислительные системыNP-полные задачизадача об упаковке в контейнерылокальность хранения данных1.Oceanstore: An Architecture for Global-Scale Persistent Storage / J. Kubiatowicz, D. Bindel, Y. Chen et al. // ASPLOS-IX / ASPLOS. - New York, USA: ACM, 2000. - Pp. 190-201.2.Wide-Area Cooperative Storage with CFS / F. Dabek, M. Kaashoek, D. Karger et al. // SOSP. - 2001. - Pp. 202-215.3.Rowstron A., Druschel P. Storage Management and Caching in PAST, A Largescale, Persistent Peer-to-peer Storage Utility // SOSP. - 2001. - Pp. 188-201.4.Ivy: A Read/Write Peer-to-Peer File System / A. Muthitacharoen, R. Morris, T. M. Gil, B. Chen // SOSDI / Ed. by D. E. Culler, P. Druschel. - USENIX Association, 2002.5.Coffman E.G.J., Garey M.R., Johnson D.S. Approximation Algorithms for NP-hard Problems. - Boston, USA: PWS Publications, 1996. - Pp. 46-96.6.Coffman E.G.J., Lueker G. Approximation Algorithms for Extensible Bin-Packing // Journal of Scheduling. - Vol. 9. - Hingham, MA, USA: Kluwer Academic Publishers, 2006. - Pp. 63-69.7.Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing / E. G. J. Coffman, C. Courcoubetis, M. R. Garey et al. // J. Discrete Math. - 2000. - Vol. 13, No 3. - Pp. 384-402.8.Seiden S.S. On the Online Bin Packing Problem // Journal of the ACM. - 2002. - Vol. 49, No 5. - Pp. 640-671.9.Karp R.M. Reducibility Among Combinatorial Problems // SOSP. - The IBM Research Symposia Series. - Plenum Press, New York, 1972. - Pp. 85-103.10.Garey M.R., Johnson D.S. Complexity Results for Multiprocessor Scheduling under Resource Constraints // SIAM Journal on Computing. - 1975. - Vol. 4, No 4. - Pp. 397-411.