УДК 004.75 Задача оптимизации размещения данных в распределённых системах А. В. Жипа Кафедра информационных технологий Российский университет дружбы народов ул. <...> 6, Москва, Россия, 117198 Эффективность работы распределённых вычислительных систем основывается на способе распределения потоков вычислительных задач и данных относительно ограниченного количества вычислительных ресурсов. <...> Из-за постоянного увеличения объёма данных таким системам необходимо решать вопрос их хранения и обработки наиболее эффективным образом. <...> Между тем современные распределённые вычислительные системы уделяют все больше внимания таким своим характеристикам, как распределение вычислительной нагрузки, построение эффективной структуры хранилища данных, а также оптимальное использование вычислительных мощностей. <...> Оптимальное управление имеющимися у вычислительной системы ресурсами вынуждено балансировать между использованием ресурсов каждого отдельно взятого узла и потерей локальности хранения данных, связанной с их неизбежной фрагментацией. <...> В данной статье мы сформируем задачу оптимизации размещения данных путём максимизации локальности их хранения, а также покажем, что данная задача является NP-полной. <...> Далее мы рассмотрим полиномиальный по времени алгоритм, дающий результат, отличающийся от оптимального на фиксированную константу. <...> Для доказательства эффективности предложенного алгоритма нами будет доказан ряд вспомогательных утверждений, а также подробно описана основная операция в работе алгоритма, за свою схожесть с процессом обмена участками хромосом в клетках названная кроссинговером. <...> Ключевые слова: фрагментация, распределённые вычислительные системы, NPполные задачи, задача об упаковке в контейнеры, локальность хранения данных. <...> Например, такие децентрализованные системы хранения данных, как OceanStore [1], CFS [2], PAST [3] и IVY [4], предоставляют возможность постоянного хранения данных, используя распределённые <...>