Computing separable functions via gossip

DOI10.1145/1146381.1146401MaRDI QIDQ5177272zbMATH OpenOpenAlexFDO

Authors Damon Mosk-Aoyama, Devavrat Shah

Publication date 10 March 2015

Published in Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1146381.1146401

zbMATH Keywords

randomized algorithmsdata aggregationgossip

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Stochastic network models in operations research (90B15) Distributed systems (68M14) Network protocols (68M12)

Recommendations

• Fast Distributed Algorithms for Computing Separable Functions
• Almost-optimal gossip-based aggregate computation
• Gossiping and broadcasting versus computing functions in networks
• Simple, fast and deterministic gossip and rumor spreading
• Fast linear iterations for distributed averaging

Cited in

(23)

• Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions
• In-network estimation of frequency moments
• Leader nodes in communities for information spreading
• A stochastic process on a network with connections to Laplacian systems of equations
• Mathematical Foundations of Computer Science 2003
• Rumor spreading with no dependence on conductance
• Multi-client functional encryption for separable functions
• Extremal properties of evolving networks: local dependence and heavy tails
• Discovery through gossip
• Towards worst-case churn resistant peer-to-peer systems
• LiMoSense: live monitoring in dynamic sensor networks
• Partially ordered knowledge sharing and fractionated systems in the context of other models for distributed computing
• Distributed Averaging in Opinion Dynamics
• Identifying frequent items in a network using gossip
• Braid Chain Radio Communication
• Towards a queueing-based framework for in-network function computation
• The cost of fault tolerance in multi-party communication complexity
• Order optimal information spreading using algebraic gossip
• Lower bounds for in-network computation of arbitrary functions
• The firing squad problem revisited
• Peer counting and sampling in overlay networks based on random walks
• Pathogen spread on coupled networks: effect of host and network properties on transmission thresholds
• Fast Distributed Algorithms for Computing Separable Functions

This page was built for publication: Computing separable functions via gossip

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