Abstract
Network overlays have been the subject of intensive research in recent years. The paper presents an overlay structure, S-Fireflies, that is self-stabilizing and is robust against permanent Byzantine faults. The overlay structure has a logarithmic diameter with high probability, which matches the diameter of less robust overlays. The overlay can withstand high churn without affecting the ability of active and correct members to disseminate their messages. The construction uses a randomized technique to choose the neighbors of each member, while limiting the ability of Byzantine members to affect the randomization or to disturb the construction. The basic ideas generalize the original Fireflies construction that withstands Byzantine failures but was not self-stabilizing.
This material is based in part upon work supported by ISF, ISOC, by the AFOSR under Award No. FA8750-06-2-0060, FA9550-06-1-0019, FA9550-06-1-0244, and by the National Science Foundation under Grant No. 0424422. Any opinions, findings, and conclusions or recommendations expressed in this publications are those of the author(s) and do not necessarily reflect the views of the AFOSR, NSF or ISF.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Dolev, S., Schiller, E.: Communicaiton adaptive self-stabilizing group membership service. IEEE Transactions on Parallel and Distributed Systems 14(7), 709–720 (2003)
Ghodsi, A., El-Ansary, S., Krishnamurthy, S., Haridi, S.: A self-stabilizing network size estimation gossip algorithm for peer-to-peer systems. Technical Report Technical Report T2005:16, SICS (2005)
Shafaat, T., Ghodsi, A., Haridi, S.: Handling network partitions and mergers in structured overlay networks. In: Proc. of the Seventh IEEE International Conference on Peer-to-Peer Computing, Galway, Ireland (September 2007)
Castro, M., Druschel, P., Ganesh, A., Rowstron, A., Wallach, D.S.: Secure routing for structured peer-to-peer overlay networks. In: Proc. of the 5th Usenix Symposium on Operation System Design and Implementation (OSDI), Boston, MA (December 2002)
Singh, A., Castro, M., Druschel, P., Rowstron, A.: Defending against Eclipse attacks on overlay networks. In: Proc. of the 11th European SIGOPS Workshop, Leuven, Belgium, ACM, New York (2004)
Johansen, H., Allavena, A., van Renesse, R.: Fireflies: Scalable support for intrusion-tolerant network overlays. In: Eurosys 2006, Leuven, Belgium (2006)
Stoica, I., Morris, R., Karger, D., Kaashoek, M.F.: Chord: A scalable peer-to-peer lookup service for Internet applications. In: Proc. of the 1995 Symp. on Communications Architectures & Protocols, Cambridge, MA, ACM SIGCOMM (August 1995)
Rowstron, A., Druschel, P.: Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: Guerraoui, R. (ed.) Middleware 2001. LNCS, vol. 2218, Springer, Heidelberg (2001)
Haridasan, M., van Renesse, R.: Defense against intrusion in a live streaming multicast system. In: 6th IEEE International Conference on Peer-to-Peer Computing (P2P 2006), Cambridge, UK (September 2006)
Johansen, H., Johansen, D., van Renesse, R.: Firepatch: Secure and time-critical dissemination of software patches. In: IFIP International Information Security Conference (IFIPSEC 2007), Sandton, South-Africa (May 2007)
Douceur, J.: The Sybil attack. In: Proc. of the 1st Int. Workshop on Peer-to-Peer Systems, Cambridge, MA (March 2002)
Malkhi, D., Mansour, Y., Reiter, M.K.: On diffusing updates in a Byzantine environment. In: Symposium on Reliable Distributed Systems, Lausanne, Switzerland, pp. 134–143 (October 1999)
Badishi, G., Keidar, I., Sasson, A.: Exposing and eliminating vulnerabilities to Denial of Service attacks in secure gossip-based multicast. In: Proc. of the International Conference on Dependable Systems and Networks (DSN), pp. 201–210 (2004)
Jenkins, K., Demers, A.: Logarithmic harary graphs. In: Proceedings of the 21st International Conference on Distributed Computing Systems, ICDCSW (2001)
Kermarrec, A.-M., Massoulié, L., Ganesh, A.J.: Probabilistic reliable dissemination in large-scale systems. IEEE Transactions on Parallel and Distributed Systems, 14(3), (March 2003)
Erdös, P., Rényi, A.: On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Közl 5(17), 17–61 (1960)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dolev, D., Hoch, E.N., van Renesse, R. (2007). Self-stabilizing and Byzantine-Tolerant Overlay Network. In: Tovar, E., Tsigas, P., Fouchal, H. (eds) Principles of Distributed Systems. OPODIS 2007. Lecture Notes in Computer Science, vol 4878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77096-1_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-77096-1_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77095-4
Online ISBN: 978-3-540-77096-1
eBook Packages: Computer ScienceComputer Science (R0)