Order optimal information spreading using algebraic gossip. (English) Zbl 1321.68016
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, PODC ’11, San Jose, CA, USA, June 06–08, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0719-2). 363-372 (2011).
MSC:
| 68M10 | Network design and communication in computer systems |
| 68M12 | Network protocols |
| 68M14 | Distributed systems |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | S. Angelopoulos, B. Doerr, A. Huber, and K. Panagiotou. Tight bounds for quasirandom rumor spreading. The Electronic Journal of Combinatorics, 16(1):R102,1-R102,19, 2009. · Zbl 1195.68020 |
| [2] | C. Avin, M. Borokhovich, K. Censor-Hillel, and Z. Lotker. Order optimal information spreading using algebraic gossip. CoRR, abs/1101.4372, 2011. |
| [3] | M. Borokhovich, C. Avin, and Z. Lotker. Tight bounds for algebraic gossip on graphs. In 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), pages 1758 –1762, jun. 2010. |
| [4] | S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508-2530, June 2006. 10.1109/TIT.2006.874516 · Zbl 1283.94005 |
| [5] | S. P. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms: design, analysis and applications. In IEEE International Conference on Computer Communications (INFOCOM), pages 1653-1664, 2005. |
| [6] | K. Censor-Hillel and H. Shachnai. Fast information spreading in graphs with large weak conductance. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 440-448, 2011. · Zbl 1376.68157 |
| [7] | A. Chaintreau, P. Fraigniaud, and E. Lebhar. Opportunistic spatial gossip over mobile social networks. In WOSP ’08: Proceedings of the first workshop on Online social networks, pages 73-78, New York, NY, USA, 2008. ACM. 10.1145/1397735.1397752 |
| [8] | H. Chen and D. Yao. Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization, volume 46 of Applications of Mathematics. Springer-Verlag, New York, first edition, 2001. · Zbl 0992.60003 |
| [9] | S. Deb, M. Médard, and C. Choute. Algebraic gossip: a network coding approach to optimal multiple rumor mongering. IEEE Transactions on Information Theory, 52(6):2486-2507, 2006. 10.1109/TIT.2006.874532 · Zbl 1293.94009 |
| [10] | A. J. Demers, D. H. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. E. Sturgis, D. C. Swinehart, and D. B. Terry. Epidemic algorithms for replicated database maintenance. Operating Systems Review, 22(1):8-32, 1988. 10.1145/43921.43922 |
| [11] | B. Doerr, T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’08, pages 773-781, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics. · Zbl 1192.90024 |
| [12] | C. Georgiou, S. Gilbert, R. Guerraoui, and D. R. Kowalski. On the complexity of asynchronous gossip. In PODC ’08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, pages 135-144, New York, NY, USA, 2008. ACM. 10.1145/1400751.1400771 · Zbl 1301.68160 |
| [13] | B. Haeupler. Analyzing Network Coding Gossip Made Easy. To appear in the ph43rd ACM Symposium on Theory of Computing (STOC), 2011. 10.1145/1993636.1993676 · Zbl 1288.68021 |
| [14] | T. Ho, R. Koetter, M. Medard, D. R. Karger, and M. Effros. The benefits of coding over routing in a randomized setting. In IEEE International Symposium on Information Theory (ISIT), page 442, 2003. |
| [15] | R. M. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking. Randomized rumor spreading. In Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 565-574, 2000. |
| [16] | D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 482-491, 2003. |
| [17] | D. Kempe, J. Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In KDD ’03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, New York, NY, USA, 2003. ACM. 10.1145/956750.956769 |
| [18] | S.-Y. R. Li, R. W. Yeung, and N. Cai. Linear network coding. IEEE Transactions on Information Theory, 49(2):371-381, 2003. 10.1109/TIT.2002.807285 · Zbl 1063.94004 |
| [19] | M. Médard and R. Koetter. Beyond routing: An algebraic approach to network coding. In IEEE International Conference on Computer Communications (INFOCOM), pages 122-130, 2002. |
| [20] | D. Mosk-Aoyama and D. Shah. Computing separable functions via gossip. In PODC ’06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 113-122, New York, NY, USA, 2006. ACM. 10.1145/1146381.1146401 · Zbl 1314.68048 |
| [21] | D. Mosk-Aoyama and D. Shah. Information dissemination via network coding. In IEEE International Symposium on Information Theory Proceedings (ISIT), pages 1748-1752, 2006. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
