Abstract
In this work, we consider a generalized fault model [7,9,5] 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 [15] 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 [6], this paper is the first to extend the technique to Byzantine fault-tolerant algorithms.
This research is supported in part by National Science Foundation award CNS 1059540 and Army Research Office grant W-911-NF-0710287. Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not necessarily reflect the views of the funding agencies or the U.S. government.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bhandari, V., Vaidya, N.H.: On reliable broadcast in a radio network. In: Proc. of ACM Symposium on Principles of Distributed Computing, PODC 2005 (2005)
Dasgupta, S., Papadimitriou, C., Vazirani, U.: Algorithms. McGraw-Hill Higher Education (2006)
Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM 33, 499–516 (1986)
Hajnal, J., Bartlett, M.S.: Weak ergodicity in non-homogeneous markov chains. In: Proceedings of the Cambridge Philosophical Society (1958)
Hirt, M., Maurer, U.: Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract). In: PODC 1997 (1997)
Jadbabaie, A., Lin, J., Morse, A.: Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control 48(6), 988–1001 (2003)
Junqueira, F.P., Marzullo, K.: Synchronous consensus for dependent process failures. In: ICDCS 2003 (2003)
Koo, C.-Y.: Broadcast in radio networks tolerating byzantine adversarial behavior. In: Proc. ACM Symp. on Principles of Distributed Computing, PODC 2004 (2004)
Kuznetsov, P.: Understanding non-uniform failure models. Bulletin of the European Association for Theoretical Computer Science (BEATCS) 106, 53–77 (2012)
Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. on Programming Languages and Systems (1982)
LeBlanc, H., Zhang, H., Sundaram, S., Koutsoukos, X.: Consensus of multi-agent networks in the presence of adversaries using only local information. In: HiCoNs 2012 (2012)
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann (1996)
Tseng, L., Vaidya, N.H.: Iterative approximate byzantine consensus under a generalized fault model. Technical report, CSL, UIUC (2012)
Vaidya, N.H.: Matrix representation of iterative approximate byzantine consensus in directed graphs. Technical report, CSL, UIUC (2012)
Vaidya, N.H., Tseng, L., Liang, G.: Iterative approximate byzantine consensus in arbitrary directed graphs. In: PODC 2012 (2012)
Wolfowitz, J.: Products of indecomposable, aperiodic, stochastic matrices. In: Proc. of the American Mathematical Society, vol. 14, pp. 733–737 (1963)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tseng, L., Vaidya, N. (2013). Iterative Approximate Byzantine Consensus under a Generalized Fault Model. In: Frey, D., Raynal, M., Sarkar, S., Shyamasundar, R.K., Sinha, P. (eds) Distributed Computing and Networking. ICDCN 2013. Lecture Notes in Computer Science, vol 7730. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35668-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-35668-1_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35667-4
Online ISBN: 978-3-642-35668-1
eBook Packages: Computer ScienceComputer Science (R0)