Hur nätverk av biologiska celler löser distribuerade datorproblem

Distribuerad datoranvändning är på modet nu för tiden. Tanken är att dela upp beräkningsuppgifter i bekväma bitar och distribuera dem över ett nätverk till ett antal datorer. Fördelarna är tydliga, som enkel tillgång på begäran till enorma datorresurser.

Det konventionella sättet att tänka på dessa system är som oberoende Turing-maskiner kopplade till ett nätverk som gör att de kan utbyta stora meddelanden. Denna så kallade 'message passing model' gäller förvisso mycket av den distribuerade datoranvändning som sker på internet; projekt som t.exSETI @ homeoch Einstein @home-programmen.

Men det finns en växande medvetenhet om att många nätverk är mycket mer begränsade, både i storleken på de meddelanden de kan sända och ta emot och även i bearbetningskapaciteten vid varje nod.

En biologisk cell, till exempel, kan endast överföra och ta emot begränsade mängder information och kan endast utföra rudimentära bearbetningsuppgifter. Det är lätt att föreställa sig att ett nätverk av celler bara kan utföra mycket enkla distribuerade datoruppgifter. Å andra sidan kanske de kan kompensera för sina individuella brister genom att arbeta som en grupp och är därför lika kapabla som andra nätverk.

Så en viktig fråga är hur dessa begränsningar påverkar klasserna av distribuerade datoruppgifter som grupper av celler kan utföra.

Idag har vi ett svar tack vare arbetet av Yuval Emek, Jasmin Smula och Roger Wattenhofer vid Swiss Federal Institute of Technology i Zürich. Vi tror att det finns ett behov av en nätverksmodell, där noder designmässigt ligger under beräknings- och kommunikationsförmågan hos Turing-maskiner, säger de.

Dessa killar har modellerat beräkningsbeteendet för ett nätverk av dessa sub-Turing-maskiner, som de kallar finita tillståndsmaskiner. De visar att långt ifrån att vara kritiskt handikappade, är ett nätverk av finita tillståndsmaskiner kapabelt att lösa många av standardproblemen i konventionell distribuerad datoranvändning, såsom 3-färgning av oriktade träd.

Dessutom kan dessa nätverk göra jobbet lika effektivt – i en tid som är polylogaritmisk med antalet celler.

Det kan visa sig få långtgående konsekvenser. Det kan vara svårt att föreställa sig ett nätverk av celler som går med iSETI @ homeprojekt. Men det ger ett ramverk för att studera hur nätverk av celler kan lösa andra vanliga problem i biologiska system som framåtplanering, banaberäkningar och så vidare.

Den nya modellen kan också tillämpas på mer prosaiska sätt, som att förutsäga prestandan hos nätverk av sensorer som är starkt begränsade av effektbegränsningar.

Emek och co ställer frågan: beräknar och/eller kommunicerar små bio/nano-noder i huvudsak [på] samma [sätt] som en dator?

Svaret verkar vara ja, vilket betyder att det är en spännande tid att vara en distribuerad datorspecialist som arbetar inom biologi.

Ref: arxiv.org/abs/1202.1186 : Stone Age Distributed Computing

Dölj