Avslutar pålitlig sändning

Terminating Reliable Broadcast ( TRB ) är ett problem i distribuerad datoranvändning som kapslar in uppgiften att sända ett meddelande till en uppsättning mottagningsprocesser i närvaro av fel . I synnerhet kan avsändaren och alla andra processer misslyckas ("krascha") när som helst.

Problembeskrivning

Ett TRB-protokoll organiserar vanligtvis systemet i en sändningsprocess och en uppsättning mottagningsprocesser, som kan inkludera avsändaren själv. En process kallas "korrekt" om den inte misslyckas vid något tillfälle under dess utförande. Målet med protokollet är att överföra data ("meddelandet") från avsändaren till uppsättningen av mottagande processer. En process kan utföra många I/O -operationer under protokollexekvering, men "levererar" så småningom ett meddelande genom att skicka det till applikationen på den processen som anropade TRB-protokollet.

Protokollet måste ge viktiga garantier till mottagande processer. Alla korrekta mottagningsprocesser måste till exempel leverera avsändarens meddelande om avsändaren också är korrekt. En mottagningsprocess kan leverera ett speciellt meddelande, $\mathrm {SF}$ ("avsändaren är felaktig"), om avsändaren misslyckades, men antingen kommer alla korrekta processer att leverera $\mathrm {SF}$ eller så kommer ingen . En korrekt process garanteras därför att data som levererats till den också levererades till alla andra korrekta processer.

Mer exakt måste ett TRB-protokoll uppfylla de fyra formella egenskaperna nedan.

• Uppsägning : varje korrekt process ger ett visst värde.
• Giltighet : om avsändaren är korrekt och sänder ett meddelande $m$ , så levererar varje korrekt process $m$ .
• Integritet : en process levererar ett meddelande högst en gång, och om det levererar något meddelande $m\neq \mathrm {SF}$ , så sändes $m$ av avsändaren.
• Avtal : om en korrekt process levererar ett meddelande $m$ , så levererar alla korrekta processer $m$ .

Förekomsten av fel i systemet gör dessa egenskaper svårare att uppfylla. Ett enkelt men ogiltigt TRB-protokoll kan få avsändaren att sända meddelandet till alla processer och få mottagande processer att leverera meddelandet så snart det tas emot. Detta protokoll uppfyller dock inte överenskommelsen om fel kan uppstå: om avsändaren kraschar efter att ha skickat meddelandet till vissa processer, men innan det skickas till andra, kan den första uppsättningen processer leverera meddelandet medan den andra uppsättningen levererar $\mathrm {SF}$ .

TRB är nära relaterat, men inte identiskt, med det grundläggande distribuerade datorproblemet med konsensus .