Aspectos Práticos sobre o Consenso Bizantino entre Participantes Desconhecidos
Abstract
Agreement protocols form the basis for the solution of most problems involving reliable distributed systems. Although the consensus has been widely studied in classic environments, few studies have considered this problem in dynamic and self-organizing systems, where the set of participants are previously unknown. Recently, a solution to Byzantine fault-tolerant consensus with unknown participants (BFT-CUP) was proposed, which identifies the degree of knowledge, about the system composition, necessary and sufficient to solve the consensus. This paper complements these theoretical works by analyzing practical aspects about the BFT-CUP. First, this problem is analyzed in Mobile Ad Hoc Networks through simulations of several realistic scenarios, where we can identify what are the parameters and settings required to solve BFT-CUP with a high probability. Moreover, this paper studies the use of BFT-CUP protocols in Vehicular Ad Hoc Networks, by analyzing the vehicular connectivity of the city of Porto - Portugal.
References
Alchieri, E. A. P., Bessani, A. N., da Silva Fraga, J., and Greve, F. (2008). Byzantine consensus with unknown participants. In 12th International Conference On Principles Of DIstributed Systems, pages 22–40.
Aspnes, J. (2003). Randomized protocols for asynchronous consensus. Distributed Computing, 16(2-3):165–175.
Barr, R., Haas, Z. J., and van Renesse, R. (2004). Jist: Embedding simulation time into a virtual machine. In Proceedings o EuroSim Congress on Modelling and Simulation.
Barr, R., Haas, Z. J., and van Renesse, R. (2005). Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless, and Peer-to-Peer Networks, chapter Scalable Wireless Ad hoc Network Simulation, pages 297–311. CRC Press.
Ben-Or, M. (1983). Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract). In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing, pages 27–30.
Bettstetter, C. (2002). On the minimum node degree and connectivity of a wireless multihop network. In Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing - MobiHoc’02.
Bracha, G. (1984). An asynchronous |(n − 1)/3|-resilient consensus protocol. In Proceedings of the 3rd ACM symposium on Principles of Distributed Computing, pages 154–162.
Castro, M. and Liskov, B. (2002). Practical Byzantine fault-tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398–461.
Cavin, D., Sasson, Y., and Schiper, A. (2004). Consensus with unknown participants or fundamental self-organization. In Proceedings of the 3rd International Conference on Ad hoc Networks and Wireless - ADHOC-NOW 2004, pages 135–148.
Cavin, D., Sasson, Y., and Schiper, A. (2005). Reaching agreement with unknown participants in mobile self-organized networks in spite of process crashes. Technical Report IC/2005/026, EPFL - LSR.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.
Correia, M., Neves, N. F., and Veríssimo, P. (2006). From consensus to atomic broadcast: Time-free Byzantine-resistant protocols without signatures. The Computer Journal, 49(1).
Costa, V. F., Greve, F. G. P., , and Tixeuil, S. (2009). Consenso ft-cup em redes manets: Uma abordagem prática. In Anais do 27º Simpósio Brasileiro de Redes de Computadores - SBRC 2009.
Costa, V. F. and Greve, F. G. P. (2007). Aspectos práticos da realização do consenso ft-cup em redes móveis ad-hoc. In Anais VIII Workshop de Teste e Tolerância a Falhas- WTF 2007, Belém, PA, Brasil.
Dwork, C., Lynch, N. A., and Stockmeyer, L. (1988). Consensus in the presence of partial synchrony. Journal of ACM, 35(2):288–322.
Ferreira, M., Conceição, H., Fernandes, R., and Tonguz, O. K. (2009). Stereoscopic aerial photography: an alternative to model-based urban mobility approaches. In Proceedings of the sixth ACM international workshop on VehiculAr InterNETworking - VANET’09.
Ferreira, M., Fernandes, R., Conceição, H., Viriyasitavat, W., and Tonguz, O. K. (2010). Self-organized traffic control. In Proceedings of the seventh ACM international workshop on VehiculAr InterNETworking - VANET’10.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382.
Greve, F. G. P. and Tixeuil, S. (2007). Knowledge connectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks. In Proceedings of the International Conference on Dependable Systems and Networks - DSN, pages 82–91.
Kotzanikolaou, P., Mavropodi, R., and Douligeris, C. (2005). Secure multipath routing for mobile ad hoc networks. Wireless On-demand Network Systems and Services - WONS, pages 89–96.
Lamport, L., Shostak, R., and Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401.
Santi, P. (2005). Topology control in wireless ad hoc and sensor networks. ACM Comput. Surv., 37:164–194.
Aspnes, J. (2003). Randomized protocols for asynchronous consensus. Distributed Computing, 16(2-3):165–175.
Barr, R., Haas, Z. J., and van Renesse, R. (2004). Jist: Embedding simulation time into a virtual machine. In Proceedings o EuroSim Congress on Modelling and Simulation.
Barr, R., Haas, Z. J., and van Renesse, R. (2005). Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless, and Peer-to-Peer Networks, chapter Scalable Wireless Ad hoc Network Simulation, pages 297–311. CRC Press.
Ben-Or, M. (1983). Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract). In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing, pages 27–30.
Bettstetter, C. (2002). On the minimum node degree and connectivity of a wireless multihop network. In Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing - MobiHoc’02.
Bracha, G. (1984). An asynchronous |(n − 1)/3|-resilient consensus protocol. In Proceedings of the 3rd ACM symposium on Principles of Distributed Computing, pages 154–162.
Castro, M. and Liskov, B. (2002). Practical Byzantine fault-tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398–461.
Cavin, D., Sasson, Y., and Schiper, A. (2004). Consensus with unknown participants or fundamental self-organization. In Proceedings of the 3rd International Conference on Ad hoc Networks and Wireless - ADHOC-NOW 2004, pages 135–148.
Cavin, D., Sasson, Y., and Schiper, A. (2005). Reaching agreement with unknown participants in mobile self-organized networks in spite of process crashes. Technical Report IC/2005/026, EPFL - LSR.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.
Correia, M., Neves, N. F., and Veríssimo, P. (2006). From consensus to atomic broadcast: Time-free Byzantine-resistant protocols without signatures. The Computer Journal, 49(1).
Costa, V. F., Greve, F. G. P., , and Tixeuil, S. (2009). Consenso ft-cup em redes manets: Uma abordagem prática. In Anais do 27º Simpósio Brasileiro de Redes de Computadores - SBRC 2009.
Costa, V. F. and Greve, F. G. P. (2007). Aspectos práticos da realização do consenso ft-cup em redes móveis ad-hoc. In Anais VIII Workshop de Teste e Tolerância a Falhas- WTF 2007, Belém, PA, Brasil.
Dwork, C., Lynch, N. A., and Stockmeyer, L. (1988). Consensus in the presence of partial synchrony. Journal of ACM, 35(2):288–322.
Ferreira, M., Conceição, H., Fernandes, R., and Tonguz, O. K. (2009). Stereoscopic aerial photography: an alternative to model-based urban mobility approaches. In Proceedings of the sixth ACM international workshop on VehiculAr InterNETworking - VANET’09.
Ferreira, M., Fernandes, R., Conceição, H., Viriyasitavat, W., and Tonguz, O. K. (2010). Self-organized traffic control. In Proceedings of the seventh ACM international workshop on VehiculAr InterNETworking - VANET’10.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382.
Greve, F. G. P. and Tixeuil, S. (2007). Knowledge connectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks. In Proceedings of the International Conference on Dependable Systems and Networks - DSN, pages 82–91.
Kotzanikolaou, P., Mavropodi, R., and Douligeris, C. (2005). Secure multipath routing for mobile ad hoc networks. Wireless On-demand Network Systems and Services - WONS, pages 89–96.
Lamport, L., Shostak, R., and Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401.
Santi, P. (2005). Topology control in wireless ad hoc and sensor networks. ACM Comput. Surv., 37:164–194.
Published
2011-05-30
How to Cite
ALCHIERI, Eduardo Adilio Pelinson; TOMELIN, Luiz Renato; BESSANI, Alysson Neves; FRAGA, Joni da Silva.
Aspectos Práticos sobre o Consenso Bizantino entre Participantes Desconhecidos. In: FAULT TOLERANCE WORKSHOP (WTF), 12. , 2011, Campo Grande/MS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 63-76.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2011.23090.
