Завершення надійної трансляції

Terminating reliable broadcast (TRB) (з англ. - Завершення надійної трансляції) - використовують для надійного  поширення повідомлень серед набору процесів. Зокрема, відправлення і будь-який інший процес можуть в будь-який момент завершитися з помилкою.

Опис проблеми

TRB протокол зазвичай організовує систему в процес відправки та набір процесів прийому, які також в себе можуть включати самого відправника. Процес може називатися "правильним", якщо він не виходить з ладу в будь-який момент його виконання. Метою протоколу є передача даних ("повідомлень") від відправника до набору процесів отримання. Під час виконання протоколу процес може представляти із себе безліч (вхідних/вихідних) операцій, але в кінцевому результаті доставляє повідомлення передаючи його в тому процесі, в якому він був викликаний протоколом.

Протокол повинен надавати великі гарантії для процесів отримання. Наприклад, всі правильні процеси отримання повинні доставляти повідомлення відправника, якщо відправник також є правильним. Процес отримання може доставити спеціальне повідомлення, "відправник несправний", якщо відправка не була виконана, але всі правильні процеси доставлять "відправник несправний", або "none” (значення відсутнє).

Протокол TRB повинен відповідати чотирьом властивостям:

• Цілісність: Якщо процес доставляє повідомлення не більше одного разу, і якщо він відправляє повідомлення, яке не дорівнює значенню "відправник несправний", то повідомлення було передано відправником.
• Обгрунтованість: Якщо відправник правильний і передає повідомлення, то всі правильні процеси врешті доставляють повідомлення.
• Угода: для будь-якого повідомлення, якщо правильний (будь-який) процес доставляє повідомлення, то кожний правильний процес доставляє повідомлення.
• Припинення: кожний правильний процес урешті-решт доставляє рівно одне повідомлення.

Наявність несправностей в системі ускладнює відповідність цим властивостям. Простий, але недійсний протокол TRB може змусити відправника надіслати повідомлення всім процесам, і отримуючі процеси доставлять повідомлення, як тільки воно буде отримано. Цей протокол, однак, не відповідає угоді, якщо можуть виникати помилки: якщо відправка не була проведена деякими процесами, то перш ніж відправити його іншим, перший набір процесів може доставити повідомлення, в той час як другий набір доставить "відправник несправний".

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

Примітки

1. Alvisi, Lorenzo (2006). "Consensus and Reliable Broadcast" [ 12 червня 2019 у Wayback Machine.] (PDF).