Информатика · объяснение и практика

FLP ограничивает гарантированное завершение консенсуса, а не запрещает все решения

Правильно сформулировать невозможность детерминированного асинхронного консенсуса при одном возможном crash-отказе и отделить безопасность от живости.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Компьютерные сети и веб · Учебная карта

Главная мысль

Результат FLP показывает: в полностью асинхронной модели с надёжной передачей сообщений и одним возможным остановившимся процессом детерминированный протокол не может гарантировать завершение консенсуса во всех допустимых исполнениях при сохранении требуемой корректности.

Метод и постановка

Укажите три требования задачи. Согласие запрещает разные решения у корректных участников. Допустимость связывает решение с входами, чтобы протокол не обходил задачу постоянным ответом. Завершение требует, чтобы корректные участники когда-нибудь приняли решение. Невозможность относится к совместному выполнению этих требований в объявленной модели.

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

Проверка и границы вывода

Идея доказательства использует неразрешённое состояние, из которого ещё возможны решения разных значений. Планировщик может выбирать следующий разрешённый шаг так, чтобы сохранять эту неопределённость. Получается допустимое бесконечное исполнение без решения. Это утверждение о существовании плохого исполнения, а не о том, что любая обычная попытка протокола обязательно зависает.

Практические протоколы получают полезные гарантии, меняя предпосылки: добавляют частичную синхронность, подходящие детекторы отказов или рандомизацию с собственной вероятностной формулировкой завершения. Это не опровержения теоремы. Также FLP не запрещает сохранять согласие, пока решение откладывается. В инженерном отчёте отдельно назовите, при каких сетевых условиях протокол остаётся безопасным и при каких начинает гарантированно продвигаться. Без такого разделения слово «работает» смешивает два разных обязательства системы.

Пример

Три процесса ждут подтверждение от третьего участника. В одном исполнении он остановился, в другом просто очень медленный. До прихода нового сообщения два остальных видят одинаковую историю, сколько бы локальных секунд ни прошло.

Правило «после секунды он точно отказал» добавляет предположение о времени, которого в полностью асинхронной модели нет. Такое предположение может быть полезно практически, но должно быть явно включено в новую гарантию.

От чтения к действию

А теперь — вы

Что именно допускает FLP для безопасного детерминированного протокола в указанной модели?

Частые вопросы

Один возможный отказ значит, что отказ обязательно случится?

Нет. Протокол должен выдерживать разрешённые отказы; плохое исполнение не обязано содержать фактический crash.

Рандомизация отменяет исходную теорему?

Она меняет детерминированную предпосылку и требует отдельного вероятностного анализа.

Углублённый разбор

Частичная синхронность после стабилизации задержек

Частичная синхронность позволяет доказывать прогресс после стабилизации задержек, сохраняя безопасность и до неё. Увеличиваемый тайм-аут может в конце концов превысить нужный бюджет, хотя участник не знает момента, когда это впервые стало верно.

Перед началом: Безопасность и живость; Ограничение задержки сообщения.

Стабилизация является условием исполнения

Возьмём модель, в которой после некоторого конечного момента GST сообщения между корректными участниками укладываются в конечную границу Δ и шаги обработки тоже ограничены. До GST задержки могут быть сколь угодно велики. Участники не получают сигнала «стабилизация наступила» и могут заранее не знать подходящую границу. Это отличается от полностью синхронной модели с известными сроками с самого начала.

Тайм-аут до стабилизации означает лишь отсутствие ответа в выбранном окне, а не доказанный отказ. Корректный протокол должен сохранять согласие при таких ошибочных подозрениях. Доказательство завершения затем использует достаточно длинный стабильный интервал, корректного координатора и остальные условия протокола. Одной фразы «сеть стала быстрой» для полного доказательства консенсуса недостаточно.

Удвоение бюджета когда-нибудь покрывает конечную границу

Если фаза требует одного запроса, ограниченной обработки и одного ответа, достаточный бюджет имеет вид B=2Δ+c при принятой модели часов. Последовательность положительных тайм-аутов 1,2,4,8,… неограниченно растёт, поэтому некоторое значение превысит B. При бесконечном продолжении попыток найдётся и попытка, начинающаяся после GST с таким бюджетом.

Из этого не следует известная заранее верхняя граница общего времени от запуска: GST может быть сколь угодно поздним. Также нужны корректное сопоставление ответов эпохам и защита от запоздалых сообщений прежних попыток. Иначе поздний ответ способен быть ошибочно принят за подтверждение нового предложения и нарушить безопасность, даже когда тайм-ауты уже достаточно велики.

