Synchronization in Complex Computing Networks

In this book we study synchronization phenomena in natural and artificial coupled multi-component systems, applicable to the scalability of parallel discrete-event simulation for systems with asynchronous dynamics. We also study the role of various complex communication topologies as synchronization networks. We analyze the properties of the virtual time horizon or synchronization landscape (corresponding to the progress of the processing elements) of these networks by using the framework of non- equilibrium surface growth. When the communication topology mimics that of the short-range interacting underlying system, the virtual time horizon exhibits Kardar-Parisi-Zhang kinetic roughening. Although the virtual times, on average, progress at a nonzero rate, their statistical spread diverges with the number of processing elements, hindering efficient data collection. We show that when the synchronization topology is extended to include quenched random communication links between the processing elements, as in small-world and scale-free networks, they make a scalable and close-to-uniform progress with a nonzero rate, without global synchronization.