Almost-optimal gossip-based aggregate computation

DOI10.1137/100793104MaRDI QIDQ2910849zbMATH OpenOpenAlexFDO

Authors Jen-Yeu Chen, Gopal Pandurangan

Publication date 12 September 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10220/10895

zbMATH Keywords

address-oblivious algorithmaggregate computationaggregate functionsdistribution random rankinggossip-based protocolmessage complexitynon-address-oblivious algorithmpeer-to-peer networkssparse communication networkstime complexity

Mathematics Subject Classification ID

Internet topics (68M11) Network protocols (68M12) Distributed systems (68M14) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• Optimal gossip algorithms for exact and approximate quantile computations
• Efficient gossip and robust distributed computation
• Efficient gossip and robust distributed computation
• Robust gossip-based aggregation: a practical point of view
• scientific article; zbMATH DE number 2061800
• Gossip consensus algorithms via quantized communication
• A polylogarithmic gossip algorithm for plurality consensus
• Optimal algorithms for broadcast and gossip in the edge-disjoint modes

Cited in

(15)

• Lower bounds for in-network computation of arbitrary functions
• Discovery through gossip
• Aggregation in dynamic networks
• Optimal gossip with direct addressing
• A Generalized Gossip Algorithm on Convex Metric Spaces
• The complexity of data aggregation in directed networks
• The cost of fault tolerance in multi-party communication complexity
• Efficient Dynamic Aggregation
• Computing separable functions via gossip
• Optimal gossip algorithms for exact and approximate quantile computations
• Robust gossip-based aggregation: a practical point of view
• Order optimal information spreading using algebraic gossip
• Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions
• Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions
• Distributed data summarization in well-connected networks

This page was built for publication: Almost-optimal gossip-based aggregate computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910849)