Оптимальность одновременного консенсуса с ограниченным обменом информацией (расширенная аннотация)

Основная информация

• ID статьи: 2511.22380
• Название: Optimality of Simultaneous Consensus with Limited Information Exchange (Extended Abstract)
• Авторы: Kaya Alpturer (Принстонский университет), Ron van der Meyden (UNSW Sydney), Sushmita Ruj (UNSW Sydney), Godfrey Wong (UNSW Sydney)
• Классификация: cs.DC (распределённые вычисления)
• Время публикации/конференция: TARK 2025 (Theoretical Aspects of Rationality and Knowledge 2025)
• Ссылка на статью: https://arxiv.org/abs/2511.22380
• Издание конференции: EPTCS 437, 2025, стр. 175–189

Аннотация

В данной работе исследуется проблема одновременного византийского соглашения (Simultaneous Byzantine Agreement, SBA) в модели отказов при сбое, с акцентом на оптимальность протоколов с ограниченным обменом информацией. Традиционные исследования отказоустойчивых протоколов консенсуса, основанные на логике знаний, сосредоточены на подходах с «полным обменом информацией», однако этот подход имеет высокую стоимость с точки зрения размера сообщений. В статье анализируются различные протоколы с ограниченным обменом информации из литературы (FloodSet и его варианты, Vectorized FloodSet) и предлагается новый протокол обмена информацией SendWaste, который позволяет принимать решения максимум на один раунд позже, чем оптимальный протокол полного обмена информации Dwork и Moses, но с меньшей вычислительной стоимостью и требованиями к памяти. Путём реализации программ на основе знаний (knowledge-based program) авторы выводят оптимальные протоколы для каждого способа обмена информацией.

Исследовательский контекст и мотивация

1. Основная проблема

Основная проблема, которую решает данная работа: как разработать оптимальные протоколы одновременного византийского соглашения в распределённых системах, когда обмен информацией между агентами ограничен?

2. Значимость проблемы

• Теоретическое значение: Проблема византийского соглашения является фундаментальной в распределённых вычислениях и тесно связана с механизмами консенсуса и проектированием отказоустойчивых систем
• Практическая ценность: Хотя протоколы полного обмена информацией теоретически оптимальны, в практических приложениях размер сообщений растёт экспоненциально, а вычислительная сложность может достичь NP-hard (например, в общей модели пропусков)
• Реальные требования: Практические протоколы обычно обмениваются меньшим объёмом информации и нуждаются в теоретическом руководстве для обеспечения полного использования обмениваемой информации

3. Ограничения существующих подходов

• Протоколы полного обмена: Каждый агент в каждом раунде транслирует полное локальное состояние, что приводит к экспоненциальному росту пространства состояний со временем
• Протокол Dwork-Moses: Хотя он относительно оптимален для полного обмена, размер сообщения составляет O(t), пространственная сложность O(n), вычислительная сложность O(nt)
• Протоколы с ограниченным обменом в литературе: Отсутствует теоретический анализ их оптимальности, они могут не полностью использовать обмениваемую информацию

4. Исследовательская мотивация

• Заполнение теоретического пробела: Только одна работа 1 исследовала оптимальность при ограниченном обмене информацией для проблемы консенсуса (для проблемы итогового соглашения)
• Практическая направленность: Предоставление теоретических гарантий для практических протоколов, определение наиболее раннего времени завершения при заданном обмене информацией
• Оптимизация существующих протоколов: Раскрытие потенциала улучшения протоколов из литературы через анализ на основе теории знаний

Основные вклады

Основные вклады статьи включают:

1. Установление теоретической базы: Расширение концепции оптимальности при ограниченном обмене информацией с проблемы итогового соглашения (EBA) на проблему одновременного соглашения (SBA)
2. Оптимизация протокола FloodSet:
   • Установление оптимального условия остановки: m ≥ min{t+1, n-1}
   • Улучшение результатов из литературы: при t=n-1 остановка раньше, чем обычно указываемый t+1
3. Анализ Counting FloodSet:
   • Доказательство того, что оптимальное условие остановки для варианта с подсчётом совпадает с FloodSet (кроме особых случаев)
   • Доказательство того, что сохранение истории подсчётов (perfect recall) не обеспечивает дополнительных преимуществ
4. Улучшение Vectorized FloodSet:
   • Обнаружение нетривиального условия ранней остановки: m > min{t+1, n-1} - max{1, βi(r,m)}
   • Улучшение времени остановки t+1 из работы Raynal11
