Задача оптимизации размещения данных в распределённых системах

Эффективность работы распределённых вычислительных систем основывается на способе распределения потоков вычислительных задач и данных относительно ограниченного количества вычислительных ресурсов. Из-за постоянного увеличения объёма данных таким системам необходимо решать вопрос их хранения и обработки наиболее эффективным образом. Между тем современные распределённые вычислительные системы уделяют все больше внимания таким своим характеристикам, как распределение вычислительной нагрузки, построение эффективной структуры хранилища данных, а также оптимальное использование вычислительных мощностей. Оптимальное управление имеющимися у вычислительной системы ресурсами вынуждено балансировать между использованием ресурсов каждого отдельно взятого узла и потерей локальности хранения данных, связанной с их неизбежной фрагментацией. В данной статье мы сформируем задачу оптимизации размещения данных путём максимизации локальности их хранения, а также покажем, что данная задача является NP-полной. Далее мы рассмотрим полиномиальный по времени алгоритм, дающий результат, отличающийся от оптимального на фиксированную константу. Для доказательства эффективности предложенного алгоритма нами будет доказан ряд вспомогательных утверждений, а также подробно описана основная операция в работе алгоритма, за свою схожесть с процессом обмена участками хромосом в клетках названная кроссинговером.

фрагментация, распределённые вычислительные системы, NP-полные задачи, задача об упаковке в контейнеры, локальность хранения данных