Прекращение надежного вещания

Прекращение надежной широковещательной рассылки ( TRB ) — это проблема в распределенных вычислениях , которая инкапсулирует задачу широковещательной передачи сообщения набору принимающих процессов при наличии сбоев . В частности, отправитель и любой другой процесс могут выйти из строя («зависнуть») в любой момент.

Описание проблемы

Протокол TRB обычно объединяет систему в процесс отправки и набор процессов получения, которые могут включать самого отправителя. Процесс называется «правильным», если он не дает сбоя ни на одном этапе своего выполнения. Целью протокола является передача данных («сообщения») от отправителя набору принимающих процессов. Процесс может выполнять множество операций ввода-вывода во время выполнения протокола, но в конечном итоге «доставляет» сообщение, передавая его приложению в том процессе, который вызвал протокол TRB.

Протокол должен предоставлять важные гарантии принимающим процессам. Например, все правильные процессы получения должны доставлять сообщение отправителя, если отправитель также прав. Получающий процесс может доставить специальное сообщение, $\mathrm {SF}$ («отправитель неисправен»), если отправитель потерпел неудачу, но либо все правильные процессы доставят $\mathrm {SF}$ или никто не будет. Таким образом, правильный процесс гарантирует, что данные, доставленные в него, также были доставлены всем другим правильным процессам.

Точнее, протокол TRB должен удовлетворять четырем формальным свойствам, указанным ниже.

• Завершение : каждый правильный процесс приносит некоторую пользу.
• Срок действия : если отправитель прав и передает сообщение. $m$, то каждый правильный процесс дает $m$.
• Целостность : процесс доставляет сообщение не более одного раза, и если он доставляет какое-либо сообщение $m\neq \mathrm {SF}$, затем $m$ было передано отправителем.
• Соглашение : если правильный процесс доставляет сообщение $m$, то все правильные процессы доставляют $m$.

Наличие неисправностей в системе затрудняет удовлетворение этих свойств. В простом, но недействительном протоколе TRB отправитель может транслировать сообщение всем процессам, а принимающие процессы доставляют сообщение сразу после его получения. Однако этот протокол не соответствует соглашению , если могут возникнуть сбои: если отправитель выходит из строя после отправки сообщения одним процессам, но до отправки его другим, то первый набор процессов может доставить сообщение, в то время как второй набор доставляет сообщение. $\mathrm {SF}$.

TRB тесно связана, но не идентична фундаментальной проблеме консенсуса распределенных вычислений .