Кворум и тайм-аут решают разные части задачи

Для пяти участников два кворума по три пересекаются хотя бы в одном участнике: 3+3−5=1. Это комбинаторный факт, не зависящий от задержек. Но само пересечение не доказывает безопасность всех раундов: протокол должен хранить и переносить сведения о ранее принятых значениях по своим правилам. Тайм-аут не заменяет эти правила, а помогает организовать попытки прогресса.

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

Первая достаточно длинная попытка

Условие. После GST=9 задержка каждого направления не больше 3, обработка запроса не больше 1. Попытки начинаются с момента 10 и используют последовательно бюджеты 1,2,4,8; координатор и нужные отвечающие участники корректны. Найдите первый бюджет, покрывающий худшее время ответа.

  1. Худший ответ занимает 3+1+3=7 единиц. Бюджеты один, два и четыре этого не покрывают.
  2. При последовательных попытках их старты равны 10,11,13,17. Первые три могут истечь до ответа соответствующего раунда.
  3. Четвёртая попытка имеет бюджет восемь, дедлайн 25 и ответ не позже 24. Следовательно, она успевает при заданной модели.
  4. Для пяти участников кворум размера три пересекает любой другой такой кворум минимум в одном участнике. Это проверяется отдельно и не расширяет расчёт одной фазы до полного доказательства консенсуса.

Ответ. Первый достаточный бюджет — 8; четвёртый ответ приходит не позже 24 при дедлайне 25.

Проверка. Точная арифметика проверяет все четыре окна; перебор всех трёхэлементных подмножеств пяти участников подтверждает минимальное пересечение один.

Где легко ошибиться. Не объявляйте истечение тайм-аута доказанным отказом и не считайте расчёт одной фазы полным доказательством консенсуса. Границы времени и правила безопасности проверяются отдельно.

Проверьте понимание

Какой из бюджетов гарантированно покрывает время семь?

Вопросы к этой главе

Участник знает, что GST прошёл?

В выбранной модели нет. Доказательство анализирует исполнение снаружи; сам протокол продолжает действовать по своим сообщениям и увеличиваемым бюджетам.

Должен ли протокол быть безопасным до GST?

Да. Нарушение согласия нельзя исправить последующей стабилизацией сети. Условие после GST помогает живости, но не разрешает временно принимать несовместимые решения.

Сверить определения и условия

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

  • Dwork, Lynch, Stockmeyer: Partial Synchrony

    Прочитаны введение, варианты неизвестных границ и GST, разделение safety/termination. Собственный расчёт бюджетов 1,2,4,8 проверяет только достаточность тайм-аута для одной ограниченной фазы; не выдаётся за полный протокол консенсуса.

Подозрение детектора отказов и настоящий сбой

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

Перед началом: Crash-отказ; Квантор «в конце концов навсегда».

Полнота относится к настоящим отказам

Сильная полнота означает: каждый действительно остановившийся процесс в конце концов постоянно подозревается каждым корректным процессом. Слово «постоянно» исключает детектор, который иногда замечает сбой, а затем бесконечно забывает его. Слабая полнота требует такого постоянного подозрения хотя бы у одного корректного наблюдателя для каждого отказавшего.

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

Постоянная и eventual точность разрешают разные ошибки

Сильная точность означает: ещё не отказавший наблюдатель не подозревает процесс до отказа последнего. Это относится и к участникам, которые остановятся позднее. Eventual strong accuracy требует существования конечного времени, после которого корректные процессы больше не подозревают корректных. До этого времени возможны ложные подозрения всех корректных участников. Класс P сочетает сильную полноту с сильной точностью, а ♦P — с eventual strong accuracy.

Таким образом, один ранний ложный сигнал исключает P, но не обязательно ♦P. И наоборот, редкие ложные сигналы через неограниченные промежутки не удовлетворяют eventual точности: последнего ошибочного момента нет. Слово «eventually» относится ко всему бесконечному хвосту, а не к тому, что последние десять измерений выглядели хорошо.

Конечный журнал не удостоверяет бесконечный класс

