Модели времени и отказов

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

Definition

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

Scope

Эта тема охватывает синхронные, асинхронные и частично синхронные модели времени; таксономию отказов от сбоев (fail-stop) через пропуски и временные задержки до произвольных (византийских) ошибок; а также абстракцию детекторов отказов, которая связывает асинхронные системы и рассуждения, основанные на таймаутах. Эти модели являются аксиомами, из которых выводятся как результаты о возможности, так и о невозможности.

Core questions

• Какие границы задержки и скорости может предполагать алгоритм, и как таймауты зависят от них?
• Какие классы отказов — сбой, пропуск, временной, византийский — должен маскировать протокол?
• Как асинхронные системы могут быть дополнены детекторами отказов для обхода результатов о невозможности?

Key theories

Частичная синхронность

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

Иерархия моделей отказов

Отказы варьируются от доброкачественных сбоев (fail-stop) до произвольного византийского поведения, включая пропуски при отправке/получении и нарушения временных характеристик; серьезность отказов, которые протокол должен выдерживать, определяет требуемый коэффициент репликации и сложность сообщений.

Ненадежные детекторы отказов

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

Clinical relevance

Производственные системы неявно выбирают модель времени и отказов всякий раз, когда они устанавливают таймауты, выбирают коэффициент репликации или решают, следует ли защищаться от злонамеренных участников; неверные предположения являются частой первопричиной инцидентов с разделением мозга (split-brain) и потерей данных.

History

После того как асинхронная модель была признана слишком слабой для отказоустойчивого консенсуса, Дворк, Линч и Стокмайер ввели частичную синхронность в 1988 году, а Чандра и Туэг формализовали ненадежные детекторы отказов в 1996 году, предоставив тем самым инструментарий моделирования, который делает возможным практическое отказоустойчивое согласование.

Debates

Являются ли таймауты предположением о времени или детектором отказов?

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

Key figures

• Cynthia Dwork
• Nancy Lynch
• Larry Stockmeyer
• Tushar Chandra
• Sam Toueg

Seminal works

• dwork1988
• chandra1996
• lynch1996

Frequently asked questions

Почему надежное обнаружение отказов не может быть реализовано в чисто асинхронной системе?

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