Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
Tóm tắt
Distributed computing models typically assume reliable communication between processors. While such assumptions often hold for engineered networks, e.g., due to underlying error correction protocols, their relevance to biological systems, wherein messages are often distorted before reaching their destination, is quite limited. In this study we take a first step towards reducing this gap by rigorously analyzing a model of communication in large anonymous populations composed of simple agents which interact through short and highly unreliable messages. We focus on the broadcast problem and the majority-consensus problem. Both are fundamental information dissemination problems in distributed computing, in which the goal of agents is to converge to some prescribed desired opinion. We initiate the study of these problems in the presence of communication noise. Our model for communication is extremely weak and follows the push gossip communication paradigm: In each round each agent that wishes to send information delivers a message to a random anonymous agent. This communication is further restricted to contain only one bit (essentially representing an opinion). Lastly, the system is assumed to be so noisy that the bit in each message sent is flipped independently with probability
$$1/2-\epsilon $$
, for some small
$$\epsilon >0$$
. Even in this severely restricted, stochastic and noisy setting we give natural protocols that solve the noisy broadcast and majority-consensus problems efficiently. Our protocols run in
$$O(\log n/\epsilon ^2)$$
rounds and use
$$O(n \log n / \epsilon ^2)$$
messages/bits in total, where n is the number of agents. These bounds are asymptotically optimal and, in fact, are as fast and message efficient as if each agent would have been simultaneously informed directly by an agent that knows the prescribed desired opinion. Our efficient, robust, and simple algorithms suggest balancing between silence and transmission, synchronization, and majority-based decisions as important ingredients towards understanding collective communication schemes in anonymous and noisy populations.
Tài liệu tham khảo
Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Z.: A biological solution to a fundamental distributed computing problem. Science 331(6014), 183–5 (2011)
Afek, Y., Alon, N., Bar-Joseph, Z., Cornejo, A., Haeupler, B., Kuhn, F.: Beeping a maximal independent set. Distrib. Comput. 26(4), 195–208 (2013)
Allen, C., Stevens, C.: An evaluation of causes for unreliability of synaptic transmission. Proc. Natl. Acad. Sci. 91, 10380–10383 (1994)
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235–253 (2006)
Angluin, D., Aspnes, J., Fischer, M.J., Jiang, H.: Self-stabilizing population protocols. TAAS 3(4) (2008)
Angluin, D., Aspnes, J., Eisenstat, D.: A simple population protocol for fast robust approximate majority. Distrib. Comput. 21(2), 87–102 (2008)
Aspnes, J., Ruppert, E.: An introduction to population protocols. Bull. EATCS 93, 98–117 (2007)
Bassler, B.L., Waters, C.M.: Quorum sensing: cell-to-cell communication in bacteria. Annu. Rev. Cell Dev. Biol. 21, 319–346 (2005)
Bar-Yehuda, R., Kutten, S.: Fault tolerant distributed majority commitment. J. Algorithms 9(4), 568–582 (1988)
Beauquier, J., Burman, J., Kutten, S.: Making population protocols self-stabilizing. SSS 90–104 (2009)
Becchetti, L., Clementi, A.E.F., Natale, E., Pasquale, F., Silvestri, R., Trevisan, L.: Simple dynamics for plurality consensus. SPAA 247–256 (2014)
Ben-Shahar, O., Dolev, S., Dolgin, A., Segal, M.: Direction election in flocking swarms. Ad Hoc Netw. 12, 250–258 (2014)
Buck, J.: Synchronous rhythmic flashing of fireflies II. Q. Rev. Biol. 63(3), 265–289 (1988)
Brumm, H., Slabbekoorn, H.: Acoustic communication in noise. Adv. Study Behav. 35, 151–209 (2005)
Carrol, M.C.: The complement system in regulation of adaptive immunity. Nat. Immunol. 5, 981–986 (2004)
Censor-Hillel, K., Haeupler, B., Kelner, J. A., Maymounkov, P.: Global computation in a poorly connected world: fast rumor-spreading with no dependence on conductance. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 961–970 (2012)
Chazelle, B.: Natural algorithms. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 422–431 (2009)
Cooper, C., Elsässer, R., Radzik, T.: The power of two choices in distributed voting. ICALP 2, 435–446 (2014)
Demers, A.J., Greene, D.H., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H.E., Swinehart, D.C., Terry, D.B.: Epidemic algorithms for replicated database maintenance. Oper. Syst. Rev. 22(1), 8–32 (1988)
Devdatt, D., Desh, R.: Balls and bins: a study in negative dependence. Random Struct. Algorithms 13(2), 99–124 (1998)
Diks, K., Pelc, A.: Optimal adaptive broadcasting with a bounded fraction of faulty nodes. Algorithmica 28(1), 37–50 (2000)
Doerr, B., Goldberg, L.A., Minder, L., Sauerwald, T., Scheideler, C.: Stabilizing consensus with the power of two choices. In: SPAA, pp. 149–158 (2011)
Doerr, B., Fouz, M.: Asymptotically optimal rumor-spreading. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), pp. 502–513 (2011)
Elsässer, R., Sauerwald, T.: On the runtime and robustness of randomized broadcasting. Theor. Comput. Sci. 410(36), 3414–3427 (2009)
Emek, Y., Wattenhofer, R.: Stone age distributed computing. In: Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 137–146 (2013)
Feinerman, O., Jentsch, G., Tkach, K., Coward, J., Hathorn, M., Sneddon, M., Emonet, T., Smith, K., Altan-Bonnet, G.: Single-cell quantification of IL-2 response by effector and regulatory T cells reveals critical plasticity in immune response. Mol. Syst. Biol. 6, 437 (2010)
Feinerman, O., Korman, A.: Memory lower bounds for randomized collaborative search and implications for biology. In: Proceedings of the 26th International Symposium on Distributed Computing (DISC), pp. 61–75 (2012)
Feinerman, O., Korman, A., Lotker, Z., Sereni, J.S.: Collaborative search on the plane without communication. In: Proceedings of the 31st ACM Symposium on Principles of Distributed Computing (PODC), pp. 77–86 (2012)
Feinerman, O., Veiga, J., Dorfman, J., Germain, R., Altan-Bonnet, G.: Variability and robustness in T cell activation from regulated heterogeneity in protein levels. Science 321(5892), 1081–1084 (2008)
Franks, N.R., Pratt, S.C., Mallon, E.B., Britton, N.F., Sumpter, D.J.T.: Information flow, opinion polling and collective intelligence in house hunting social insects. R. Soc. B 537(1427), 1567–1583 (2002)
El Gamal, A., Kim, Y.H.: Network Information Theory. Cambridge University Press, Cambridge (2012)
Georgiou, C., Gilbert, S., Guerraoui, R., Kowalski, D.R.: Asynchronous gossip. J. ACM 60(2), 11 (2013)
Gasieniec, L., Pelc, A.: Adaptive broadcasting with faulty nodes. Parallel Comput. 22(6), 903–912 (1996)
Giakkoupis, G., Sauerwald, T.: rumor-spreading and vertex expansion. In: Proceedigs of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1623–1641 (2012)
Haeupler, B.: Analyzing network coding gossip made easy. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 293–302 (2011)
Haeupler, B., Malkhi, D.: Optimal gossip with direct addressing. In: Proceedigs of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 176–185 (2014)
Ikegaya, Y., Aaron, G., Cossart, R., Aronov, D., Lampl, I., Ferster, D., Yuste, R.: Synfire chains and cortical songs: temporal modules of cortical activity. Science 304(5670), 559–564 (2004)
Joag-Dev, K., Proschan, F.: Negative association of random variables with applications. Ann. Stat. 286–295 (1983)
Kar, S., Moura, J.M.F.: Distributed consensus algorithms in sensor networks with imperfect communication: link failures and channel noise. IEEE Trans. Signal Process. 57(1), 355–369 (2009)
Karp, R.M., Schindelhauer, C., Shenker, S., Vöcking, B.: Randomized rumor-spreading. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 565–574 (2000)
Koetter, R., Kschischang, F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inf. Theory 54(8), 3579–3591 (2008)
Lengagne, T., Aubin, T., Lauga, J., Jouventin, P.J.: How do king penguins (Aptenodytes patagonicus) apply the mathematical theory of information to communicate in windy conditions? Proc. R. Soc. B Biol. Sci. 266(1429), 1623–1628 (1999)
Mertzios, G.B., Nikoletseas, S.E., Raptopoulos, C., Spirakis, P.G.: Natural models for evolution on networks. Theor. Comput. Sci. 477, 76–95 (2013)
Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Mediated population protocols. Theor. Comput. Sci. 412(22), 2434–2450 (2011)
Newman, M.E.J.: Spread of epidemic disease on networks. Phys. Rev. E 66(16128) (2002)
Mobilia, M.: Does a single zealot affect an infinite group of voters? Phys. Rev. Lett. 91(028701), 1–4 (2003)
Mobilia, M., Petersen, A., Redner, S.: On the role of zealotry in the voter model. J. Stat. Mech. P08029 (2007)
Moon, T.: Error Correction Coding: Mathematical Methods and Algorithms. Wiley-Interscience, New York (2005)
Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds. SIAM J. Comput. 26, 350–368 (1997)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)
Pittel, Boris: On spreading a rumor. SIAM J. Appl. Math. 47(1), 213–223 (1987)
Razin, N., Eckmann, J.P., Feinerman, O.: Desert ants achieve reliable recruitment across noisy interactions. J. R. Soc. Interface 10(20130079) (2013)
Roberts, G.: Why individual vigilance increases as group size increases. Anim. Behav. 51, 1077–1086 (1996)
Shannon, C.: A mathematical theory of communication. Bell Syst. Tech. J. 27(3), 379–423 (1948)
Sumpter, D.J.T., Krause, J., James, R., Couzin, I.D., Ward, A.J.W.: Consensus decision making by fish. Curr. Biol. 22(25), 1773–1777 (2008)
Sykulev, Y., Joo, M., Vturina, I., Tsomides, T.J., Eisen, H.N.: Evidence that a single peptide-MHC complex on a target cell can elicit a cytolytic T cell response. Immunity 4(6), 565–571 (1996)
Doerr, B., Huber, A., Levavi, A.: Strong robustness of randomized rumor-spreading protocols. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC), pp. 812–821 (2009)
Wilson, E.O., Holldobler, B.: The Superorganism: The Beauty, Elegance, and Strangeness of Insect Societies. W. W. Norton & Company, New York (2008)