5. Новый протокол SendWaste:
   • Предложение нового механизма обмена информацией: передача оценок потерь вместо наборов агентов
   • Гарантия производительности: принятие решения максимум на один раунд позже, чем протокол Dwork-Moses
   • Повышение эффективности: вычислительная сложность O(n), размер сообщения O(1), пространственная сложность O(1)
6. Систематическое сравнение сложности: Предоставление полного сравнения всех протоколов по трём измерениям: вычисления, размер сообщения, пространство (см. таблицу 1)

Подробное описание методов

Определение задачи

Проблема одновременного византийского соглашения (SBA) включает следующие спецификации:

• Вход: n агентов, каждый с начальным значением vi ∈ {0,1}, система имеет максимум t < n отказов при сбое
• Выход: Неотказавшие агенты принимают решение о значении v ∈ {0,1}

Ограничения:

1. Согласованность (Agreement): Все неотказавшие агенты принимают одно и то же значение
2. Корректность (Validity): Принятое значение должно быть начальным значением некоторого агента
3. Одновременность (Simultaneity): Все неотказавшие агенты принимают решение в одном и том же раунде
4. Завершение (Termination): Каждый агент в конечном итоге принимает решение или отказывает

Модель отказов при сбое (Crasht):

• Отказавший агент может отправить любое подмножество сообщений в раунде сбоя
• После сбоя агент больше не отправляет сообщения
• Максимум t агентов отказывают

Архитектура модели

1. Структура разложения протокола

Статья разлагает протокол SBA на два компонента: (P, E)

• Протокол обмена информацией E: Определяет, какую информацию записывают агенты и какие сообщения отправляют
• Протокол принятия решения P: Определяет, когда и какое решение принимает агент

Формальное определение протокола обмена информацией Ei как шеститерминального кортежа:

• Li: множество локальных состояний
• Ii ⊆ Li: множество начальных состояний
• Ai: множество допустимых действий
• Mi: множество отправляемых сообщений
• μi: Li × Ai → ∏j∈Agt(Mi ∪ {⊥}): функция выбора сообщений
• δi: Li × Le × Ai × ∏j∈Agt(Mj ∪ {⊥}) → Li: функция переходов состояния

2. Программы на основе знаний (Knowledge-Based Program)

Основная программа на основе знаний Popt_i определяется как:

if Ki(CN(∃0)) then decidei(0)
else if Ki(CN(∃1)) then decidei(1)
else noop

где:

• Ki(φ): агент i знает φ
• CN(φ): общее знание неотказавших агентов
• ∃v: существует агент с начальным значением v

Ключевое понимание (Лемма 1): Если агент i принимает решение v в (r,m), то (I,r,m) ⊨ CN(∃v)

3. Определение оптимальности

Отношение частичного порядка: P ≤E P' тогда и только тогда, когда во всех соответствующих выполнениях, когда P принимает решение, P' также принимает решение

Оптимальный протокол: Не существует строго лучшего протокола (то есть P ≤E P' влечёт P' ≤E P)

Теорема оптимальной реализации (Теорема 2): Реализация программы на основе знаний Popt является оптимальным протоколом SBA относительно её обмена информацией E

Технические инновации

1. Теория отношений хранения информации

Определение: E1 хранит больше информации, чем E2, если в соответствующих выполнениях: (r1,m) ~i (r3,m) ⟹ (r2,m) ~i (r4,m)

Следствие (Предложение 1): Если E1 хранит информацию ≥ E2, то: (IE1,r1,m) ⊨ ¬CN φ ⟹ (IE2,r2,m) ⊨ ¬CN φ

Этот теоретический инструмент позволяет передавать выводы о получении знаний путём сравнения объёма информации.

2. Концепция чистого раунда (Clean Round)

Определение: Раунд является чистым, если все неотказавшие агенты получают одинаковый набор сообщений

Ключевые свойства:

• После чистого раунда все агенты имеют одинаковое состояние (Лемма 5)
• Максимум за t+1 раунд должен произойти чистый раунд (максимум t отказов)
• При t=n-1 решение может быть принято на раунде n-1

3. Оценка потерь (Waste)

