Abstrakt. Vi studerar problemet med att uppnå tillförlitlig kommunikation med quiescentalgoritmer (dvs algoritmer som så småningom slutar skicka meddelanden) i asynkrona system med processkrascher och förlustlänkar. Vi visar först att det är omöjligt att lösa detta problem utan feldetektorer. Vi visar sedan hur man löser det med hjälp av en ny feldetektor, som kallas hjärtslag. I motsats till tidigare feldetektorer som har använts för att kringgå omöjliga resultat, är detektorn för fel i hjärtslagen genomförbar, och dess tillämpning använder inte tidsgränser. Dessa resultat har bred tillämplighet: de kan användas för att omvandla många befintliga algoritmer som tolererar endast processkrascher till tysta algoritmer som tolererar både processkrascher och meddelandeförluster. Detta kan tillämpas på samförstånd, atomsändningar, k-set-avtal, atomiskt engagemang osv.  Detta papper introducerar hjärtslag, en feldetektor som kan implementeras utan timeouts, och visar hur det kan användas för att lösa problemet med tystgående tillförlitlig kommunikation i asynkrona meddelande-passing system med processkrascher och förlust länkar. För att illustrera detta problem överväga ett system av två processer, en avsändare och en mottagare r, ansluten genom en asynkron dubbelriktad länk. Process s vill skicka några meddelanden m till r. Antag först att ingen process kan krascha, men länken mellan s och r kan förlora meddelanden (i båda riktningarna). Om vi inte sätter några begränsningar på meddelandeförluster är det naturligtvis omöjligt att säkerställa att r tar emot m. Ett antagande som vanligen görs för att kringgå detta problem är att länken är rättvis: om ett meddelande skickas oändligt ofta så tas det emot oändligt ofta. Med en sådan länk, s kunde upprepade gånger skicka kopior av m för alltid, och r är garanterat att så småningom ta emot m. Detta är opraktiskt, eftersom s aldrig slutar skicka meddelanden. Den uppenbara fixa är följande protokoll: a) s skickar en kopia av m upprepade gånger tills den tar emot ack(m) från r, och b) vid varje mottagande av m, r skickar ack(m) tillbaka till s. Observera att detta protokoll är tyst: slutligen ingen process skickar eller tar emot meddelanden.
Till exempel Aguilera et al. implementerade en feldetektor som möjliggör en tystgående tillförlitlig kommunikation när processer kan misslyckas REF.
Heartbeat : A Timeout-Free Failure Detector for Quiescent Reliable Communication
{'venue': 'ICDE', 'journal': None, 'mag_field_of_study': ['Computer Science']}