Aspectos Práticos sobre o Consenso Bizantino entre Participantes Desconhecidos
Resumo
Protocolos de acordo formam a base para a solução da maioria dos problemas que envolvem sistemas distribuídos e confiáveis. Apesar de o consenso ter sido amplamente estudado em ambientes clássicos, onde o conjunto de participantes é conhecido, poucos trabalhos consideram este problema em ambientes dinâmicos e auto-organizáveis, onde os participantes da computação são, a priori, desconhecidos. Recentemente foi proposta uma solução para o problema do consenso Bizantino entre participantes desconhecidos, chamada BFT-CUP (Byzantine Consensus with Unknown Participants), a qual busca definir o grau de conhecimento, sobre a composição do sistema, necessário e suficiente para que este problema admita solução. Este trabalho complementa os resultados teóricos obtidos até então e busca analisar aspectos práticos da realização do BFT-CUP. Primeiramente, este problema é analisado em redes MANETs (Mobile Ad Hoc Networks) através de simulações de vários cenários realistas, onde é possível verificar quais são os parâmetros e configurações necessários para que os participantes do sistema consigam resolver o BFT-CUP com uma alta probabilidade. Além disso, também é apresentado um estudo acerca da utilização do BFT-CUP em redes VANETs (Veicular Ad Hoc Networks), através de uma analise sobre a conectividade veicular da cidade de Porto - Portugal.
Referências
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.
