A randomized algorithm for the joining protocol in dynamic distributed networks. (English) Zbl 1160.68002
Summary: We describe a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The aim of the algorithm is to maintain connectivity, low diameter and constant vertex degree. On joining each vertex donates a constant number of tokens to the network. These tokens contain the address of the donor vertex. The tokens make independent random walks in the network. A token can be used by any vertex it is visiting to establish a connection to the donor vertex. This allows joining vertices to be allocated a random set of neighbours although the overall vertex membership of the network is unknown. The network we obtain in this way is robust under adversarial deletion of vertices and edges and actively reconnects itself.
One model we consider is a network constructed in this fashion, in which vertices join but never leave. If \(t\) is the size of the network, then the diameter of the network is \(O(\log t)\) for all \(t\), with high probability. As an example of the robustness of this model, suppose an adversary deletes edges from the network leaving components of size at least \(t^{1/2+\delta}\). With high probability the network reconnects itself by replacing lost edges using tokens from the token pool.
One model we consider is a network constructed in this fashion, in which vertices join but never leave. If \(t\) is the size of the network, then the diameter of the network is \(O(\log t)\) for all \(t\), with high probability. As an example of the robustness of this model, suppose an adversary deletes edges from the network leaving components of size at least \(t^{1/2+\delta}\). With high probability the network reconnects itself by replacing lost edges using tokens from the token pool.
Keywords:
randomized algorithm; dynamic network; joining protocol; random graph process; overlay network; random walks; peer to peer networks; self repairing networksSoftware:
ChordReferences:
| [1] | Bollobás, B., Random Graphs (2001), Cambridge University Press · Zbl 0997.05049 |
| [2] | V. Bourassa, F.B. Holt, SWAN: Small-world Wide Area Networks, in: Proc. SSGRR-2003s, International Conference on Advances in Infrastructure for Electronic Business, Education, Science, Medicine, and Mobile Technologies on the Internet, 2003; V. Bourassa, F.B. Holt, SWAN: Small-world Wide Area Networks, in: Proc. SSGRR-2003s, International Conference on Advances in Infrastructure for Electronic Business, Education, Science, Medicine, and Mobile Technologies on the Internet, 2003 |
| [3] | Chvátal, V., The tail of the hypergeometric distribution, Discrete Mathematics, 25, 285-287 (1979) · Zbl 0396.60016 |
| [4] | Cooper, C.; Dyer, M.; Greenhill, C., Sampling regular graphs and a peer-to-peer network, (Proceedings of the sixteenth annual ACM-SIAM Symposium on Discrete Algorithms, SODA’05 (2005), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA), 980-988 · Zbl 1297.05214 |
| [5] | eDonkey2000, http://www.edonkey2000.com/documentation/onvsed2k.html; eDonkey2000, http://www.edonkey2000.com/documentation/onvsed2k.html |
| [6] | A. Fiat, J. Saia, Censorship resistant peer-to-peer content addressable networks, in: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2002, pp. 94-103; A. Fiat, J. Saia, Censorship resistant peer-to-peer content addressable networks, in: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2002, pp. 94-103 · Zbl 1093.68539 |
| [7] | C. Gkantsidis, M. Mihail, A. Saberi, Random walks in peer-to-peer networks, in: Proc. 22-nd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, March 2004; C. Gkantsidis, M. Mihail, A. Saberi, Random walks in peer-to-peer networks, in: Proc. 22-nd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, March 2004 |
| [8] | Gnutella, http://gnutella.wego.com; Gnutella, http://gnutella.wego.com · Zbl 1020.68927 |
| [9] | Hoeffding, W., Probability inequalities for sums of bounded random variables, Journal American Statistical Association, 58, 13-30 (1963) · Zbl 0127.10602 |
| [10] | Kazaa, http://www.kazaa.com; Kazaa, http://www.kazaa.com |
| [11] | C. Law, K.-Y. Siu, Distributed construction of random expander graphs, in: Proc. 22-nd Annual Joint Conference of the IEEE Computer and Communications Societies, April 2003; C. Law, K.-Y. Siu, Distributed construction of random expander graphs, in: Proc. 22-nd Annual Joint Conference of the IEEE Computer and Communications Societies, April 2003 |
| [12] | Liben-Nowell, D.; Balakrishnan, H.; Karger, D., Analysis of the evolution of peer-to-peer systems, (Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing (2002), ACM Press), 233-242 · Zbl 1292.68014 |
| [13] | Lovász, L., Random walks on graphs: A survey, (Combinatorics, Paul Erdős is 80 (volume 2) (1993)), 1-46 |
| [14] | Malkhi, D.; Naor, M.; Ratajczak, D., Viceroy: A scalable and dynamic emulation of the butterfly, (Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing (2002), ACM Press), 183-192 · Zbl 1292.68015 |
| [15] | McDiarmid, C., On the method of bounded differences, (Simeons, J., Surveys in Combinatorics, 1989 (1989), Cambridge University Press) · Zbl 0712.05012 |
| [16] | Napster, http://www.napster.com; Napster, http://www.napster.com |
| [17] | Pandurangan, G.; Raghavan, P.; Upfal, E., Building low-diameter peer-to-peer networks, IEEE Journal on Selected Areas in Communications, 21, 6, 995-1002 (2003) |
| [18] | M. Ripeanu, Peer-to-peer architecture case study: Gnutella network, Technical report, University of Chicago Technical Report TR-2001-26; M. Ripeanu, Peer-to-peer architecture case study: Gnutella network, Technical report, University of Chicago Technical Report TR-2001-26 · Zbl 1014.68937 |
| [19] | M.T. Schlosser, M. Sintek, S. Decker, W. Nejdl, Hypercup — hypercubes, ontologies, and efficient search on peer-to-peer networks, in: Agents and Peer-to-Peer Computing, First International Workshop, AP2PC 2002, July 2002, pp. 112-124; M.T. Schlosser, M. Sintek, S. Decker, W. Nejdl, Hypercup — hypercubes, ontologies, and efficient search on peer-to-peer networks, in: Agents and Peer-to-Peer Computing, First International Workshop, AP2PC 2002, July 2002, pp. 112-124 · Zbl 1023.68834 |
| [20] | M.T. Schlosser, M. Sintek, S. Decker, W. Nejdl, A scalable and ontology-based p2p infrastructure for semantic web services, in: 2nd International Conference on Peer-to-Peer Computing, P2P 2002, September 2002, pp. 104-111; M.T. Schlosser, M. Sintek, S. Decker, W. Nejdl, A scalable and ontology-based p2p infrastructure for semantic web services, in: 2nd International Conference on Peer-to-Peer Computing, P2P 2002, September 2002, pp. 104-111 |
| [21] | Sinclair, A., Improved bounds for mixing rates of Markov chains and multicommodity flow, Combinatorics, Probability and Computing, 1, 351-370 (1992) · Zbl 0801.90039 |
| [22] | I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, Chord: A scalable peer-to-peer lookup service for Internet applications, in: Proc. 2001 ACM SIGCOMM Conference, 2001, pp. 149-160; I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, Chord: A scalable peer-to-peer lookup service for Internet applications, in: Proc. 2001 ACM SIGCOMM Conference, 2001, pp. 149-160 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
