Biologisches Distributed Computing

Schweizer Informatiker haben gezeigt, dass Netzwerke aus einfachen Zellen genauso effizient rechnen können wie vernetzte Turingmaschinen.

Verteiltes Rechnen liegt aus guten Gründen seit Jahren im Trend: Vernetzte Rechner erledigen komplexe Aufgaben schneller, wenn sie in leicht verdauliche Happen zerlegt und gemeinsam bewältigt werden. So arbeiten beispielsweise Projekte in der Weltraumforschung wie SETI@Home oder Einstein@Home, an denen Hunderttausende per Internet koordinierte PCs arbeiten.

Die IT-Theorie des Distributed Computing geht dabei stets von einer Anzahl Turingmaschinen aus, die miteinander kommunizieren können – in Form des sogenannten Message Passing Model, bei dem Prozesse und Objekte in einem Programm Nachrichten sowohl senden als auch empfangen dürfen. Dies bedingt stets eine gewisse Komplexität.

Die Forscher Yuval Emek, Jasmin Smula und Roger Wattenhofer von der Eidgenössischen Technischen Hochschule (ETH) in Zürich haben nun in einer neuen Studie gezeigt, dass verteiltes Rechnen auch mit deutlich einfacheren Strukturen funktionieren könnte.

Eine biologische Zelle kann beispielsweise nur eine eingeschränkte Anzahl an Informationen empfangen und weitergeben und selbst nur rudimentäre Verarbeitungsschritte vornehmen. Entsprechend naheliegend wäre es eigentlich, dass ein Netzwerk aus solchen Entitäten nur sehr einfache verteilte Rechenarbeit leisten kann.

Das ETH-Team hat mit Modellrechnungen nun aber gezeigt, dass ein Netzwerk aus solchen Knoten durchaus leistungsfähig ist. Die individuellen Nachteile der Zellen scheinen sich gegenseitig aufzuheben, in dem sie als Gruppe agieren.

Die einzelnen Bestandteile sind sogenannte "Finite State Machines", also endliche Automaten. In der Praxis scheinen sie kaum benachteiligt zu sein: Die Finite State Machines können viele der Standardprobleme im konventionellen verteilten Rechnen lösen – etwa bei der Färbung innerhalb der Graphentheorie. Solche Jobs erledigt das Netz laut dem Modell des ETH-Teams mindestens genauso effizient wie Turingmaschinen - und das in einer Zeit, die polylogarithmisch zur Anzahl der Zellen ist.

"Wir glauben, dass wir ein neues Netzwerkmodell brauchen, bei dem die Knoten von vorneherein so gestaltet sind, dass ihre Rechen- und Kommunikationsfähigkeiten unter denen von Turingmaschinen liegen", schreiben die Forscher in ihrer Studie. Allerdings sei noch nicht abschließend geklärt, wie variabel das Modell ist. Das ETH-Team stellt zudem die Frage in den Raum, ob biologische Knoten nicht auch in der Natur in ihren Grundstrukturen computerartig "rechnen" und kommunizieren könnten.

Das Ergebnis der Studie dürfte durchaus praktische Auswirkungen haben. Zwar wird ein Netzwerk aus biologischen Zellen kaum eines Tages bei einem praktischen Projekt wie SETI@Home zum Einsatz kommen. Doch die Studie liefert den Rahmen dafür, wie man ein solches Konstrukt dazu bringen könnte, alltägliche verteilte Probleme zu lösen, denen es nicht an Komplexität fehlt. Übertragbar ist die Idee beispielsweise auf ein Netzwerk aus technisch eingeschränkten Sensoren, die derzeit aufgrund geringer Rechenleistung nicht smart genug sind. (bsc)