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.