Потери Dwork-Moses: W(r) = maxk≥0{#KF(r,k) - k}

• #KF(r,k): максимальное количество отказов в распределённом знании на раунде k

Оценка SendWaste: di = max{di-1, полученные dj, hi - m}

• hi: количество отсутствующих сообщений на раунде m
• Оценка: hi - m (наблюдаемые «потери» в текущем раунде)

Инновационный момент:

• Нет необходимости поддерживать набор отказавших агентов, только подсчёт
• Размер сообщения снижается с O(t) до O(1)
• Вычислительная сложность снижается с O(nt) до O(n)

Экспериментальная установка

Метод теоретического анализа

Данная работа является чисто теоретической и не содержит экспериментальных данных, а вместо этого устанавливает результаты через формальные доказательства. Основные методы анализа:

1. Анализ семантики теории знаний: Использование интерпретируемых систем и отношений неразличимости
2. Доказательство по индукции: Индукция по времени выполнения и состояниям
3. Конструктивное доказательство: Доказательство необходимости путём построения контрпримеров
4. Сравнение соответствующих выполнений: Сравнение поведения различных протоколов при одинаковых сбоях

Критерии оценки

Качество протокола оценивается по следующим измерениям:

1. Время принятия решения: Наиболее ранний раунд первого решения
2. Вычислительная сложность: Объём вычислений на агента за раунд
3. Размер сообщения: Количество бит в каждом сообщении
4. Пространственная сложность: Размер состояния, хранящегося на агента

Базовые протоколы для сравнения

• FloodSet Lynch 1996
• Counting FloodSet Castañeda et al. 2017
• Vectorized FloodSet Raynal 2002
• Протокол Dwork-Moses Dwork & Moses 1990 - оптимальный протокол полного обмена

Результаты экспериментов

Основные теоретические результаты

1. FloodSet и его оптимизация (Теорема 3)

Исходное условие остановки: m = t+1

Оптимизированное условие остановки: m ≥ min{t+1, n-1}

Ключевые моменты доказательства:

• Необходимость: Лемма 2 показывает, что при m < min{t+1, n-1} нет общего знания
• Достаточность: После min{t+1, n-1} раундов должен произойти чистый раунд, из Лемм 5-6 получается общее знание

Значение улучшения: При t=n-1 решение может быть принято на раунде n-1 вместо раунда n

2. Counting FloodSet (Теорема 4)

Условие остановки: m ≥ min{t+1, n-1} или hi ≥ n-1

Ключевое наблюдение:

• При hi ≥ n-1 агент i знает, что живо максимум один другой агент
• В этом случае может быть принято немедленное решение min Wi

Сравнение с FloodSet: Более ранняя остановка только при обнаружении n-1 отсутствующих сообщений

3. Counting FloodSet с полной памятью (Теорема 5)

Условие остановки: m ≥ min{t+1, n-1} или ∃k≤m(hik ≥ n-1)

Важное открытие: Сохранение истории не обеспечивает дополнительных преимуществ

• В отличие от EBA (где историческая информация полезна)
• Стоимость: увеличение памяти без улучшения производительности

Отношение хранения информации (Лемма 7): Ecount(pr) ≥ Ecount ≥ Eflood

4. Vectorized FloodSet (Теорема 6)

Условие остановки: m > min{t+1, n-1} - max{1, βi(r,m)}

где βi(r,m) — количество агентов, от которых агент i не получил сообщение на раунде 1

Анализ:

• Чем больше βi(r,m), тем раньше решение
• При βi(r,m) = n-1 решение может быть принято после раунда 1
• Улучшение исходного времени остановки t+1 из работы 11

Сравнение особых случаев:

• При hi ≥ n-1 Counting FloodSet может принять решение, но Vectorized FloodSet нет
• В других случаях Vectorized FloodSet по крайней мере так же хорош

5. Протокол SendWaste (Теоремы 7-8)

Условие остановки: m ≥ min{t+1, n-1} - dN

где dN = maxi∈N(r,m) di(r,m) — максимальная оценка потерь неотказавших агентов

Сравнение с Dwork-Moses (Теорема 8):

• Если Dwork-Moses принимает решение на раунде m', SendWaste принимает решение на раунде m
• Гарантия: m' ≤ m ≤ m'+1 (максимум на один раунд позже)

Повышение эффективности:

Сравнение комплексной производительности

Таблица 1 — Итоговое сравнение (на агента за раунд):

Упорядочение по времени принятия решения (от худшего к лучшему):

1. FloodSet: min{t+1, n-1} (худший)
2. Counting FloodSet: то же, но ранняя остановка в особых случаях
3. Vectorized FloodSet: возможно раньше (зависит от β)
4. SendWaste: близко к Dwork-Moses
5. Dwork-Moses: оптимальный (полный обмен)

Ключевые выводы

1. Мощь чистых раундов: Как только происходит чистый раунд, общее знание устанавливается немедленно
2. Ограничения подсчёта: Только подсчёт текущего раунда недостаточен для превышения FloodSet
3. Бесполезность истории: Для SBA историческое подсчитывание не обеспечивает преимущества (в отличие от EBA)
4. Преимущества векторизации: Связь агентов со значениями обеспечивает раннюю остановку
5. Эффективность оценки: Оценка потерь более эффективна, чем поддержание наборов

Связанные работы

1. Теория знаний и распределённые алгоритмы

Основополагающие работы:

• Halpern & Moses (1990) 6: Установление основ знания и общего знания в распределённой среде
• Fagin et al. (1995) 5: «Reasoning About Knowledge» — теоретическая база

Анализ византийского соглашения на основе теории знаний:

• Dwork & Moses (1990) 4: Доказательство необходимости общего знания для SBA, предложение оптимального протокола полного обмена
• Moses & Tuttle (1988) 10: Использование общего знания для программирования синхронных действий

2. Ограниченный обмен информацией

Прямой предшественник данной работы:

• Alpturer, Halpern & van der Meyden (2023) 1: Первое исследование оптимальности EBA при ограниченном обмене информацией (модель пропусков отправки)

Классические протоколы:

• Lynch (1996) 7: Исходное описание протокола FloodSet
• Castañeda et al. (2017) 3: Ранняя остановка на основе предикатов, введение механизма подсчёта
• Raynal (2002) 11: Vectorized FloodSet

3. Вычислительная сложность

Результаты NP-hard:

• Moses (2009) 9: Оптимальное синхронное соглашение при общих пропусках эквивалентно NP-оракулу
• Moses & Tuttle (1988) 10: Протокол полного обмена при общих пропусках требует NP-hard вычисления

4. Непобедимый консенсус (Unbeatable Consensus)

• Castañeda, Gonczarowski & Moses (2022) 2: Исследование протоколов консенсуса, которые не могут быть побеждены

Позиционирование данной работы

Преимущества относительно связанных работ:

1. Первое систематическое исследование: Оптимальность при ограниченном обмене для SBA (1 исследовал только EBA)
2. Анализ множественных протоколов: Сравнение в единой базе различных обменов информацией
3. Новый дизайн протокола: SendWaste заполняет пробел в компромиссе производительность-эффективность
4. Теоретические улучшения: Исправление и улучшение условий остановки из литературы

Связь с 1:

• Методологическое продолжение: Использование структуры реализации программ на основе знаний
• Различие проблем: SBA vs EBA (более строгие требования одновременности)
• Различие моделей отказов: Отказ при сбое vs пропуск отправки

Заключение и обсуждение

Основные выводы

1. Оптимальность вариантов FloodSet:
   • FloodSet и его вариант с подсчётом достигают оптимальности при своём обмене информацией
   • Условие остановки: m ≥ min{t+1, n-1} (возможны исключения с ранней остановкой)
   • Сохранение истории подсчётов бесполезно для SBA
2. Улучшение Vectorized FloodSet:
   • Установление нетривиального условия ранней остановки
   • Улучшение исходного времени остановки t+1 из работы Raynal11
   • Но в некоторых случаях уступает Counting FloodSet
3. Практичность SendWaste:
   • Время принятия решения близко к оптимальному полному обмену (максимум на один раунд позже)
   • Значительное улучшение эффективности по сравнению с протоколом Dwork-Moses
   • Обеспечивает хороший баланс между теоретической оптимальностью и практической осуществимостью
4. Ценность теоретической базы:
   • Метод программ на основе знаний эффективно характеризует оптимальность
   • Теория отношений хранения информации удобна для сравнения протоколов
   • Предоставляет систематический метод анализа протоколов с ограниченным обменом информацией

Ограничения

1. Предположение об уникальности решения

Текущая установка:

• Агенты могут принимать одно и то же решение несколько раз
• Локальное состояние не записывает факт принятого решения
• Не удовлетворяет свойству «уникального решения» (Unique Decision)

Влияние:

• Облегчает сравнение протоколов и анализ обмена информацией
• Но отличается от стандартной спецификации SBA

Пояснение авторов:

• Предположение, что модификация для уникального решения сохранит оптимальность
• Результаты van der Meyden8 поддерживают это предположение
• Требует других техник доказательства (будущая работа)

2. Ограничение модели отказов

Текущая модель: Только отказы при сбое

Не охватывает:

• Общие пропуски (пропуски отправки/получения)
• Византийские отказы (вредоносное поведение)

Вызовы:

• Оптимальный протокол при общих пропусках требует NP-hard вычисления 10
• Протоколы с ограниченным обменом за полиномиальное время особенно ценны

3. Предположение о синхронности

Сильное предположение:

• Синхронные часы
• Известная верхняя граница времени доставки сообщений
• Коммуникация на основе раундов

Практические ограничения:

• Неприменимо к асинхронным системам
• Модели частичной синхронности не рассмотрены

4. Двоичное соглашение

Упрощение: Рассматриваются только Values = {0, 1}

Расширяемость: Многозначное соглашение может требовать другого анализа

Будущие направления

1. Модель общих пропусков (явно указано авторами)

Цель: Найти протокол SBA за полиномиальное время, оптимальный при ограниченном обмене информацией

Значение:

• Оптимальный полный обмен требует NP-hard вычисления
• Ограниченный обмен может избежать вычислительной сложности
• Высокая практическая ценность

2. Свойство уникального решения

Работа:

• Модификация протоколов для записи состояния решения
• Доказательство сохранения оптимальности после модификации
• Применение техник van der Meyden8

3. Асинхронные и частично синхронные модели

Расширение:

• Исследование оптимальности при ограниченном обмене в асинхронной среде
• Анализ моделей частичной синхронности

4. Византийские отказы

Вызовы:

• Вредоносные агенты могут отправлять ложную информацию
• Требуются более сложные механизмы проверки

5. Практическая реализация и верификация

Направления:

• Реализация протокола SendWaste в реальных системах
• Тестирование производительности
• Разработка инструментов формальной верификации

Глубокая оценка

Преимущества

1. Теоретическая строгость (★★★★★)

Формальная полнота:

• Полная математическая база: интерпретируемые системы, семантика теории знаний, определение оптимальности
• Все теоремы имеют строгие доказательства (хотя расширенная аннотация опускает детали)
• Ясная цепь логических рассуждений

Методологические инновации:

• Теория отношений хранения информации (Предложение 1) предоставляет элегантный инструмент сравнения
• Структура реализации программ на основе знаний унифицирует анализ оптимальности

2. Практическая ценность (★★★★☆)

Протокол SendWaste:

• Решает противоречие между теоретической оптимальностью и практической эффективностью
• Конкретные улучшения сложности (O(nt)→O(n), O(t)→O(1))
• Подходит для сценариев с большим t (крупномасштабные распределённые системы)

Оптимизация протоколов:

• Улучшение условий остановки из литературы
• Теоретические гарантии для практических систем

3. Систематический анализ (★★★★★)

Полное охватывание:

• Анализ множественных протоколов из литературы
• Сравнение в единой базе
• Ясные таблицы производительности (таблица 1)

Глубокие выводы:

• Раскрытие бесполезности исторической информации для SBA (в отличие от EBA)
• Объяснение ценности различных типов информации

4. Ясность изложения (★★★★☆)

Хорошая структура:

• Логичный поток от контекста к конкретным протоколам
• Отдельные разделы для каждого протокола, удобно для понимания

Читаемость:

• Баланс между техническими деталями и интуитивными объяснениями
• Ясный псевдокод

Недостатки

1. Отсутствие экспериментальной верификации (★★☆☆☆)

Чисто теоретическая:

• Нет реальной реализации системы
• Нет тестирования производительности
• Нет сравнения с практическими протоколами (Paxos, Raft)

Влияние:

• Практическое улучшение производительности не количественно
• Неизвестны константные множители и скрытые затраты

2. Ограничения расширенной аннотации (★★★☆☆)

Опущенные доказательства:

• Большинство доказательств теорем не приведены
• Сложно проверить технические детали
• Требуется обращение к полной версии

Ограниченная глубина:

• Анализ некоторых протоколов поверхностный
• Недостаточное обсуждение граничных случаев

3. Ограничение применимости (★★★☆☆)

Сильные предположения:

• Ограничение синхронной моделью
• Только отказы при сбое
• Двоичное соглашение

Обобщаемость:

• Неясно, могут ли результаты распространяться на другие установки

4. Разрыв с практическими протоколами (★★☆☆☆)

Промышленные протоколы:

• Не обсуждается связь с Paxos, Raft и т.д.
• Факторы реальных систем (задержка сети, частичные отказы) не рассмотрены

Оценка влияния

1. Вклад в область (★★★★★)

Теоретический прогресс:

• Заполнение пробела в оптимальности SBA при ограниченном обмене информацией
• Новая перспектива для проектирования распределённых алгоритмов

Методология:

• Структура программ на основе знаний применима к другим проблемам
• Теория отношений хранения информации имеет универсальное значение

2. Потенциал цитирования (★★★★☆)

Вероятные сценарии цитирования:

• Исследование протоколов распределённого консенсуса
• Применение теории знаний в информатике
• Проектирование отказоустойчивых систем
• Механизмы консенсуса блокчейна

Ограничения:

• Теоретическая направленность может ограничить цитирование в инженерных областях

3. Воспроизводимость (★★★★☆)

Теоретические результаты:

• Математические доказательства проверяемы
• Структура ясна и воспроизводима

Реализация:

• Описание протоколов достаточно детально
• Но нет реализации кода

4. Вдохновение для последующих исследований (★★★★★)

Явные направления:

• Модель общих пропусков
• Свойство уникального решения
• Реализация в реальных системах

Потенциальные расширения:

• Другие модели отказов
• Асинхронная среда
• Многозначное соглашение

Применимые сценарии

1. Идеальные сценарии применения

Крупномасштабные синхронные системы:

• Большие n и параметр отказоустойчивости t
• Явное преимущество SendWaste (по сравнению с Dwork-Moses)

Среды с ограниченными ресурсами:

• Чувствительность к размеру сообщения (например, IoT)
• Ограниченная вычислительная мощность
• Подходят FloodSet или SendWaste

Теоретические исследования:

• Анализ оптимальности распределённых алгоритмов
• Применение теории знаний

2. Неприменимые сценарии

Асинхронные системы:

• Отсутствие предположения о синхронных часах
• Требуется другая теоретическая база

Византийская среда:

• Наличие вредоносных узлов
• Требуются дополнительные механизмы верификации

Строгие требования реального времени:

• Требуется гарантия детерминированной задержки
• Может потребоваться более агрессивная ранняя остановка

3. Практические соображения системы

Интеграция с промышленными протоколами:

• Идеи SendWaste могут вдохновить оптимизацию Raft/Paxos
• Требуется адаптация к модели частичной синхронности

Гибридный подход:

• Использование ограниченного обмена в нормальных условиях
• Переключение на полный обмен в исключительных ситуациях

Ключевые ссылки

1. Alpturer, Halpern & van der Meyden (2023): PODC 2023, прямой предшественник данной работы, исследование оптимальности EBA при ограниченном обмене информацией
2. Dwork & Moses (1990): I&C, классическая работа, установление связи SBA с общим знанием, предложение оптимального протокола полного обмена
3. Halpern & Moses (1990): JACM, основная теория знания и общего знания в распределённой среде
4. Lynch (1996): учебник «Distributed Algorithms», источник протокола FloodSet
5. Moses & Tuttle (1988): Algorithmica, программирование синхронных действий с использованием общего знания
6. Raynal (2002): PRDC, источник Vectorized FloodSet
7. Castañeda et al. (2017): NETYS, источник Counting FloodSet
8. van der Meyden (2024): на рассмотрении, связанная работа о свойстве уникального решения

Общая оценка

• Теоретический вклад: ★★★★★ (5/5)
• Практическая ценность: ★★★★☆ (4/5)
• Строгость: ★★★★★ (5/5)
• Инновационность: ★★★★☆ (4/5)
• Полнота: ★★★☆☆ (3/5, ограничено форматом расширенной аннотации)

Общая оценка: Это высококачественная работа по теоретической информатике, которая вносит важный вклад в анализ оптимальности протоколов распределённого консенсуса. Предложение протокола SendWaste демонстрирует, как теоретические выводы могут направлять проектирование практических систем. Несмотря на отсутствие экспериментальной верификации, строгий теоретический анализ и систематическое сравнение протоколов делают её важным справочником в этой области. Для исследователей, работающих над распределёнными алгоритмами, применением теории знаний или проектированием отказоустойчивых систем, данная работа предоставляет ценные теоретические инструменты и методы анализа.