211service.com
Wie Netzwerke biologischer Zellen verteilte Rechenprobleme lösen
Verteiltes Computing ist heutzutage in aller Munde. Die Idee besteht darin, Rechenaufgaben in praktische Teile zu zerlegen und sie über ein Netzwerk auf eine Reihe von Computern zu verteilen. Die Vorteile liegen auf der Hand, wie beispielsweise der einfache On-Demand-Zugriff auf riesige Computerressourcen.
Herkömmlicherweise kann man sich diese Systeme als unabhängige Turing-Maschinen vorstellen, die durch ein Netzwerk verbunden sind, das es ihnen ermöglicht, große Nachrichten auszutauschen. Dieses sogenannte „Message-Passing-Modell“ gilt sicherlich für einen Großteil des verteilten Computings, das im Internet stattfindet; Projekte wie dieSETI @ homeund die Einstein @home-Programme.
Es gibt jedoch ein wachsendes Bewusstsein, dass viele Netzwerke viel begrenzter sind, sowohl in der Größe der Nachrichten, die sie senden und empfangen können, als auch in der Verarbeitungskapazität an jedem Knoten.
Eine biologische Zelle beispielsweise kann nur begrenzte Mengen an Informationen senden und empfangen und nur rudimentäre Verarbeitungsaufgaben ausführen. Es ist leicht vorstellbar, dass ein Netzwerk von Zellen nur sehr einfache verteilte Rechenaufgaben ausführen kann. Auf der anderen Seite können sie vielleicht ihre individuellen Defizite durch Gruppenarbeit ausgleichen und sind damit genauso leistungsfähig wie andere Netzwerke.
Eine wichtige Frage ist also, wie diese Einschränkungen die Klassen von verteilten Rechenaufgaben beeinflussen, die Gruppen von Zellen ausführen können.
Heute haben wir dank der Arbeit von Yuval Emek, Jasmin Smula und Roger Wattenhofer an der Eidgenössischen Technischen Hochschule in Zürich eine Antwort. Wir glauben, dass ein Netzwerkmodell benötigt wird, bei dem die Knoten konstruktionsbedingt unter den Rechen- und Kommunikationsfähigkeiten von Turing-Maschinen liegen, sagen sie.
Diese Jungs haben das Rechenverhalten eines Netzwerks dieser Sub-Turing-Maschinen modelliert, die sie endliche Automaten nennen. Sie zeigen, dass ein Netzwerk von endlichen Automaten weit davon entfernt ist, kritisch behindert zu sein, sondern in der Lage ist, viele der Standardprobleme des konventionellen verteilten Rechnens zu lösen, wie beispielsweise die 3-Färbung ungerichteter Bäume.
Darüber hinaus können diese Netzwerke die Arbeit genauso effizient erledigen – in einer Zeit, die mit der Anzahl der Zellen polylogarithmisch ist.
Das könnte weitreichende Folgen haben. Es mag weit hergeholt sein, sich ein Netzwerk von Zellen vorzustellen, die dieSETI @ homeProjekt. Aber es bietet einen Rahmen, in dem untersucht werden kann, wie Zellnetzwerke andere häufige Probleme in biologischen Systemen wie Vorausplanung, Flugbahnberechnungen usw. lösen könnten.
Das neue Modell kann auch prosaischer angewendet werden, beispielsweise zur Vorhersage der Leistung von Sensornetzwerken, die durch Leistungsbeschränkungen stark eingeschränkt sind.
Emek und Co stellen sich die Frage: Rechnen und/oder kommunizieren winzige Bio-/Nano-Knoten im Wesentlichen [auf] die gleiche [Weise] wie ein Computer?
Die Antwort, so scheint es, lautet ja, was bedeutet, dass es eine aufregende Zeit ist, ein Spezialist für verteilte Computer in der Biologie zu sein.
Ref: arxiv.org/abs/1202.1186 : Verteiltes Rechnen der Steinzeit