Bounds for the Security of the Vivaldi Network Coordinate System

Network coordinate systems have gained much attention as they allow for an elegant estimation of distances between nodes in distributed systems. Their most prominent representative is Vivaldi, which is using a mass-spring-damper system to embed peers into a two-dimensional Euclidean coordinate space with an additional height coordinate. In unimpaired overlay networks this simple method leads to a good approximation of pair wise delays. Unfortunately, like most distributed algorithms, Vivaldi is vulnerable to Byzantine failures, leading to possible routing attacks in peer-to-peer systems. Hence, several attack methods and countermeasures have been proposed. In this article, we analyze bounds for protection of Vivaldi network coordinates and show by theory and simulation how triangle inequality violations can be exploited to create instabilities, despite the proposed countermeasures.