Failure model coverage under transient link failures

In a number of former papers, we analyzed several consensus and Byzantine agree-ment algorithms under a novel hybrid failure model for synchronous distributed systems. It extends traditional process failure models by allowing every process in the system to commit up to f sℓ send link failures and experience up to f r ℓ receive link failures per round, without being considered (process-)faulty. The present paper shows that this model—and hence our algorithms—can also be applied in systems with high transient link failures rates: Assuming that every link may fail inde-pendently with some probability p in every round, we derive the probability that the link failure bounds f sℓ, f r ℓ are respected during the entire execution of some communications-expensive Byzantine agreement algorithm. This probability can in fact be made (almost) as large as desired by increasing f rℓ and f s ℓ appropriately, even though n and hence the number of links that could fail systemwide increases as well. It turns out that our algorithms could even be applied in wireless systems, where link loss probabilities up to p = 10−2 are common. Key words: Fault-tolerant distributed systems, hybrid failure models, Byzantine agreement, transient link failures, assumption coverage