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

Теорема 1. Предполагая существование мультирайтерных мультиридерных регистров, существует рандомизированный алгоритм решения задачи двоичного консенсуса против промежуточного соперника с O(1) ожидаемых шагов на процессор.

Теорема 2. Предполагая существование мультирайтерных мультиридерных регистров, существует рандомизированный алгоритм решения задачи ID-консенсуса против промежуточного соперника с O(log2 n) ожидаемых шагов на процессор.

Оба этих результата предполагают, что каждый процессор имеет уникальный идентификатор. До получения этого результата самый быстрый из известных рандомизированных алгоритмов для двоичного консенсуса использовал однорайтерные мультиридерные регистры, был устойчив относительно сильного соперника и требовал O(n log2 n) шагов на процессор [2]. Таким образом, вышеуказанные улучшения получены за счет ослабления соперника и усиления модели системы по сравнению с [2].