Phys. Rev. E 73, 066115 (2006) [20 pages]
Synchronization landscapes in small-world-connected computer networks
Abstract
References (106)
Citing Articles
H. Guclu and G. KornissDepartment of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8th Street, Troy, New York, 12180-3590 USAM. A. NovotnyDepartment of Physics and Astronomy, and Center for Computational Sciences, Mississippi State University, P. O. Box 5167, Mississippi State, Mississippi, 39762-5167 USAZ. ToroczkaiCenter for Nonlinear Studies, Theoretical Division, Los Alamos National Laboratory, MS-B258, Los Alamos, New Mexico 87545 USAZ. RáczInstitute for Theoretical Physics–HAS, Eötvös University, Pázmány sétány 1/a, 1117 Budapest, Hungary
Received 26 December 2005; published 13 June 2006
Motivated by a synchronization problem in distributed computing we studied a simple growth model on regular and small-world networks, embedded in one and two dimensions. We find that the synchronization landscape (corresponding to the progress of the individual processors) exhibits Kardar-Parisi-Zhang-like kinetic roughening on regular networks with short-range communication links. Although the processors, on average, progress at a nonzero rate, their spread (the width of the synchronization landscape) diverges with the number of nodes (desynchronized state) hindering efficient data management. When random communication links are added on top of the one and two-dimensional regular networks (resulting in a small-world network), large fluctuations in the synchronization landscape are suppressed and the width approaches a finite value in the large system-size limit (synchronized state). In the resulting synchronization scheme, the processors make close-to-uniform progress with a nonzero rate without global intervention. We obtain our results by "simulating the simulations," based on the exact algorithmic rules, supported by coarse-grained arguments.
©2006 The American Physical Society
REFERENCES (106)
For access to fully linked references, you need to log in.
For access to fully linked references, you need to Log in.
- R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
- B. J. Kim, H. Hong, P. Holme, G. S. Jeon, P. Minnhagen, and M. Y. Choi, Phys. Rev. E 64, 056135 (2001).
- H. Hong, M. Y. Choi, and B. J. Kim, Phys. Rev. E 65, 047104 (2002).
- B. Kozma, M. B. Hastings, and G. Korniss, Phys. Rev. Lett. 92, 108701 (2004).
- B. Kozma, M. B. Hastings, and G. Korniss, Phys. Rev. Lett. 95, 018701 (2005).
- S. Jespersen, I. M. Sokolov, and A. Blumen, Phys. Rev. E 62, 4405 (2002).
- S. Jespersen and A. Blumen, Phys. Rev. E 62, 6270 (2002).
- E. Almaas, R. V. Kulkarni, and D. Stroud, Phys. Rev. Lett. 88, 098101 (2002).
- K. Wiesenfeld, P. Colet, and S. H. Strogatz, Phys. Rev. Lett. 76, 404 (1996).
- M. Barahona and L. M. Pecora, Phys. Rev. Lett. 89, 054101 (2002).
- H. Hong, B. J. Kim, and M. Y. Choi, Phys. Rev. E 66, 018101 (2002).
- G. Korniss, Z. Toroczkai, M. A. Novotny, and P. A. Rikvold, Phys. Rev. Lett. 84, 1351 (2000).
- R. J. Glauber, J. Math. Phys. 4, 294 (1963).
- G. Korniss, C. J. White, P. A. Rikvold, and M. A. Novotny, Phys. Rev. E 63, 016120 (2001).
- Y. Shim and J. G. Amar, Phys. Rev. B 71, 115436 (2005).
- Y. Shim and J. G. Amar, Phys. Rev. B 71, 125432 (2005).
- L. N. Shchur and M. A. Novotny, Phys. Rev. E 70, 026703 (2004).
- P. Bak, C. Tang, and K. Wiesenfeld, Phys. Rev. Lett. 59, 381 (1987).
- P. Bak, C. Tang, and K. Wiesenfeld, Phys. Rev. A 38, 364 (1988).
- X. Z. Cheng, M. B. A. Jalil, H. K. Lee, and Y. Okabe, Phys. Rev. Lett. 96, 067208 (2006).
- Z. Toroczkai, G. Korniss, S. Das Sarma, and R. K. P. Zia, Phys. Rev. E 62, 276 (2000).
- A. Kolakowska, M. A. Novotny, and G. Korniss, Phys. Rev. E 67, 046703 (2003).
- A. Kolakowska, M. A. Novotny, and P. A. Rikvold, Phys. Rev. E 68, 046705 (2003).
- A. Kolakowska and M. A. Novotny, Phys. Rev. B 69, 075407 (2004).
- M. Kardar, G. Parisi, and Y.-C. Zhang, Phys. Rev. Lett. 56, 889 (1986).
- G. Foltin, K. Oerding, Z. Rácz, R. L. Workman, and R. K. P. Zia, Phys. Rev. E 50, R639 (1994).
- M. Plischke, Z. Rácz, and R. K. P. Zia, Phys. Rev. E 50, 3589 (1994).
- Z. Rácz and M. Plischke, Phys. Rev. E 50, 3530 (1994).
- T. Antal and Z. Rácz, Phys. Rev. E 54, 2256 (1996).
- T. Antal, M. Droz, G. Györgyi, and Z. Rácz, Phys. Rev. Lett. 87, 240601 (2001).
- T. Antal, M. Droz, G. Györgyi, and Z. Rácz, Phys. Rev. E 65, 046140 (2002).
- E. Marinari, A. Pagnani, G. Parisi, and Z. Rácz, Phys. Rev. E 65, 026136 (2002).
- J. M. Kim and J. M. Kosterlitz, Phys. Rev. Lett. 62, 2289 (1989).
- A. Kolakowska, M. A. Novotny, and P. S. Verma, Phys. Rev. E 70, 051602 (2004).
- A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes, Phys. Rev. E 67, 026123 (2003).
- M. B. Hastings, Phys. Rev. Lett. 91, 098701 (2003).
- C. P. Herrero, Phys. Rev. E 65, 066110 (2002).
- A. Pekalski, Phys. Rev. E 64, 057104 (2001).
- D. Jeong, H. Hong, B. J. Kim, and M. Y. Choi, Phys. Rev. E 68, 027101 (2003).
- J. Viana Lopes, Y. G. Pogorelov, J. M. B. Lopes dos Santos, and R. Toral, Phys. Rev. E 70, 026112 (2004).
- M. Droz, Z. Rácz, and P. Tartaglia, Phys. Rev. A 41, 6621 (1990).
- B. Bergersen and Z. Rácz, Phys. Rev. Lett. 67, 3047 (1991).
CITING ARTICLES
For access to citing articles, you need to log in.For access to citing articles, you need to Log in.
|
A new free weekly publication from APS
|
You are not logged in to this journal. Log in
| Subscription Information
View Cart
Download Citation
MyScitation
Print View