Для строгой классификации истории нужно задать её продолжение или доказать свойства алгоритма в модели задержек. Любой конечный спокойный префикс можно продолжить новой ошибкой. Поэтому учебная история ниже задаёт постоянный хвост явно; это математическое условие примера, а не прогноз по наблюдениям. В реальной системе измерения дают свидетельства эксплуатации, но не заменяют модельную гарантию.

Использующий детектор протокол должен быть безопасен при разрешённых его классом ошибках. Подозрение может заставить сменить координатора, однако не должно само по себе отменять уже принятые обязательства или разрешать несовместимое решение. Класс детектора — дополнительная предпосылка доказательства, а не универсальное разрешение считать подозреваемый узел навсегда исчезнувшим.

Ошибки закончились, настоящий сбой остался

Условие. Процессы A и B корректны, C останавливается в момент 5. A ложно подозревает B только в момент 2, B ложно подозревает A только в момент 3. Начиная с момента 7 оба корректных процесса навсегда подозревают ровно C; других подозрений нет. Классифицируйте историю.

  1. После момента семь каждый корректный наблюдатель постоянно подозревает единственный отказавший процесс C. Сильная полнота выполнена.
  2. Ранние подозрения B у A и A у B нарушают сильную точность. Следовательно, история не удовлетворяет классу P.
  3. После момента четыре ложных подозрений корректных процессов уже нет и по условию они больше не появятся. Eventual strong accuracy выполнена.
  4. Вместе с сильной полнотой это даёт ♦P. Вывод использует явно заданный бесконечный хвост, а не только просмотр событий до седьмого момента.

Ответ. История соответствует ♦P и не соответствует P.

Проверка. Проверка конечного префикса и символически постоянного хвоста устанавливает обе eventual границы; события 2 и 3 служат отдельными контрпримерами сильной точности.

Где легко ошибиться. Не отождествляйте подозрение с отказом и не выводите eventual гарантию из конечного периода без ошибок. Классификация требует кванторов над всем дальнейшим исполнением.

Проверьте понимание

Какой наиболее сильный из перечисленных вариантов подходит истории?

Вопросы к этой главе

Если C подозревает живой A после своего отказа?

После остановки C новых шагов нет. Однако до своего отказа C остаётся наблюдателем для strong accuracy: он не должен подозревать ещё живой A. Для eventual точности достаточно условия через процессы, корректные во всём исполнении.

Бесконечно редкие ошибки допустимы для ♦P?

Нет, если они снова и снова затрагивают корректных участников. Eventual strong accuracy требует конечной границы, после которой таких ошибок не будет вовсе.

Сверить определения и условия

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

  • Chandra and Toueg: Unreliable Failure Detectors

    Прочитаны §2.3 strong completeness, strong accuracy и eventual strong accuracy, затем классы P/♦P. Собственная бесконечная история задаётся конечным префиксом и явно постоянным хвостом; классификация не выводится из одного конечного журнала.

Test-and-set решает консенсус двоих, но не произвольного числа

В общей памяти мощность атомарного объекта измеряется числом процессов, которым он позволяет решить wait-free консенсус вместе с регистрами. Test-and-set уже сильнее чтения и записи: он выбирает победителя для двоих. Но это не универсальный примитив консенсуса для любого числа участников.

Перед началом: Атомарный read-modify-write; Crash-stop процесс.

Число консенсуса относится к точной модели

Процессы асинхронны и могут навсегда остановиться. Консенсус требует согласия всех принявших решение, выбора одного из предложенных значений и wait-free завершения каждого продолжающего делать шаги процесса. Wait-free означает конечное число собственных шагов независимо от скоростей остальных. Здесь используются детерминированные алгоритмы, атомарные регистры и заданный тип дополнительных объектов.

Consensus number типа — максимальное число процессов, для которых его экземпляры и регистры позволяют решить эту задачу; если ограничений нет, число бесконечно. Обычные read/write регистры имеют число 1, test-and-set —2, compare-and-swap — бесконечность. Это классификация возможностей реализации, а не оценка числа одновременно работающих потоков процессора или производительности конкретной программы.

Два предложения публикуются до выбора победителя

Объект TAS первоначально хранит 0. Каждая операция атомарно возвращает старое значение и ставит 1; первый вызов возвращает 0, все дальнейшие 1. Процесс i сначала пишет своё предложение в P[i], затем вызывает TAS. Если получил 0, решает собственное значение; если 1, решает P[1−i]. Для двоих проигравший точно знает, кто был победителем.

