Loading...
Please wait, while we are loading the content...
Similar Documents
ABSTRACT Veracity Radius- Capturing the Locality of Distributed Computations ∗
| Content Provider | CiteSeerX |
|---|---|
| Author | Birk, Yitzhak Schuster, Assaf Wolff, Ran |
| 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. Categories and Subject Descriptors C.4 [Performance of Systems]: [Performance attributes]; |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Abstract Veracity Radius Distributed Computation Problem Instance Quiescence Time Veracity Radius Output Stabilization Output-stabilization Time Per-node Communication Several Respect Subject Descriptor Local Computation Efficient Aggregation Algorithm Fixed Graph Efficient Aggregation Protocol Inherent Possibility Distributed Aggregation Problem |
| Content Type | Text |
| Resource Type | Article |
