Practical privacy preserving size approximation in distributed systems
Marek Klonowski, Piotr Syga · 2016
Size approximation is used as a subroutine in many more complex algorithms in order to establish their parameters, hence it is crucial to be able to perform fast and (reasonably) accurate algorithms. In our paper we show that, despite the fact that some of the existing algorithms are asymptotically optimal, for most common in practical settings networks of a moderate size (up to 10000 nodes), they may require more time than simpler protocols with asymptotically inferior performance. We present a simple approach to size approximation that works faster than some popular asymptotically optimal algorithms in scenarios concerning realistic sized networks. We provide experimental results for the estimation. Moreover, we show that the simple algorithm can be easier protected against a passive adversary aiming at learning the number of stations working in the system.