АНАЛИЗ РЕАЛИЗАЦИИ МИНИМАЛЬНОГО АЛГОРИТМА В КЛАСТЕРНОЙ АРХИТЕКТУРЕ
Рассмотрена теорема о минимальном алгоритме применительно к задаче сортировки кортежей в компьютерном кластере. Приведено более подробное ее доказательство, в котором устранены выявленные неточности. Рассмотрен распространенный алгоритм сортировки TeraSort в системе MapReduce, состоящий из двух заданий. Получены верхние оценки времени реализации первого задания в системе Hadoopна каждой фазы: Map, Shuffle, Reduce. Показано, что при фиксированной вероятности фильтрации кортежей нарушаются свойства минимального алгоритма.
Ключевые слова: минимальный алгоритм, сортировка, MapReduce, Hadoop
