Топологический подход в распределенных вычислениях: различия между версиями

Применение методов комбинаторной и алгебраической топологии позволило успешно решить ряд проблем в области распределенных вычислений. В 1993 году три независимые команды [3, 15, 17], используя различные способы обобщения классической теоретико-графовой модели распределенных вычислений, смогли решить задачу согласования множеств, которая долгое время не поддавалась стандартным подходам. Позднее, в 2004 году, журнальные статьи Херлихи и Шавита [15] и Сакса и Захароглу [ ] были удостоены престижной премии Гёделя. Ниже описывается подход, примененный в статье Херлихи и Шавита, в которой впервые была установлена связь между алгебраической и комбинаторной топологией и распределенными вычислениями.

Комбинаторная топология обобщает понятие графа до понятия симплициального комплекса – структуры, которая уже более века активно изучается в «большой» математике. Одним из наиболее интересующих топологов свойств было отсутствие в симплициальном комплексе «дыр» ниже определенной размерности k – свойство, известное как k-связность. Нижние границы, которые ранее выражались в терминах связности графов, можно обобщить, переформулировав их в терминах k-связности симплициальных комплексов. Используя это представление, удалось разрешить некоторые открытые вопросы (такие как [[Согласование множеств|согласование k множеств]] или [[переименование]]), поставить и решить несколько новых задач ([ ]), а также унифицировать ряд разрозненных результатов и моделей [14].