Предложение победителя записано до его TAS, поэтому проигравшему не нужно ждать следующего шага победителя. Даже если победитель остановился сразу после выбора, его значение доступно. Согласие следует из уникальности первого TAS, допустимость — из происхождения P, завершение — из фиксированного числа атомарных операций. Если опубликовать предложение после TAS, остановка победителя оставит проигравшего без нужных данных.

Третий участник меняет силу задачи

При трёх процессах ответ 1 уже не сообщает, кто из двух других выиграл. Это объясняет неудачу непосредственного расширения, но само по себе ещё не доказывает невозможность любого алгоритма. Верхняя граница 2 устанавливается аргументом критического двухзначного состояния: шаги разных процессов либо коммутируют, либо перезаписывают общий эффект. Третий процесс не различает соответствующие продолжения, хотя требуемые единственные решения должны различаться.

Для TAS операции устанавливают одну и ту же единицу; регистровые операции также попадают в разобранные случаи. Теорема о таких interfering operations запрещает детерминированный wait-free консенсус троих даже при многих экземплярах объектов. Поэтому нижняя граница конструкцией для двоих вместе с верхней даёт ровно 2. Это отдельная модель общей памяти; ссылкой на сетевую FLP нельзя заменить указание доступных атомарных примитивов.

Победитель больше не делает шагов

Условие. Процессы 0 и1 предлагают 7 и9. Сначала 0 пишет P[0]=7, затем 1 пишет P[1]=9. После этого 0 получает TAS→0 и навсегда останавливается. Процесс 1 получает TAS→1. Что он может решить по двухпроцессному протоколу?

  1. Оба предложения опубликованы до вызовов TAS. Единственным победителем является 0, потому что его вызов первым заменил 0 на1.
  2. Процесс 1 получает 1 и читает P[0], где уже находится 7. Никакой дополнительной записи от остановившегося 0 не требуется.
  3. Процесс 1 решает 7, соблюдая допустимость. Если 0 успел бы решить, он тоже выбрал бы своё 7; остановка не допускает несовместимого решения 9.
  4. Для обратного порядка TAS выиграл бы1 и оба решения были бы9. Проверка всех чередований, сохраняющих публикацию перед TAS каждого процесса, подтверждает обе симметричные возможности.

Ответ. Продолжающий процесс 1 решает 7, не ожидая возобновления процесса 0.

Проверка. Перебор полных порядков атомарных публикаций, TAS и решений сверяет согласие и допустимость. Отдельные префиксы с остановкой победителя подтверждают, что его предложение уже доступно до прекращения шагов.

Где легко ошибиться. Не используйте ожидание завершения победителя внутри wait-free протокола и не выводите верхнюю границу иерархии из одного неудачного расширения на троих.

Проверьте понимание

Что решит процесс 1 в указанной трассе, если 0 остановился после своего TAS?

Вопросы к этой главе

Почему проигравший может читать чужое предложение без ожидания?

Возврат 1 означает, что чужой TAS уже произошёл. По программному порядку его публикация была ещё раньше. При атомарной последовательной модели памяти это гарантирует доступность предложения; перенос на язык со слабой памятью требует соответствующей реализации этих порядков.

Можно ли обойти границу, взяв много test-and-set объектов?

В определении типа уже разрешено использовать произвольное число его экземпляров вместе с регистрами. Поэтому теорема верхней границы относится и к такому варианту, при сохранении детерминированности и wait-free требования.

Сверить определения и условия

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

  • Maurice Herlihy: Wait-Free Synchronization, §3.2/Theorems3–4

    Прочитаны двухпроцессный протокол через RMW, consensus number и верхняя граница interfering operations. Test-and-set рассмотрен с атомарными регистрами и crash-stop процессами, без рандомизации. Собственные значения предложений и перебор чередований не заимствованы из статьи.

Paxos сохраняет уже выбранное значение между раундами

Выбор лидера ещё не объясняет, почему следующий раунд не выберет другое значение. В однослотовом Paxos безопасность поддерживают пересечение кворумов, обещания принимающих и обязательный перенос уже принятого значения. Разберём раунд, где новый предложивший видит противоречивые старые записи, но не имеет свободы выбрать любимое значение.

Перед началом: Большинство конечного множества и пересечение кворумов; Отказ процесса и задержка сообщения.

Выбрано большинством, принято одним — разные события

