Report on "Vivaldi: A Decentralized Network Coordinate System"

In the paper an algorithm that estimates RTT between computers in the Internet via synthetic coordinate system is described. The prediction of RTT is important because it used in many different network applications, for example, in peer-to-peer systems. This algorithm can estimate RTT without contacting computers explicitly that reduces the overhead associated with probing RTT.  The main idea of the algorithm is of introduction a decentralized coordinates which are drawn from a two-dimensional Euclidean model and an additional dimension, height. So the mechanism uses two-dimensional model space plus height, and height is associated with latency within a node, i.e. queuing delay, low bandwidth, or  the sheer length of the link. Computers are considered to be some "masses" that are connected by "springs". Through simulation of the forces in this spring system the computers coordinates their "movement", and, consequently, the length of the "springs" between them, and eventually a state corresponding to the minimum of the mass-spring system potential energy is reached, where the distance between two computers, i.e. the length of the "springs", on the synthetic coordinates reflects the RTT in the real world. The coordinates of computers are adjusted based on a time-step variable, so as a computer becomes more sure of its coordinates, the time-step decreases, and the computer adjusts its coordinates in smaller amount..

People defined the contribution of the paper as the development of a decentralized, adaptive, low-overhead synthetic coordinate system that calculates coordinates of computers which can estimate RTT between nodes without any sort of central servers, any explicit knowledge of the network topology, need to contact to all computers, or any modifications to the Internet infrastructure. So the algorithm that uses the coordinate system gives an opportunity to figure out the closest computer for the given one. The other good idea is of using a time-step variable as the base of coordinates adjustment mechanism, which provides quick convergence, low oscillation, and  makes sure the avoidance of influence of high-error node errors on the accuracy of the algorithm.

The paper is written and organized very well, it provides a good exploration of using different coordinate systems, the topic is clearly defined. While evaluating the algorithm using a simulated network, the median relative error in RTT prediction  is 11%, and people consider this result as a very good one. Using two datasets consisting of 192 and 1740 hosts, is a good way to evaluate the algorithm. Some people appreciate well organized references to related work. However, there are some unclear things in the paper. The algorithm uses coordinates of "nearby" nodes and "distant" nodes for estimating the coordinates of any particular node, but it doesn't explicit, which node is supposed to be a "nearby" one, and which node supposed to be a "distant" one. So there isn't any definition of these two types of nodes, whereas there is some experimental issue that an optimal ratio between "nearby" and "distant" nodes should be equal to one-to-one. Some people think that it is not immediately obvious what some of the graphs were trying to show. It is not explicit how many samples should each node keep in order to have good performance, whether there is an optimum, and how one can figure out that optimum.

So, at the end of the discussion, people have a good opinion about the paper, and most of them ranked the paper as a top-third.