Muszka owocówka udoskonaliła algorytm komputerowy

| Technologia
Image Editor, CC-BY

Muszka owocówka, którą, jak się wydaje, dobrze poznaliśmy, znowu zaskoczyła naukowców pokazując, jak mało pomysłowi są ludzie w porównaniu z naturą. Owad wykorzystuje niewielkie podobne do włosków struktury do odbierania bodźców zewnętrznych, a struktury te są zorganizowane w sposób jednocześnie niezwykle prosty i niezwykle efektywny. To tak proste i intuicyjne rozwiązanie, że nie mogę uwierzyć, iż ludzie nie wpadli na to już 25 lat temu - mówi matematyk i informatyk z Tel Awiwu, Noga Alon.

Poznanie sposobu organizacji połączeń pomiędzy wspomnianymi strukturami przyczyni się do stworzenia doskonalszych sieci i programów komputerowych oraz sieci czujników. Już teraz wiadomo, że komórki nerwowe tworzące połączenia u muszki owocówki zorganizowały się w ten sposób, że część z nich to liderzy mający połączenie z każdą inną komórką. W podobny sposób zorganizowane są komputerowe sieci rozproszone, od takich umożliwiających przeszukiwanie internetu po te sterujące samolotem podczas lotu. Jednak tym, co wprawiło naukowców w zdumienie jest fakt, że u muszek owocówek organizacja tych sieci jest znacznie prostsza, bardziej wydajna i odporna na zakłócenia niż wszystko, co wymyślił człowiek.

Uczeni wykorzystali zdobytą wiedzę do stworzenia nowego algorytmu działania sieci rozproszonych. Podczas jego testów odkryli, że jest on szczególnie przydatny do sieci, w których liczba węzłów i ich położenie nie są całkowicie pewne. Algorytm taki świetnie sprawdzi się w zarządzaniu np. sieciami rozproszonych w wodzie czujników czy też do dużymi grupami robotów.

Naukowcy od dawna używają modeli komputerowych i matematycznych do analizowania systemów biologicznych. Tutaj zastosowaliśmy odwrotną strategię i studiujemy system biologiczny, by rozwiązać problem z dziedziny informatyki - mówi Zvi Bar-Joseph z Carnegie Mellon University.

Badanie połączeń nerwowych muszki owocówki pozwoli na rozwiązanie jednego z bardzo istotnych problemów matematyczno-informatycznych. Obecnie rozległe sieci komputerowe korzystają z przetwarzania rozproszonego. Tysiące czy miliony procesorów wspólnie pracują nad rozwiązaniem tego samego problemu, żaden z nich nie ma kompletnej wiedzy o tym, co jest przetwarzane, a całość musi pracować pomimo błędów czy awarii występujących w pojedynczych elementach. Aby taki system działał konieczne jest wyznaczenie procesorów-liderów, które będą w stanie szybko komunikować się z innymi procesorami sieci. W teorii grafów nazywa się to maksymalnym zbiorem niezależnym (MIS). Każdy z procesorów w sieci jest albo liderem, członkiem MIS, albo też jest połączony z liderem. Natomiast liderzy nie są ze sobą bezpośrednio połączeni. Eksperci od 30 lat poszukują najlepszego sposobu nad optymalnym wyznaczanie przez sieć elementów, które powinny należeć do MIS. Obecnie najczęściej stosuje się metodę probabilistyczną, w której procesory samodzielnie przejmują rolę liderów na podstawie liczby bezpośrednich połączeń, które mają z innymi procesorami. W każdej rundzie wykonywania algorytmu dochodzi do ponownego wybrania liderów na podstawie liczby połączeń.

Liderzy wybierani są błyskawicznie, jednak cały proces związany jest z wysyłaniem olbrzymiej liczby dodatkowych informacji oraz wymaga od procesorów, by z wyprzedzeniem znały liczbę przypadających nań połączeń. To stanowi olbrzymi problem w przypadku sieci bezprzewodowych czujników, których położenie może być przypadkowe, a połączenia między nimi nie są im znane, gdyż nie każdy czujnik będzie znajdował się w zasięgu każdego innego czujnika.

Naukowcy odkryli, że u muszki owocówki, już podczas jej rozwoju, wybierane są komórki nerwowe, które będą liderami. Jednak, w przeciwieństwie do opisanych powyżej procesorów, komórki nie mają informacji o połączeniach z innymi. Komórki, które same wybrały się na liderów, wysyłają po prostu sygnały, które powodują, że bezpośrednio połączone z nimi komórki nie zostają liderami. Taki proces trwa zaledwie trzy godziny i w tym czasie zostają ustaleni liderzy i podlegające im komórki.

Bar-Joseph zauważa, że u muszki prawdopodobieństwo, iż komórka zostanie liderem nie jest - jak w przypadku sieci procesorów - funkcją liczby połączeń, ale funkcją czasu. To oznacza, że komórki nie muszą z wyprzedzeniem znać liczby połączeń, a komunikacja pomiędzy nimi jest maksymalnie uproszczona.

Badania algorytmu zbudowanego dzięki badaniu owadów wykazały, że działa on nieco wolniej od obecnie używanych, ale jest za to bardziej wydajny i odporny na zakłócenia.

Autor:

Źródło: PhysOrg

algorytm muszka owocówka sieci rozproszone maksymalny zbiór niezależny