Есть три принимающих A, B, C; кворум состоит из любых двух. Номер предложения уникален и задаётся в общем строгом порядке; одному номеру соответствует одно значение. Принятие предложения отдельным участником не означает его выбора. Значение становится выбранным, когда одну пару номер—значение приняли участники кворума. Рассматривается один слот решения без византийских действий.

Каждый принимающий хранит наибольший обещанный номер и принятую пару наибольшего номера. На prepare(n) с допустимым новым номером он обещает не принимать меньшие номера и сообщает старую принятую пару, если она есть. Состояние обещаний и принятых предложений должно переживать предусмотренные моделью перезапуски. Простая потеря этих записей разрушила бы основание дальнейшего доказательства.

Первая фаза ограничивает право выбирать значение

Получив обещания кворума, предложивший смотрит не на большинство значений в ответах, а на наибольший принятый номер. Если хотя бы одна принятая пара сообщена, он обязан перенести её значение. Свой новый выбор разрешён лишь при отсутствии принятых пар во всех ответах кворума. Затем рассылается accept(n, v). Принимающий отклоняет его, если уже обещал больший номер; при приёме фиксируется и нижняя граница допустимого номера.

Пусть раньше большинство выбрало(m, v). Любой последующий кворум обещаний пересекает то большинство. Обещание большему номеру не позволяет пересекающемуся участнику позже принять m: значит, принятие m, необходимое для прежнего выбора, отражается в его истории до обещания. Если в ответах есть ещё более высокий принятый номер меньше нового n, его значение тоже должно быть v по индукции по номерам. Поэтому правило максимальной принятой пары сохраняет v.

Конкретный раунд и граница живости

Пусть A и B приняли(7, «синий»), а C сохранил одиночное старое принятие(2, «жёлтый»). Синий уже выбран. Новый раунд 11 собирает обещания B, C и получает пары 7 и 2. Он обязан предложить синий, даже если предпочитал жёлтый. Принятие(11, «синий») участниками B, C создаёт ещё один выбранный номер с прежним значением; противоречия безопасности нет.

Доказательство не утверждает, что раунд обязательно соберёт ответы. Конкурирующие предложившие могут бесконечно повышать номера и мешать друг другу; задержки могут не дать кворуму ответить. Для живости нужны дополнительные условия работы системы, например устойчивый предложивший и достаточная доставка. Сохранение выбранного значения — свойство безопасности, отдельное от завершения при произвольном асинхронном исполнении.

Почему две разные старые пары не дают нового выбора

Условие. У A, B принято(7, «синий»); у C принято(2, «жёлтый»). Раунд 11 получает prepare-ответы B, C. Какое значение он обязан предложить и что будет выбрано после accept у B, C?

  1. Множество{A, B} — кворум, поэтому синий уже выбран в раунде 7. Одиночная запись C не выбирала жёлтый.
  2. В ответах B, C наибольший принятый номер 7, его значение — синий. Оба участника обещают не принимать номера ниже 11.
  3. Раунд 11 посылает accept(11, «синий»), а не выбирает по своему предпочтению или большинству различных значений ответов.
  4. Если B, C не дали более новых обещаний, они принимают 11. Пара(11, «синий») выбрана новым кворумом; оба выбранных номера несут одно значение.

Ответ. Нужно перенести синий из максимальной принятой пары 7. При принятии B, C раунд 11 выбирает тот же синий.

Проверка. Все кворумы размера 2 на трёх участниках пересекаются. В этом запуске пересечение прежнего{A, B} и нового{B, C} равно{B}; его ответ несёт уже выбранное значение.

Где легко ошибиться. Не выбирайте значение большинством prepare-ответов и не путайте номер обещания с номером принятой пары.

Проверьте понимание

Раунд 11 получил от B пару(7, «синий»), а от C пару(2, «жёлтый»). Что он обязан предложить?

Вопросы к этой главе

Разрешено ли новое значение, если в одном ответе уже есть принятая пара?

Нет. При наличии принятых пар выбирают значение пары с наибольшим номером среди всего кворума ответов, даже если остальные пока ничего не приняли.

Достаточно ли пересечения кворумов без обещаний?

Нет. Нужны правила состояния принимающего и выбора значения предложившим. Одно пересечение множеств не запрещает участникам принимать несовместимые новые значения.

Сверить определения и условия

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

  • Lamport2001: Paxos Made Simple, §2.2

    Пересечение большинства, индуктивный инвариант сохранения значения и две фазы. История номеров 2,7,11 и разбор ошибочных способов выбора составлены для главы.

