Spatial gossip and resource location protocols

DOI10.1145/380752.380796zbMath1323.68015MaRDI QIDQ5175964

Alan Demers, David Kempe, Jon M. Kleinberg

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68M14: Distributed systems

68M12: Network protocols

Related Items

Unnamed Item, Partially Ordered Knowledge Sharing and Fractionated Systems in the Context of other Models for Distributed Computing, Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems, Araneola: a scalable reliable multicast system for dynamic environments, A random walk model for infection on graphs: spread of epidemics \& rumours with mobile agents, Efficient distributed computation of distance sketches in networks, Agent-based randomized broadcasting in large networks, Spatially-decaying aggregation over a network, A probabilistic characterization of a fault-tolerant gossiping algorithm, Analysis of randomized protocols for conflict-free distributed access, Optimal routing in a small-world network, Discovery Through Gossip, Rumor Spreading with No Dependence on Conductance, Sub-linear Universal Spatial Gossip Protocols

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)