More Like this

1. A Model and Analysis of House-Hunting in Ant Colonies

   Zhang, E. ; Zhao, J. ; Lynch, N. ( January 2021 , 8th Workshop on Biological Distributed Algorithms (BDA))

   We study the problem of house-hunting in ant colonies, where ants reach consensus on a new nest and relocate their colony to that nest, from a distributed computing perspective. We propose a house-hunting algorithm that is biologically inspired by Temnothorax ants. Each ant is modelled as a probabilistic agent with limited power, and there is no central control governing the ants. We show a Ω(log n) lower bound on the running time of our proposed house-hunting algorithm, where n is the number of ants. Further, we show a matching upper bound of expected O(log n) rounds for environments with only one candidate nest for the ants to move to. Our work provides insights into the house-hunting process, giving a perspective on how environmental factors such as nest qualities or a quorum rule can affect the emigration process. In particular, we find that a quorum threshold that is high enough causes transports to the inferior nest to cease to happen after O(log n) rounds when there are two nests in the environment. 

   more » « less
2. An Upper and Lower Bound for the Convergence Time of House-Hunting in Temnothorax Ant Colonies.

   Zhang, E. ; Zhao, J. ; Lynch, N. ( January 2022 , Journal of computational biology)

   We study the problem of house-hunting in ant colonies, where ants reach consensus on a new nest and relocate their colony to that nest, from a distributed computing perspective. We propose a house-hunting algorithm that is biologically inspired by Temnothorax ants. Each ant is modeled as a probabilistic agent with limited power, and there is no central control governing the ants. We show an O( log n) lower bound on the running time of our proposed house-hunting algorithm, where n is the number of ants. Furthermore, we show a matching upper bound of expected O( log n) rounds for environments with only one candidate nest for the ants to move to. Our work provides insights into the house-hunting process, giving a perspective on how environmental factors such as nest quality or a quorum rule can affect the emigration process. 

   more » « less
3. Lack of Quorum Sensing Leads to Failure of Consensus in Temnothorax Ant Emigration

   Zhao, J. ; Su, L. ; Lynch, N. ( January 2021 , 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2021))

   We investigate the importance of quorum sensing in the success of house-hunting of emigrating Temnothorax ant colonies. Specifically, we show that the absence of the quorum sensing mechanism leads to failure of consensus during emigrations. We tackle this problem through the lens of distributed computing by viewing it as a natural distributed consensus algorithm. We develop an agent-based model of the house-hunting process, and use mathematical tools such as conditional probability, concentration bounds and Markov mixing time to rigorously prove the negative impact of not employing the quorum sensing mechanism on emigration outcomes. Our main result is a high probability bound for failure of consensus without quorum sensing in a two-new-nest environment, which we further extend to the general multiple-new-nest environments. We also show preliminary evidence that appropriate quorum sizes indeed help with consensus during emigrations. Our work provides theoretical foundations to analyze why Temnothorax ants evolved to utilize the quorum rule in their house-hunting process. 

   more » « less
4. The Power of Population Effect in Temnothorax Ants House-Hunting: A Computational Modeling Approach.

   Zhao, J. ; Lynch, N. ; Pratt, S.C. ( January 2022 , Journal of computational biology)

   The decentralized cognition of animal groups is both a challenging biological problem and a potential basis for bio-inspired design. In this study, we investigated the house-hunting algorithm used by emigrating colonies of Temnothorax ants to reach consensus on a new nest. We developed a tractable model that encodes accurate individual behavior rules, and estimated our parameter values by matching simulated behaviors with observed ones on both the individual and group levels. We then used our model to explore a potential, but yet untested, component of the ants’ decision algorithm. Specifically, we examined the hypothesis that incorporating site population (the number of adult ants at each potential nest site) into individual perceptions of nest quality can improve emigration performance. Our results showed that attending to site population accelerates emigration and reduces the incidence of split decisions. This result suggests the value of testing empirically whether nest site scouts use site population in this way, in addition to the well demonstrated quorum rule. We also used our model to make other predictions with varying degrees of empirical support, including the high cognitive capacity of colonies and their rational time investment during decision-making. Additionally, we provide a versatile and easy-to-use Python simulator that can be used to explore other hypotheses or make testable predictions. It is our hope that the insights and the modeling tools can inspire further research from both the biology and computer science community. 

   more » « less
5. Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity

   https://doi.org/10.1145/3382734.3405718  

   Chatterjee, Soumyottam ; Gmyr, Robert ; Pandurangan, Gopal ( July 2020 , PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing)

   null (Ed.)

   Maximal Independent Set (MIS) is one of the fundamental problems in distributed computing. The round (time) complexity of distributed MIS has traditionally focused on the worst-case time for all nodes to finish. The best-known (randomized) MIS algorithms take O(log n) worst-case rounds on general graphs (where n is the number of nodes). Breaking the O(log n) worst-case bound has been a longstanding open problem, while currently the best-known lower bound is [EQUATION] rounds. Motivated by the goal to reduce total energy consumption in energy-constrained networks such as sensor and ad hoc wireless networks, we take an alternative approach to measuring performance. We focus on minimizing the total (or equivalently, the average) time for all nodes to finish. It is not clear whether the currently best-known algorithms yield constant-round (or even o(log n)) node-averaged round complexity for MIS in general graphs. We posit the sleeping model, a generalization of the traditional model, that allows nodes to enter either "sleep" or "waking" states at any round. While waking state corresponds to the default state in the traditional model, in sleeping state a node is "offline", i.e., it does not send or receive messages (and messages sent to it are dropped as well) and does not incur any time, communication, or local computation cost. Hence, in this model, only rounds in which a node is awake are counted and we are interested in minimizing the average as well as the worst-case number of rounds a node spends in the awake state, besides the traditional worst-case round complexity (i.e., the rounds for all nodes to finish including both the awake and sleeping rounds). Our main result is that we show that MIS can be solved in (expected) O(1) rounds under node-averaged awake complexity measure in the sleeping model. In particular, we present a randomized distributed algorithm for MIS that has expected O(1)-rounds node-averaged awake complexity and, with high probability1 has O(log n)-rounds worst-case awake complexity and O(log3.41 n)-rounds worst-case complexity. Our work is a step towards understanding the node-averaged complexity of MIS both in the traditional and sleeping models, as well as designing energy-efficient distributed algorithms for energy-constrained networks. 

   more » « less