Maximal Independent Set val är ett grundläggande problem i distribuerad dator. En ny probabilistisk algoritm för detta problem har nyligen föreslagits av Afek et al, inspirerad av studien av hur utvecklande celler i flugan blir specialiserade. Den algoritm de föreslår är enkel och robust, men inte lika effektiv som tidigare metoder: den förväntade tids komplexiteten är O(log 2 n). Här visar vi först att Afek et als tillvägagångssätt inte kan uppnå bättre effektivitet än detta i alla nätverk, oavsett hur de globala sannolikhetsvärdena väljs. Men sedan föreslår vi en ny algoritm som innehåller en annan viktig egenskap hos det biologiska systemet: sannolikhetsvärdet vid varje nod anpassas med hjälp av lokal återkoppling från angränsande noder. Vår nya algoritm behåller alla fördelar med enkelhet och robusthet, men uppnår också optimal effektivitet av O(log n) förväntad tid. Den nya algoritmen har också bara en konstant meddelande komplexitet per nod.
Efter detta arbete, Scott et al. REF presenterar i modellen B cd L en randomiserad algoritm med återkopplingsmekanism vars förväntade tid att beräkna en MIS är O(log n).
Feedback from nature: an optimal distributed algorithm for maximal independent set selection
{'venue': "PODC '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}