Abstrakt. Vi tillhandahåller en svit av omöjlighetsresultat och lägre gränser för det antal processer och rundor som krävs för synkront samförstånd under övergående länkfel. Våra resultat visar att samförstånd kan lösas även i närvaro av O(n 2 ) rörlig underlåtenhet och / eller godtyckliga länkfel per runda, förutsatt att både antalet berörda utgående och inkommande länkar i varje process begränsas. Om vi tar ett steg längre mot de svagaste förhållanden under vilka samförstånd kan lösas, kan våra resultat tillämpas på en mängd olika dynamiska fenomen som tillfälliga kommunikationsfel och end-to-end-fördröjningsvariationer. Vi visar också att vår modell överträffar alternativa länk misslyckande modellering metoder i form av antagande täckning. Nyckelord. Feltolerant distribuerade algoritmer, konsensus, övergående länkfel, omöjliga resultat, lägre gränser, antagande täckningsanalys. AMS-ämnesklassificeringar. 68Q25, 68Q85, 68W15, 68W40 1. Inledning. De flesta undersökningar på feltoleranta distribuerade algoritmer som utförts tidigare bygger på modeller för processfel. Varje fel som uppstår i ett system tillskrivs antingen sändnings- eller mottagningsprocessen här, oavsett om det faktiska felet inträffar vid denna process eller snarare på den mellanliggande kommunikationsvägen. Dessutom anses en process som begår ett enda fel ofta "statiskt" felaktigt under hela avrättningen, även om dess misslyckande är övergående. Även om sådana modeller för processfel tillräckligt fångar många viktiga scenarier, inklusive kraschfel där en felaktig process bara slutar fungera, och bysantinska fel där en felaktig process kan göra något, är de inte särskilt lämpliga för att modellera mer dynamiska fenomen. Särskilt med tanke på den stadigt ökande dominansen av kommunikation över beräkning i moderna distribuerade system, i kombination med den höga tillförlitligheten hos moderna processorer och robusta operativsystem design, övergående kommunikationsfel såsom förlorade eller icke-erkända paket (synkroniseringsfel), CRC fel (datakorruption), och överskridanden mottagare (packet buffertspill) alltmer dominerar verkliga misslyckanden. Ett annat dynamiskt fenomen som man ofta stöter på i praktiken är oförutsägbara variationer i förseningarna från början till slut i multihop-nät som Internet, som till exempel orsakas av tillfällig överbelastning av nätet och tillfälliga fel på routern. Eftersom alltför stora förseningar från end-to-end uppträder som utelämnanden i klassiska (semi-)synkrona system och andra tids(out)baserade metoder, till exempel [3–5, 7, 39, 43, 51, 53], kan sådana tidsvariationer också betraktas som övergående länkfel. De särskiljande egenskaperna hos sådana fel är a) att de påverkar den väg (termerad länk i uppföljaren) som förbinder två processer, snarare än de endpoints (processerna), och b) att de är mobila [58], eftersom olika länkar kan misslyckas vid olika tidpunkter. Därför kan förmågan att kommunicera [i rätt tid] med andra processer i systemet inte statiskt tillskrivas en process här: Om länkfelsfrekvensen är tillräckligt hög, kommer det aldrig att finnas en uppsättning icke-tomma processer som visas
För länkfel i kompletta grafer, Schmid, Weiss, och Keidar visade omöjligt resultat och lägre gräns för antalet noder för synkront samförstånd under övergående Bysantine länk fel REF; dock noderna är alltid felfria.
Impossibility results and lower bounds for consensus under link failures
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}