Co-author Saket Navlakha discusses "Distributed Information Processing in Biological and Computational Systems," (cacm.acm.org/magazines/2015/1/181614) his Review Article in the January 2015 Communications of the ACM.
00:00-00:10 When you hear the words "distributed computing", do you think of this? Or this?
00:10-00:19 Both are collections of independent information processors, passing data to each other through a network.
00:19-00:28 What can these natural systems teach us about computers? And what can computer science tell us about the natural world?
00:28-00:40 Join me in San Diego as I talk with Savet Navlakha about Distributed information processing in biological and computational systems.
00:40-00:50 [Intro graphics/music]
00:50-00:58 The Salk Institute is situated by the sea, in an area famous for its natural beauty.
00:58-01:13 It's a fitting place for Dr. Navlakha. Here, he examines how the natural world solves problems, reaches decisions, and coordinates responses -- behaviors also central to distributed computing systems.
01:13-01:20 His work started, as with so much in biology, with Drosophila melanogaster -- the common fruit fly.
01:20-01:50 DR. NAVLAKHA: It's long been known that cells, during this developmental process, some of them become these sensory cells where they have little bristles coming out of their head... And this pattern that forms is what's called a maximal independent set... It serves the basis of a lot routing algorithms, a lot of clustering algorithms... And so developing algorithms based on how the fruit fly was solving this problem led to improved algorithms for this very fundamental distributed computing problem.
01:50-01:57 The fruit fly's developing cells communicate with each other using what Dr. Navlakha and co-author Ziv Bar-Joseph call the "Beeping" model.
01:57-02:19 DR. NAVLAKHA: O.K., so this is an extremely simple and restricted setting, where I have no idea necessarily how many neighbors I have, I don't even know who is actually beeping, all I know is if somebody around me has beeped... And what's been shown is that this maximal independent set problem can actually be solved even within this very restricted environment.
02:19-02:30 But the beeping model is only one that's employed both in nature and computer science. In their paper, Drs. Navlakha and Bar-Joseph identify three others.
02:30-02:42 First is the "stone-age model", where a node initiates events only after it receives signals beyond a certain threshhold. It's how both neurons and network traffic balancers work.
02:42-03:00 Then there's "population protocol". Like a group of friends calling each other to make a dinner date, each node talks to only one partner per step -- but partners change frequently. This communication method is used by flocking birds and TCP-based networks alike.
03:00-03:08 Finally, some biological systems communicate using "shared memory", much like writing bits to a hard drive.
03:08-03:29 DR. NAVLAKHA: If you think of DNA as shared memory, then you have specific proteins that are leaving marks on the DNA... And one of the classic results in distributed computing is that any algorithm that you can solve using a message-passing algorithm... that problem can also be solved via shared-memory algorithm.
03:29-03:59 But biological and computer systems are similar in ways beyond how they pass messages. They also both vary in their topology, from densely connected cliques... to weakly connected modules... to collections of nodes only barely connected. Each topology is a tradeoff between speed and robustness. These structures have a lot to teach us -- and in fact, nature has taught computer science quite a lot already.
03:59-04:14 DR. NAVLAKHA: Genetic algorithms came from biology; deep learning and neural networks originally came from how we thought the brain was working; non-negative matrix factorization; ant colony optimization; these are all ideas that have come from biology.
04:14-04:20 At the same time, computer science gives us special insight into the natural world.
04:20-04:37 DR. NAVLAKHA: And if you think of biology as also trying to solve computational problems, then we have really good frameworks and models to understand what different constraints are in place, and what you can do given those constraints to solve a problem.
04:37-04:47 Find out more in this month's Communications of the ACM, in the review article, "Distributed information processing in biological and computational systems".
04:47-05:02 [Outro and credits]