检索结果-内蒙古大学图书馆

ALMOST-OPTIMAL GOSSIP-BASED AGGREGATE COMPUTATION

SIAM JOURNAL ON COMPUTING 2012年第3期41卷 455-483页

作者： Chen, Jen-Yeu Pandurangan, Gopal Natl DongHwa Univ Dept Elect Engn Shoufeng 97401 Hualien Taiwan Brown Univ Dept Comp Sci Providence RI 02912 USA Nanyang Technol Univ Div Math Sci Singapore 637371 Singapore

Motivated by applications to modern networking technologies, there has been interest in designing efficient gossip-based protocols for computing aggregate functions. While gossip-based protocols provide robustness due to their randomized nature, reducing the message and time complexity of these protocols is also of paramount importance in the context of resource-constrained networks such as sensor and peer-to-peer networks. We present provably time-optimal efficient gossip-based algorithms for aggregate computation with almost optimal message complexity. Given an n-node network, our algorithms guarantee that all the nodes can compute the common aggregates (such as Max, Min, Average, Sum, and Count) of their values in optimal O(log n) time and using O(n log log n) messages. Our result improves on the algorithm of Kempe, Dobra, and Gehrke [Proceedings of the IEEE Annual Symposium on Foundations of Computer Science, 2003, pp. 482-491] that is time-optimal but uses O(n log n) messages, as well as on the algorithm of Kashyap et al. [Proceedings of Symposium on Principles of Database Systems, 2006, pp. 308-317] that uses O(n log log n) messages but is not time-optimal (takes O(log n log log n) time). Furthermore, we show that our algorithms can be used to improve gossip-based aggregate computation in sparse communication networks, such as in peer-to-peer networks. The main technical ingredient of our algorithm is a technique called distributed random ranking (DRR) that can be useful in other applications as well. DRR gives an efficient distributed procedure to partition the network into a forest of (disjoint) trees of small size. Since the size of each tree is small, aggregates within each tree can be efficiently obtained at their respective roots. All the roots then perform a uniform gossip algorithm on their local aggregates to reach a distributed consensus on the global aggregates. Our algorithms are non-address-oblivious. In contrast, we show a lower bound of Omega(n

关键词： gossip-based protocols aggregate computation distributed randomized protocols probabilistic analysis lower bounds

来源：评论

学校读者我要写书评

暂无评论

Optimal Gossip-Based Aggregate Computation 10

Optimal Gossip-Based Aggregate Computation

引用

22nd ACM Symposium on Parallelism in Algorithms and Architectures

作者： Chen, Jen-Yeu Pandurangan, Gopal Natl Dong Hwa Univ Dept Elect Engn Shoufeng 97401 Hualien Taiwan

ISBN: (纸本)9781450300797

Motivated by applications to modern networking technologies, there has been interest in designing efficient gossip-based protocols for computing aggregate functions While gossip-based protocols provide robustness due to their randomized nature, reducing the message and time complexity of these protocols is also of paramount importance in the context of resource-constrained networks such as sensor and peer-to-peer networks We present the first provably almost-optimal gossip-based algorithms for aggregate computation that are both time optimal and message-optimal. Given a n-node network, our algorithms guarantee that all the nodes can compute the common aggregates (such as Min, Max, Count. Sum, Average, Rank etc) of their values in optimal O(log n) time and using O(n log log n) messages Our result improves on the algorithm of Kempe et al [II] that is time-optimal, but uses O(n log n) messages as well as on the algorithm of Kashyap et al [10] that uses O(n Jog log n) messages, but is not time-optimal (takes O(log n log log n) time). Furthermore, we show that our algorithms can be used to improve gossip-based aggregate computation in sparse communication networks, such as in peer-to-peer networks The main technical ingredient of our algorithm is a technique called distributed random ranking (DRR) that can be useful in other applications as well DRR gives an efficient distributed procedure to partition the network into a forest of (disjoint) trees of small size. Since the size of each tree is small, aggregates within each tree can be efficiently obtained at their respective roots All the roots then perform a uniform gossip algorithm on their local aggregates to reach a distributed consensus on the global aggregates Our algorithms are non-address oblivious In contrast, we show a lower bound of Omega(n log n) on the message complexity of any address-oblivious algorithm for computing aggregates. This shows that non-address oblivious algorithms are needed to obtain significa

关键词： Gossip-based protocols aggregate computation distributed randomized protocols probabilistic analysis lower bounds

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：