Notes taken by Ted Pavlic ====================================================================== *** 10:00 AM Conference opens: Nancy Lynch introduction -- Hopefully the conference will foster new collaborations -- Results will be featured on-line in the form of notes, talk slides, blog entries, etc. ====================================================================== *** 10:15 AM -- Anna Dornhaus -- Distributed problem solving in nature: social-insect colonies -- Goal of talk: Explain what do biologists study -- Eusocial insects (ants, termites, some bees and wasps) * Live in groups * Some species have colonies that are small (~100 individuals), other species have colonies that are very large (10 million individuals). Colony size can vary within species. * Diverse lifestyles * Common characteristics: ** Distributed and decentralized problem solving ** Queen is only the ovaries of the colony; she does not direct individuals ** Most individuals doing the work do not reproduce -- Anna's study species #1: "Rock Ants" of the genus /Temnothorax/ * Colonies have up to a few hundred individuals * Can live in a rock crevice or even a small acorn * Often used to study collective decision making -- Anna's study species #2: honeybees * 10's of thousands of individuals * Very dense (compared to /Temnothorax/) -- colonies often consist of two layers of bees -- Anna's study species #3: bumblebees * Much lower density * 150 individuals in a colony * Group size starts at 1 individual initially (whereas new honeybee colonies start with workers from the mother colony) -- Collective behavior interests: 1. Task allocation -- How do individuals choose? 2. Collective foraging 3. Nest construction -- Collective behavior in non-eusocial animals is fundamentally different * A herd of sheep has not been adapted to enhance properties of the *group*. Instead, it emerges from selection at the *individual* level. Eusoecial insects have a stronger coupling that makes interpretation difficult at any level aside from the group. * Eusocial insects are more like cells of the body than individuals in a sheep herd -- From developing embryos to robotics, there are common problems and solutions found in social insects. So social insects may be innovative and we may be able to learn from them in order to assist these otherwise unrelated fields. -- Example social-insect challenge: Foraging * In a social-insect colony, only 5% (for Temnothorax) to 30% (for honeybees) collect food. For the average social-insect colony, only 10% of a colony collects food. * Foragers travel long distances with respect to body size (10 miles for bees, 10's to 100's of meters for honeybees) * There is extremely high mortality risk * There is large variation in resource quality over time and space -- There is a large diversity in communication strategies * Visual, chemical, vibration, etc. * Trail laying, blackboards, beacon, tandem running, etc. * Information varies in coarseness -- Navigation is a separate issue for each individual social insect, but it is typically not considered by social-insect researchers as it is not a collective phenomenon (with army ants as an exception). ** What question's do biologists ask? == 'HOW' QUESTIONS == -- What are the individual-level rules and machinery required to implement those rules? (e.g., paint individual ants and track them to determine the polices that each ant uses in a collective behavior, like nest-site selection) -- Example: symmetry breaking in foraging * Colonies must focus on one out of three equal food sources * Positive feedback amplifies small initial differences in order to break the symmetry and make a quick decision ** For *foraging*, why choose a single food choices and not exploit all three equally? ** A similar process for nest-site selection would be good because quick group consensus to one alternative is necessary. ** Some species are more asymmetric in food choices than others. Is there an ecological context to explain the differences? ** Can we use individual-based models (or "agent-based models") to investigate whether hypothesized individual-based rules produce similar results to those observed in nature? == 'WHY' QUESTIONS == * Honeybees use a "waggle dance" to communicate precise polar coordinates (distance and angle). But other bees do not use a similar mechanism. WHY? Apparently it has advantages in some contexts but not in others, or there are developmental constraints in other bees that restrict its evolution. ** It is difficult to investigate the waggle-dance question empirically, but it is possible by turning nests on their side so that waggle-dancing bees cannot orient. - Results: Waggle dance has greatest impact on honeybee productivity when there is diversity in flower types. The density of flowers has no effect. There is an increase in speed with waggle dancing, but it is possible that this trades off accuracy. ** But it's harder to investigate larger questions, like WHY bumblebees use a "blackboard" system that does not encode the same kind of distance information... and WHY bumblebees have redundant systems (blackboard plus pheromone recruitment) instead of just one. * Another example: Why size polymorphism in bumblebees? Why are there large and small workers? Are they bet hedging? Is it more economical? ** How to address this problem in a larger set of species * Another example: Why so many lazy ants? * Another example: Why is workload distribution so uneven? == CONCLUSION TO ANNA'S TALK == *Models* can help find **general** rules to understand *both* the "HOW" and "WHY" questions that biologists ask. ====================================================================== * 10:45 AM -- Nancy Lynch ("Distributed Algorithms and Biological Systems" -- PART I) - DC community looking for biological systems to study and biological strategies for technological inspiration - How to contribute *back* to biological researchers? == What are distributed systems? * Abstract models of many interacting parts working toward a goal -- Swarms, wired/wireless networks, and social-insect colonies * Distributed algorithms research -- formal models for algorithmic analysis -- lower bounds and impossibility results ** Example problems: Agreement, consensus, data management, etc. ** Models: Interacting automata, local commnunication, shared memory, etc. ** Algorithms: Simple rules with complicated bookkeeping to analyze and optimize == Lower bounds and impossibility results: * Can't solve a problem in certain models at all, or can't solve them within certain time constraints == Formal modeling * Many components, concurrent, different speeds * Clear *mathematical* foundations * Interacting automata -- timing, probabilistic, discrete and continuous, composable pieces, correctness and cost analysis == Three separate areas in CS: * Problems * Platforms (capabilities -- "hardware") * Algorithms ("software") Then cost metrics can be used to analyze and compare algorithms and prove lower bounds. == How to help biologists? * Model with automata ** Identify cost metrics ** Try to predict system behavior ** Prove certain beahviors optimal == Examples * Example: Leader election ** System of processes send messages ** Exactly one should be elected to be leader ** Impossible for completely deterministic algorithm (no way to break symmetry) ** Solution: Deterministic algo with unique ID's per process -- Can then analyze how many rounds needed ** Solution: Probabilistic algo with no unique IDs but known total # of processes (toss unfair coin and keep trying until only 1 comes up heads in the group) -- Can analyze how many rounds are expected to be needed and compare to completely deterministic approach with unique ID's * Example: Maximally Independent Set (MIS) ** Given set of nodes with neighbors represented by edges in a graph ** Can build a set of nodes that includes no neighbors ** The largest such set will have the property that adding any other node will lose the no-neighbor property ** Such MIS have been found in developmental biology (sensory organ precursor) ** Solution cannot be solved *in general* with a deterministic algorithm ** Instead, solution is probabilistic and finishes with probability 1 and an expected number of rounds available to be analyzed * Other examples: spanning trees, consensus, etc. * More recently, interest in *dynamic* networks where topology changes in time -- relationship to insect societies? * More recently, ant foraging models with 2D spaces for searching for food ** No communication, limited ant memory ** Provide lower bounds on expected time to find food (basic prob. thy) ** Effects of memory size * More recently, ant task allocation ** Try to minimize energy deficits for all tasks ** Need extra task types to damp oscillations ====================================================================== * Saket Navlakha ("Distributed Algorithms and Biological Systems" -- PART II) * Example: Slime moulds and minimum spanning trees (MST) ** Faced with oats placed on locations proportional to major cities in Japan, slime mould reinforces pathways very similar to Tokyo rail network ** PROBLEM: Transport network design ** PLATFORM: Distributed, unknown locations, msg passing between nodes ** ALGORITHM: Feedback: Greater flow --> thicker tube to reinforce preferred routes ** EVALUATION: Network efficiency and robustness ** Modeled as a network flow problem with sources, sinks, and flow conservation -- Start with a large mesh network and determine which edges to keep by letting the edge weights evolve and culling edges with low weights -- Edge weights evolve dynamically according to a simple ODE -- The terms in the ODE are computed locally -- Can parameterize the evolution of the system to trade performance and accuracy * Example: Network development in brain ** Synaptic pruning: Development initially grows many synapses and then prunes starting at age 2 -- Very common in learning systems, but seems inefficient -- Explanation? -- Explore possible good solutions first and then reinforce important networks later when specificity is greater in the environmental challenges ** PROBLEM: Design network very specific to input pattern from environment, where that input pattern is *unknown* initially ** Distributed implementation like slime mould above ** In model, a critical parameter not previously explored is the **RATE** of pruning --- Prune edges all that once? Ramp up over time? Could differences from nominal rate explain some diseases? ** Based on experimental data in real systems, there is a RAPID elimination of edges and then a tapering off -- In the model, this strategy actually improves network performance * Example: _E. coli_ foraging (chemotaxis and gradient following) ** PROBLEM: How to collectively navigate? That is, how does a "swarm" of _E. coli_ navigate to a food source? Speed and accuracy tradeoff? ** MODEL: Use a Reynolds--Vicsek-like model for chemotaxis, with attraction, alignment, and repulsion zones (like flocking models) ** Just following gradient doesn't match real data ** Static interactions also don't work (makes mistakes) ** Plasticity -- Control interaction weights based on history -- leads to much more efficient paths to food source ====================================================================== * 11:30 AM -- Ofer Feinerman ("Queen for a moment: Collective load transport in ants") ** "Conformism without conservatism" ** Collective transport (e.g., "crazy ants" -- _Paratrechina longicornis_) *** Rare outside of humans and ants *** Coordination is required *** Complete individualism leads to much wasted coordination *** Aligning forces is easy in humans with a rope or a road, but it is not clear how other animals do it * Can you mix "INSIDE" and "OUTSIDE" attention? ** Attention: "INSIDE" -- Behavioral conforimism, like fish school alignment patterns ** Attention: "OUTSIDE" -- Can be problematic in unpredictable and dynamic environment because too little information is available to a single individual about the environment * Video analysis: Crazy ants carrying a Cheerio ** Automatically track every ant and the object being carried ** Analyze trajectories ** Object always ends up moving in the correct direction, but it takes many detours and loops ** So are ants looking "inwards" or "outwards"? * By increasing number of ants, speed of object increases linearly ** But difference between front population and back population stays constant ** So ants are always looking "inward" -- they're always doing the same thing * When an ant attaches to a load, that single new ant can redirect a load back in a correct direction even though many other ants connected ** The entropy drops up to 5 seconds after an attachment but then rises back to initial levels at 10 seconds ** So here, these attached ants are looking "OUTWARD" and directing the swarm, and the swarm is otherwise looking "INWARD" and maintaining its heading between new attachments * How do they direct attention to *both* inward and outward directions? ** To answer, build a quantitative algorithm/model where "informed" ants pull toward nest for 10 seconds and then become non-informed. non-informed ants can pull according to local velocity (or they can lift). A parameter in the model lets them switch between modes. The only communication is through the physical forces on the object. ** The best fit of this model is near the predicted optimum response ** In the model, moving parameters to more "individual" based makes object behave like random walk. Moving parameters be "less individual" leads to a too stubborn object with much inertia. Real ants are in between. * By varying load size in real ants, can get changes (predicted by the model) similar to changing individuality parameter. In this way, can adjust real ants' internal "individuality." ** Small loads pass obstacles much faster (very large can get stuck) ** Large loads have very conservative trajectories * Conclusion: Informed ants are "mayor for a day" -- In the long run, they have no effect. Nevertheless, it is still better for uniformed ants to have some individuality and not just "go with the flow." ====================================================================== * 12:00 PM -- Mira Radeva -- "Studying house-hunting in _Temnothorax_ using distributed computing theory" * Cast ant colony in distributed computing model to get biological insights * "Rock ants" (/Temnothorax/) have nests that are frequently destroyed, and they search for a new nest. Several candidates will be found, and the colony will have to agree on a candidate nest. * Individuals move through states: SEARCH, ASSESS, LEAD TANDEM RUNS, TRANSPORT ANTS where "LEAD TANDEM RUNS" either loops back to itself or goes to "TRANSPORT ANTS." The switch to "TRANSPORT ANTS" occurs at a critical population at a candidate nest. * MODEL (Platform): -- n ants -- k nests (with one "best" nest) -- ants can count other ants in candidate nest -- ants can recruit by tandem run -- ants can carry by transporting * What is the minimum # of steps to solve problem? (a "round" is either search, tandem run, or transport) -- Solution: Consensus on best nest * CASE 1: No search, only tandem running and transport -- This model is similar to gossip and rumor spreading. The question is how long to disseminate info to all about a best nest. -- For gossip like this, log n rounds are required * CASE 2: Only search, no tandem running nor transport -- n/k ants find the nest in first round, etc. -- So k log n rounds required * TOGETHER: At *least* log n rounds are required * Consider algorithm with SEARCH *and* recruitment -- Compare increase and decrease in scout population at each nest candidate from round to round -- log k rounds for 1 ant to find the nest -- log n rounds to recruit everyone else -- total time: log k + log n -- these results match expectations from CASE 1 and CASE 2 * DC results: Nest-site selection looks like gossip/consensus * Bio insights? How can this result be useful in biology?