Partial information spreading with application to distributed maximum coverage

DOI10.1145/1835698.1835739MaRDI QIDQ5176196zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, Hadas Shachnai

Publication date 2 March 2015

Published in Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsdistributed computingmaximum coveragepartial information spreadingrandomized algorithmsweak conductance

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Fast information spreading in graphs with large weak conductance
• Fast information spreading in graphs with large weak conductance
• Rumour spreading and graph conductance
• Rumor spreading and conductance
• Almost tight bounds for rumour spreading with conductance

Cites work

• Elastic Transactions
• Software transactional memory
• Toward a theory of transactional contention managers

Cited in

(10)

• Xheal: a localized self-healing algorithm using expanders
• Faster rumor spreading with multiple calls
• Distributed agreement in dynamic peer-to-peer networks
• The worst case behavior of randomized gossip protocols
• Fast information spreading in graphs with large weak conductance
• Fast information spreading in graphs with large weak conductance
• Towards robust and efficient computation in dynamic peer-to-peer networks
• Ultra-fast rumor spreading in social networks
• Extremal properties of evolving networks: local dependence and heavy tails
• Leader nodes in communities for information spreading

Describes a project that uses

Uses Software

• CCSTM

This page was built for publication: Partial information spreading with application to distributed maximum coverage

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