Veracity Radius - Capturing the Locality of Distributed Computations.

Authors: Yitzhak Birk, Idit Keidar, Liran Liss, Assaf Schuster, and Ran Wolff.

In the 25th ACM Symposium on Principles of Distributed Computing (PODC '06), pages 102-111, July 2006.

Full version Technical Report CCIT 578, Technion Department of Electrical Engineering, February 2006.

Abstract:

This paper focuses on local computations of distributed aggregation problems on fixed graphs. We define a new metric on problem instances, Veracity Radius (VR), which captures the inherent possibility to compute them locally. We prove that VR yields a tight lower bound on output-stabilization time, i.e., the time until all nodes fix their outputs, as well as a lower bound on quiescence time. We present an efficient aggregation algorithm, I-LEAG, which reaches both output stabilization and quiescence within a time that is proportional to the VR of the problem instance, and is also efficient in terms of per-node communication and memory. We empirically show that the VR metric also effectively captures the performance of previously suggested efficient aggregation protocols, and that I-LEAG significantly outperforms these protocols in several respects.

Download:

Preprint of PODC paper: pdf, pdf.gz.

Technical Report CCIT 578, Technion Department of Electrical Engineering, July 2006: pdf.