Abstract En överseende algoritm är en distribuerad algoritm som tolererar asynkrona perioder i nätverket när process krasch upptäckt är opålitlig. I detta dokument presenteras en snäv begränsning av tids komplexiteten hos algoritmer med eftergiven konsensus. Vi anser att en rundbaserad så småningom synkron modell, och vi visar att alla t-tåliga konsensus algoritm i denna modell, kräver minst t + 2 rundor för ett globalt beslut även i körningar som är synkrona. Vi jämför vår nedre gräns med den välkända t + 1 runda snäva gränsen för samförstånd i synkronmodellen. Vi bevisar sedan att det kommer att vara tight genom att ställa ut en ny t-tålig konsensusalgoritm i den så småningom synkrona modellen som når ett globalt beslut på runda t + 2 i varje synkron körning. Vår nya algoritm är i denna mening betydligt snabbare än den mest effektiva avlatent algoritm vi känner till, vilket kräver 2t + 2 rundor i synkrona körningar. Vår nedre gräns gäller rundbaserade konsensusalgoritmer med opålitliga feldetektorer som QP och QS, och vår matchande algoritm kan anpassas till sådana feldetektorer.
I ett tidigare dokument REF har vi övervägt en något annorlunda så småningom synkron modell, och studerat komplexiteten i konsensusalgoritmer i synkrona körningar med misslyckanden.
The inherent price of indulgence
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science']}