Summary: In this work, we consider a generalized fault model [F. P. Junqueira and K. Mazullo, “Synchronous consensus for dependent process failures”, in: Proceedings of the 23rd international IEEE conference on distributed computing systems, ICDCS’03. Los Alamitos, CA: IEEE Computer Society. 274–283 (2003; doi:10.1109/ICDCS.2003.1203476); P. Kuznetsov, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 106, 54–77 (2012; Zbl 1261.68030); M Hirt and U. Maurer, “Complete characterization of adversaries tolerable in secure multi-party computation”, in: Proceedings of the 16th annual ACM symposium on principles of distributed computing, PODC’97. New York, NY: Association for Computing Machinery (ACM). 25–34 (1997; doi:10.1145/259380.259412)] that can be used to represent a wide range of failure scenarios, including correlated failures and non-uniform node reliabilities. Under the generalized fault model, we explore iterative approximate Byzantine consensus (IABC) algorithms [N. H. Vaidya et al., in: Proceedings of the 2012 ACM symposium on principles of distributed computing, PODC ’12. New York, NY: Association for Computing Machinery (ACM). 365–374 (2012; Zbl 1301.68168)] in arbitrary directed networks. We prove a tight necessary and sufficient condition on the underlying communication graph for the existence of IABC algorithms.{ }We propose a new IABC algorithm for the generalized fault model, and present a transition matrix-based proof to show the correctness of the proposed algorithm. While transition matrices have been used to prove correctness of non-fault-tolerant consensus [A. Jadbabaie et al., “Coordination of groups of mobile autonomous agents using nearest neighbor rules”, IEEE Trans. Autom. Control 48, No. 6, 988–1001 (2003; doi:10.1109/TAC.2003.812781)], this paper is the first to extend the technique to Byzantine fault-tolerant algorithms.
For the entire collection see [Zbl 1322.68011].