Rachid Guerraoui
ABSTRACT
This paper shows for the first time that distributed computing can be both reliable and efficient in an environment that is both highly dynamic and hostile. More specifically, we show how to maintain clusters of size O(log N), each containing more than two thirds of honest nodes with high probability, within a system whose size can vary polynomially with respect to its initial size. Furthermore, the communication cost induced by each node arrival or departure is polylogarithmic with respect to N, the maximal size of the system. Our clustering can be achieved despite the presence of a Byzantine adversary controlling a fraction τ ≤ 1⁄3-ε of the nodes, for some fixed constant ε > 0, independent of N. So far, such a clustering could only be performed for systems whose size can vary constantly and it was not clear whether that was at all possible for polynomial variances.
- D. Aldous and J. Fill. Reversible markov chains and random walks on graphs. http://statwww.berkeley.edu/users/aldous/RWG/book.html.Google Scholar
- J. Aspnes and U. Wieder. The expansion and mixing time of skip graphs with applications. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'05), pages 126--134, 2005. Google ScholarDigital Library
- J. Aspnes and Y. Yin. Distributed algorithms for maintaining dynamic expander graphs. Citeseer, 2008.Google Scholar
- J. Augustine, G. Pandurangan, P. Robinson, and E. Upfal. Towards robust and efficient computation in dynamic peer-to-peer networks. Arxiv preprint, arXiv:1108.0809, 2011.Google Scholar
- B. Awerbuch and C. Scheideler. Group spreading: A protocol for provably secure distributed name service. Automata, Languages and Programming, pages 187--210, 2004.Google ScholarCross Ref
- B. Awerbuch and C. Scheideler. Towards scalable and robust overlay networks. In Proceedings of the International Workshop on Peer-To-Peer Systems (IPTPS'07), 2007.Google Scholar
- B. Awerbuch and C. Scheideler. Towards a scalable and robust DHT. Theory of Computing Systems, 45(2):234--260, 2009. Google ScholarDigital Library
- R. Baldoni, S. Bonomi, and A. S. Nezhad. An algorithm for implementing bft registers in distributed systems with bounded churn. In SSS, pages 32--46, 2011. Google ScholarDigital Library
- R. Baldoni, S. Bonomi, and M. Raynal. An implementation in a churn prone environment. In SIROCCO, pages 15--29, 2009. Google ScholarDigital Library
- H. Baumann, P. Crescenzi, and P. Fraigniaud. Parsimonious flooding in dynamic graphs. In Proceedings of the 28th symposium on Principles of distributed computing (PODC'09), 2009. Google ScholarDigital Library
- Z. Galil and M. Yung. Partitioned encryption and achieving simultaneity by partitioning. Information Processing Letters, 26(2):81--88, 1987. Google ScholarDigital Library
- S. Gambs, R. Guerraoui, H. Harkous, F. Huc, and A.-M. Kermarrec. Scalable and secure polling in dynamic distributed networks. SRDS, 2012. Google ScholarDigital Library
- J. Garay, J. Katz, R. Kumaresan, and H. Zhou. Adaptively secure broadcast, revisited. In 30th annual Symposium on Principles of Distributed Computing (PODC'11), 2011. Google ScholarDigital Library
- A. Giurgiu, R. Guerraoui, K. Huguenin, and A. Kermarrec. Computing in social networks. Stabilization, Safety, and Security of Distributed Systems, pages 332--346, 2010. Google ScholarDigital Library
- C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'2004), volume 1, 2004.Google ScholarCross Ref
- R. Guerraoui, F. Huc, and A.-M. Kermarrec. Highly dynamic distributed computing with byzantine failures. Arxiv preprint, arXiv:1202.3084, 2013. Google ScholarDigital Library
- M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed. Probabilistic Methods for Algorithmic Discrete Mathematics. Springer Verlag, Berlin, 1998.Google ScholarCross Ref
- V. King, S. Lonargan, J. Saia, and A. Trehan. Load balanced scalable byzantine agreement through quorum building, with full information. Distributed Computing and Networking, pages 203--214, 2011. Google ScholarCross Ref
- V. King and J. Saia. Scalable Byzantine Computation. ACM SIGACT News, 41(3), 2010. Google ScholarDigital Library
- M. Krebs and A. Shaheen. Expander Families and Cayley Graphs: A Beginner's Guide. Oxford University Press, USA, 2011.Google Scholar
- F. Kuhn, N. Lynch, and R. Oshman. Distributed computation in dynamic networks. In Proceedings of the 42nd symposium on Theory of computing (STOC'10), pages 513--522, 2010. Google ScholarDigital Library
- F. Kuhn, Y. Moses, and R. Oshman. Coordinated consensus in dynamic networks. In Proceedings of the 30th annual symposium on Principles of distributed computing (PODC'11), pages 1--10, 2011. Google ScholarDigital Library
- F. Kuhn, S. Schmid, and R. Wattenhofer. Towards worst-case churn resistant peer-to-peer systems. Distributed Computing, 22(4):249--267, 2010.Google ScholarDigital Library
- K. L., E. Liberty, and O. Somekh. Estimating sizes of social networks via biased sampling. In Proceedings of the 20th international conference on World wide web, pages 597--606. ACM, 2011. Google ScholarDigital Library
- L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems (TOPLAS'82), 4(3):382--401, July 1982. Google ScholarDigital Library
- C. Law and K. Siu. Distributed construction of random expander graphs. In Proceedings of 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'2003), pages 2133--2143, 2003.Google Scholar
- X. Li, J. Misra, and C. Plaxton. Active and concurrent topology maintenance. Distributed Computing, pages 320--334, 2004.Google ScholarCross Ref
- G. Pandurangan and A. Trehan. Xheal: localized self-healing using expanders. In Proceedings of the 30th annual symposium on Principles of distributed computing (PODC'11), pages 301--310, 2011. Google ScholarDigital Library
- S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Conference on Applications, technologies, architectures, and protocols for computer communications, pages 161--172, 2001. Google ScholarDigital Library
- A. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Proceedings of Middleware'01, pages 329--350, 2001. Google ScholarDigital Library
- C. Scheideler. How to spread adversarial nodes? Rotate! Proceedings of the 37th annual symposium on Theory of computing (STOC'05), page 704, 2005. Google ScholarDigital Library
- C. Scheideler and S. Schmid. A distributed and oblivious heap. Automata, Languages and Programming, pages 571--582, 2009. Google ScholarDigital Library
- B. Zhao, L. Huang, J. Stribling, S. Rhea, A. Joseph, and J. Kubiatowicz. Tapestry: A resilient global-scale overlay for service deployment. IEEE Journal on Selected Areas in Communications, 22(1):41--53, 2004. Google ScholarDigital Library
Index Terms
- Highly dynamic distributed computing with byzantine failures
Recommendations
Scalable and Secure Polling in Dynamic Distributed Networks
SRDS '12: Proceedings of the 2012 IEEE 31st Symposium on Reliable Distributed SystemsWe consider the problem of securely conducting a poll in synchronous dynamic networks equipped with a Public Key Infrastructure (PKI). Whereas previous distributed solutions had a communication cost of $O(n^2)$ in an $n$ nodes system, we present SPP (...
Containing Byzantine Failures with Control Zones
We consider the problem of reliably broadcasting messages in a network where some nodes are likely to fail. We consider the most general failure model: the Byzantine model, where the failing nodes have an arbitrary behavior, and may actively try to ...
Asynchronous Byzantine Agreement with optimal resilience
We present an efficient, optimally-resilient Asynchronous Byzantine Agreement (ABA) protocol involving $$n = 3t+1$$n=3t+1 parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, capable of corrupting ...
Comments