Обнаружение завершения считает работу и неподтверждённые сообщения

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

Перед началом: Отправка, доставка и сообщение в пути; Локальная активность и инвариант учёта.

Долг возникает при отправке, а не после доставки

Конечное диффузное вычисление без отказов и нового внешнего ввода после старта. В разобранной специализации связи активации образуют дерево, каждый некорневой процесс активируется один раз; сообщения и подтверждения надёжно доставляются ровно один раз.

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

У отправителя хранится out — число его отправленных работ, для которых ещё не получено итоговое подтверждение. Отправка сразу увеличивает out, включая ещё не доставленное сообщение. Подтверждение уменьшает его ровно один раз. Если увеличивать счётчик лишь после известия о доставке, появится опасный промежуток, в котором работа уже существует, но никто её не учитывает.

Последнее подтверждение удерживает всё поддерево

В нашей древесной специализации первый рабочий запрос задаёт процессу родителя. Процесс не подтверждает этот запрос немедленно. Он ждёт собственного перехода в пассивность и out=0, то есть завершения всех порождённых дочерних работ. Только тогда возвращает подтверждение родителю. Корень не имеет родителя и объявляет завершение при своей пассивности и out=0.

Индукция по дереву объясняет безопасность. Подтверждённый лист пассивен и больше не породит работу. Подтверждённая внутренняя вершина пассивна, а все её дочерние ветви уже подтверждены. Поэтому подтверждение представляет завершённое поддерево, а не только моментальную пустоту локальной очереди. Надёжная конечная доставка и конечность работ обеспечивают продвижение подтверждений к корню.

У более общей схемы нужны дополнительные правила

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

Здесь конкретный подсчёт проверяет дерево с однократной активацией, а не готовый общий сетевой протокол. Потерянное подтверждение может навсегда задержать объявление; выдуманное или повторно применённое способно сделать его ложным. Тайм-аут не заменяет подтверждение в асинхронной модели. Задача также отличается от консенсуса с возможным crash-отказом: у нас иная спецификация и более сильные предпосылки доставки.

Корень уже пассивен, но работа ещё летит к B

Условие. R посылает задание A. Получив его, A посылает задание B, затем завершает свою локальную работу. R тоже становится пассивным. Сообщение A→B пока в пути. Проследите out и подтверждения до объявления завершения.

  1. После отправки R→A счётчик out(R)=1. A удерживает родительское подтверждение R и при отправке A→B получает out(A)=1.
  2. Хотя R и A локально пассивны, R имеет долг 1, а A — долг 1. Завершение объявлять нельзя: рабочее сообщение ещё находится в канале A→B.
  3. B получает работу, выполняет её и становится пассивным без дочерних отправок. При out(B)=0 он посылает подтверждение A. До доставки подтверждения out(A) остаётся равным 1.
  4. Получив подтверждение B, A уменьшает out(A) до нуля и теперь вправе подтвердить R. Лишь после доставки этого последнего подтверждения out(R)=0; пассивный R объявляет глобальное завершение.

Ответ. Объявление допустимо после получения корнем подтверждения от A, а не при первом одновременном простое R и A.

Проверка. Для каждого ребра число отправленных работ минус число полученных подтверждений равно его непогашенному долгу. На финальном шаге все долги нулевые; раньше цепь R→A→B содержит хотя бы один учтённый незакрытый участок.

Где легко ошибиться. Не подтверждайте родительское задание сразу после передачи его части дальше. Завершение локального кода не означает завершение порождённой им работы.

Проверьте понимание

Когда пассивный R в задаче вправе объявить завершение?

Вопросы к этой главе

Рабочие каналы обязаны быть FIFO?

В этом однократно активируемом дереве порядок единственного задания по ребру не создаёт требования FIFO. Существенны надёжность и однократный учёт подтверждения. Для обобщённой реализации предпосылки объявляются заново.

Почему нулевой out одного пассивного узла недостаточен?

У него может не быть собственных потомков, но в другой ветви ещё есть работа. Глобальное свидетельство собирает именно корень после замыкания всех ветвей, а не произвольный лист.

Сверить определения и условия

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

  • Dijkstra и Scholten: EWD687

    Прочитаны модель диффузного вычисления, исходящий deficit и ограничение последнего входящего обязательства. Собственный пример R→A→B намеренно ограничен деревом однократных активаций; общий cornet не выдаётся за реализованный алгоритм.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться