A Biological Solution to a Fundamental Distributed Computing Problem

DOI10.1126/science.1193210zbMath1226.92001OpenAlexW1984727163WikidataQ51613411 ScholiaQ51613411MaRDI QIDQ3101797

Naama Barkai, Ziv Bar-Joseph, Noga Alon, Yehuda Afek, Omer Barad, Hornstein Eran

Publication date: 30 November 2011

Published in: Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1126/science.1193210

Mathematics Subject Classification ID

Neural biology (92C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Computational methods for problems pertaining to biology (92-08)

Related Items (27)

Fixed points in conjunctive networks and maximal independent sets in graph contractions ⋮ Iteratively reweighted least squares and slime mold dynamics: connection and convergence ⋮ An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models ⋮ The ANTS problem ⋮ Searching without communicating: tradeoffs between performance and selection complexity ⋮ Find Your Place: Simple Distributed Algorithms for Community Detection ⋮ Multistate network model for the pathfinding problem with a self-recovery property ⋮ Unnamed Item ⋮ Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models ⋮ Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication ⋮ Optimal Message-Passing with Noisy Beeps ⋮ Distributed Self-Stabilizing MIS with Few States and Weak Communication ⋮ Beeping a maximal independent set ⋮ Simple Neural-Like P Systems for Maximal Independent Set Selection ⋮ Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks ⋮ Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits ⋮ Dynamic networks of finite state machines ⋮ Threshold-based network structural dynamics ⋮ Threshold-based network structural dynamics ⋮ The Synergy of Finite State Machines ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ Noisy rumor spreading and plurality consensus ⋮ An algorithmic approach to collective behavior ⋮ Noisy beeping networks ⋮ The epigenetic consensus problem

This page was built for publication: A Biological Solution to a Fundamental Distributed Computing Problem