Adaptive indulgent consensus

Due to their fundamental role in the design of fault-tolerant distributed systems, consensus protocols have been widely studied. In particular, design and performance issues of indulgent consensus are a research topic that has gained considerable attention. Most of these protocols are asymmetric in the sense that different participants can assume different roles during the execution of the protocol. Usually, there is a process that assumes a "special" role and the others cooperate with it to finish the computation. However, the asymmetric structure of indulgent consensus protocols has a performance pitfall, specially when processes and communication channels are subject to considerable variability in load. The problem is that such protocols use an a priori agreed process ordering to select the process to perform the "special" role. We advocate that adaptive indulgent consensus protocols can be constructed by the introduction of an adaptive process ordering module. In this sense, it is proposed a generic implementation for this module. Based on this generic module we provide implementations of both ◊S- and Ω-based adaptive indulgent consensus protocols. Further, we investigate their performance by means of simulation and real experiments over a widely distributed system. The experimental results obtained show that the adaptive consensus protocols can outperform their non-adaptive counterparts in as much as 50%.