Vivaldi swMATH ID: 39231 Software Authors: Dabek, F., Cox, R., Kaashoek, F., Morris, R. Description: Vivaldi: a decentralized network coordinate system. Large-scale Internet applications can benefit from an ability to predict round-trip times to other hosts without having to contact them first. Explicit measurements are often unattractive because the cost of measurement can outweigh the benefits of exploiting proximity information. Vivaldi is a simple, light-weight algorithm that assigns synthetic coordinates to hosts such that the distance between the coordinates of two hosts accurately predicts the communication latency between the hosts. Vivaldi is fully distributed, requiring no fixed network infrastructure and no distinguished hosts. It is also efficient: a new host can compute good coordinates for itself after collecting latency information from only a few other hosts. Because it requires little com-munication, Vivaldi can piggy-back on the communication patterns of the application using it and scale to a large number of hosts. An evaluation of Vivaldi using a simulated network whose latencies are based on measurements among 1740 Internet hosts shows that a 2-dimensional Euclidean model with height vectors embeds these hosts with low error (the median relative error in round-trip time prediction is 11 percent). Homepage: https://dl.acm.org/doi/10.1145/1030194.1015471 Related Software: Pastry; Chord; plfit; Algorithm 97; Graphs; DIMACS; p2psim; Azureus; clusfind; BATON; Rigel Cited in: 6 Documents all top 5 Cited by 15 Authors 1 Bhatia, Ravinder Singh 1 Das Sarma, Atish 1 Dinitz, Michael H. 1 Du, Hongwei 1 García-López, Pedro 1 Lin, Zhi 1 Liu, Hui 1 Liu, Yaning 1 Pandurangan, Gopal 1 Sànchez-Artigas, Marc 1 Sharma, Bharti 1 Singh, Awadhesh Kumar 1 Sommer, Christian 1 Waqas, Ahmad 1 Ye, Qiang Cited in 5 Serials 1 ACM Computing Surveys 1 Journal of Parallel and Distributed Computing 1 Distributed Computing 1 Proceedings of the National Academy of Sciences, India. Section A. Physical Sciences 1 Mathematical Foundations of Computing Cited in 4 Fields 6 Computer science (68-XX) 2 Combinatorics (05-XX) 1 Operations research, mathematical programming (90-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year