Review: Big-Bang Simulation

Yuval Shavitt and Tomer Tankel, "Big-Bang Simulation for Embedding Network Distances in Euclidean Space", IEEE Infocom, 2003.

A rather complex paper on mapping the Internet nodes on to a Cartesian space. In this work all the nodes are treated as molecules floating in an imaginary Euclidean space acting upon repulsive/attractive forces created by one on another. As all the nodes' initial position is at the origin and then they move away under these forces, the algorithm is called big-bang simulation (BBS). The fundamental principle of the BBS algorithm is to minimize the energy in the system; the energy can be both potential energy due to the inter-molecular forces and kinetic energy due to the movement of the molecules under these forces.

The paper elaborately explain the energy equations used in the algorithm. However, no mathematical proof is given to ensure a convergence. Each iteration involves four phases each applying the energy equations to minimize the total energy or tuning the coordinates so that tension is distributed evenly. Communication complexity is O(I n^2), where I is the number of iteration. Still at each step, message complexity is 4n^2.