Armon Dadgar on Vivaldi: A Decentralized Network Coordinate System

In designing the distributed networking tool Consul, HashiCorp turned to an algorithm for mapping nodes into a simple coordinate system, where distance between coordinates predicts latency. In this talk sponsored by Papers We Love, HashiCorp CTO Armon Dadgar discusses (starting at 28:10) a 2004 paper he loves, “Vivaldi: A Decentralized Network Coordinate System,” by Dabek, Cox, Kaashoek, and Morris. In it, the authors laid out the problem with communications latency and suggested a way to achieve latency prediction that is lightweight, accurate, adaptive to changing topology, and distributed, relying on local knowledge alone.

Recognizing that, because real latencies violate triangle inequality, no simple coordinate system can avoid error, even if measurements were perfect and consistent, the authors modeled error as spring tension. To minimize error, coordinates are adjusted by simulating spring movement.

Dadgar explains how the authors had to incorporate the dimension of height (the fixed time for communication down the stack) to get acceptable predictability of coordinates, and then he discusses Vivaldi’s function in Consul, HashiCorp’s solution for service discovery, monitoring, configuration, and orchestration.