Stopping Times of Distributed Consensus Protocols: A Probabilistic Analysis

Abstract

Given a model where each processor remains correct for an exponentially distributed random time and then fails independently of the others, we characterize system executions that permit the processors to reach consensus. We show that with non-zero probability, a protocol can achieve consensus even during executions where the number of actual processors to fail exceeds its resiliency.