Terminating Reliable Broadcast

Кіріспе

Сенімді хабар таратуды тоқтату (TRB) - бұл қателер болған кезде хабарды қабылдау процестерінің жиынтығына тарату міндетін қамтитын, үлестірілген есептеулердегі мәселе. Әсіресе, жіберуші және кез келген басқа процесс кез келген уақытта сәтсіздікке ұшырауы мүмкін ("жағылу").

Мәселе сипаттамасы

TRB протоколы жүйелерді әдетте жіберу процессіне және қабылдау процестерінің жиынтығына ұйымдастырады, оған жіберушінің өзі кіруі мүмкін. Процесс "дөре" деп аталады, егер ол орындалу кезінде кез-келген уақытта сәтсіздікке ұшырамайды. Протоколдың мақсаты - деректерді ("хабарламаны") жіберушіден қабылдау процестерінің жиынтығына беру. Процесс протоколды орындау кезінде көптеген I/O операцияларды орындауы мүмкін, бірақ ақыр соңында TRB протоколын шақырған процестегі қосымшаға тапсыру арқылы хабарламаны "беріп береді". Хаттама қабылдау процестеріне маңызды кепілдіктер беруі тиіс. Мысалы, барлық дұрыс қабылдау процестері, егер жіберуші де дұрыс болса, жіберушінің хабарламасын беруі керек. Қабылдау процессі арнайы хабарды ("жөнелтуші ақаулы") жіберуі мүмкін, егер жіберуші сәтсіз болса, бірақ барлық дұрыс процестер немесе ешқайсысы жеткізбейді. Сондықтан оған берілген деректердің басқа да барлық дұрыс процестерге берілгендігі дұрыс процеске кепілдік беріледі. Нақтырақ айтқанда, TRB протоколы төмендегі төрт формалды қасиеттерге сәйкес болуы керек. Аяқтау: әрбір дұрыс процесс белгілі бір құндылық береді. Дұрысдық: егер жіберуші дұрыс болса және хабарды таратады, онда әрбір дұрыс процесс толықтықты береді: процесс хабарды ең көп дегенде бір рет береді, ал егер ол қандай да бір хабарды таратады, онда оны жіберуші таратты. Келісім: егер дұрыс процесс хабарды жеткізсе, онда барлық дұрыс процестер жеткізеді. Жүйедегі ақаулардың болуы осы қасиеттерді қанағаттандыруды қиындатады. Қарапайым, бірақ жарамсыз TRB протоколы жіберушінің хабарламаны барлық процестерге таратуы және қабылдау процестерінің хабарламаны алғаннан кейін дереу жеткізуі мүмкін. Алайда, егер қателер пайда болса, бұл протокол келісімді қанағаттандырмайды: егер хабарды кейбір процестерге жібергеннен кейін, бірақ басқаларға жіберместен бұрын жіберуші құлап кетсе, онда процестердің бірінші жиынтығы хабарды жеткізе алады, ал екінші жиынтық TRB-ді жеткізеді. Бұл консенсус туралы негізгі үлестірілген есептеу проблемасына жақын, бірақ бірдей емес.

A TRB protocol typically organizes the system into a sending process and a set of receiving processes, which may include the sender itself. A process is called "correct" if it does not fail at any point during its execution. The goal of the protocol is to transfer data (the "message") from the sender to the set of receiving processes. A process may perform many I/O operations during protocol execution, but eventually "delivers" a message by passing it to the application on that process that invoked the TRB protocol. The protocol must provide important guarantees to the receiving processes. All correct receiving processes, for example, must deliver the sender's message if the sender is also correct. A receiving process may deliver a special message, ("sender faulty"), if the sender failed, but either all correct processes will deliver or none will. A correct process is therefore guaranteed that data delivered to it was also delivered to all other correct processes. More precisely, a TRB protocol must satisfy the four formal properties below. Termination: every correct process delivers some value. Validity: if the sender is correct and broadcasts a message , then every correct process delivers Integrity: a process delivers a message at most once, and if it delivers some message , then was broadcast by the sender. Agreement: if a correct process delivers a message , then all correct processes deliver
The presence of faults in the system makes these properties more difficult to satisfy. A simple but invalid TRB protocol might have the sender broadcast the message to all processes, and have receiving processes deliver the message as soon as it is received. This protocol, however, does not satisfy agreement if faults can occur: if the sender crashes after sending the message to some processes, but before sending it to others, then the first set of processes may deliver the message while the second set delivers
TRB is closely related, but not identical, to the fundamental distributed computing problem of consensus.