Рандомизация в распределенных вычислениях: различия между версиями

Бинарный консенсус является одной из наиболее фундаментальных проблем в распределенных вычислениях. Примером ее важности может служить следующий результат, полученный Херлихи [8]. Если абстрактный тип данных X вместе с общей памятью являются достаточно мощными для реализации консенсуса без ожидания, то X вместе с общей памятью является достаточно мощным для реализации без ожидания любой другой структуры данных Y. Таким образом, используя этот результат, можно создать версию любой структуры данных без ожидания, используя в качестве строительного блока только мультирайтерные мультиридерные регистры без ожидания.