2025/07/23 by Marco Pulimeno, Pulimeno, Marco, Italo Epicoco +3
Computer Science · #Peer-to-Peer Network Technologies
paper · pdf · doi:10.48550/arxiv.2507.17458
In this paper we present DUDDSketch, a distributed version of the UDDSketch algorithm for accurate tracking of quantiles. The algorithm is a fully decentralized, gossip-based distributed protocol working in the context of unstructured P2P networks. We discuss the algorithm's design and formally prove its correctness. We also show, through extensive experimental results, that the algorithm converges to the results provided by the sequential algorithm, which is a fundamental and highly desirable property.