Populační protokol - Population protocol

tento článek je sirotek, jako žádné další články odkaz na to. Prosím zavést odkazy na tuto stránku z související články; zkuste Najít odkaz nástroj pro návrhy. (únor 2013)

A populační protokol je distribuované výpočty model vytvořený mobilními agenty s omezeným zdrojem, kteří se náhodně setkávají podle interakční graf. Funkce se počítají aktualizací stavu agentů, kdykoli se setkají na základě jejich předchozího stavu, a výsledek výpočtu lze číst ve stavech agentů, jakmile má výpočet konvergované.

Modelka

K dispozici je sada ${ displaystyle N = {1,2, ldots, n }}$ uzlů. Každý uzel je konečný automat s ${ displaystyle s}$ státy. Důležitou třídou populačních protokolů jsou většinové algoritmy, jejichž cílem je vypočítat většinový bit: každý uzel začíná bitem víry v ${ displaystyle {0,1 }}$a cílem je navrhnout protokol, na jehož konci je bit víry každého uzlu správný počáteční většinový bit.

Diskrétní časová verze modelu je následující: v každém bodě ${ displaystyle t = 1,2, ldots}$včas nějaký uzel ${ displaystyle i}$ je vybrán rovnoměrně náhodně. Poté je uzel spárován s jiným uzlem ${ displaystyle j}$, který je náhodně vybrán jednotně ze sady sousedů uzlu ${ displaystyle i}$. Poté uzly ${ displaystyle i}$ a ${ displaystyle j}$ vyměňovat si obsah paměti a aktualizovat jejich stavy. Alternativně lze uvažovat o kontinuálním časovém modelu, kde každý uzel ${ displaystyle i}$ má Poissonovy hodiny, které zvoní jednotkovou rychlostí. Když hodiny uzlu zazvoní, tento uzel komunikuje s náhodným sousedem.

Protokoly jsou často navrženy tak, aby se minimalizovala doba konvergence nebo množství paměti požadované na uzel nebo obojí.^[1]

Protokol o třech státech

Pro problém výpočtu většiny (shoda) existuje známý protokol, který vyžaduje pouze tři stavy paměti na uzel a byl analyzován pro kompletní grafy interakce.^[2][3] Tento protokol funguje následovně. Nechte každý uzel ${ displaystyle i}$ inicializovat jeho paměťový stav na jejich počáteční bit víry ${ displaystyle b_ {i} v {0,1 }.}$ V každém okamžiku, kdy dva uzly komunikují, aktualizují svůj stav podle následující tabulky. Popisky řádků udávají stav iniciátora a popisky sloupců stav respondenta.

Například pokud uzel s vírou ${ displaystyle 0}$ dostane uzavřeno s uzlem s vírou ${ displaystyle 0}$, pak si oba uzly zachovají svoji víru; aktualizace je podobná, pokud jsou obě víry ${ displaystyle 1}$nebo oba jsou ${ displaystyle?}$. Pokud však víra iniciátora je ${ displaystyle 0}$ a víra respondenta je ${ displaystyle?}$, poté respondent aktualizuje svoji víru ${ displaystyle 0}$. Pokud má naopak iniciátor víru ${ displaystyle 0}$ a respondent má víru ${ displaystyle 1}$, pak respondent změní svou víru na ${ displaystyle?}$. Tento protokol je jednosměrný: každá interakce se mění maximálně ve stavu respondenta; lze jej tedy implementovat pomocí jednosměrné komunikace.

Angluin, Aspnes a Eisenstat ^[2] ukázal, že z jakékoli počáteční konfigurace, která nespočívá ve všech${ displaystyle?}$"s, třístavový protokol přibližné většiny konverguje buď ke všem uzlům, které věří ${ displaystyle 0}$ nebo všechny uzly, které mají víru ${ displaystyle 1}$ v rámci ${ displaystyle O (n cdot log n)}$ interakce s vysokou pravděpodobností. Vybraná hodnota bude navíc většinou ne- “${ displaystyle?}$"počáteční hodnota, pokud přesahuje menšinu dostatečným rozpětím.

Následující obrázek ukazuje vývoj protokolu tří stavů na sadě ${ displaystyle n = 500}$ uzly, kde jedna třetina uzlů má počáteční bit víry ${ displaystyle 0}$, zatímco zbývající dvě třetiny mají počáteční bit víry ${ displaystyle 1}$. Zlomek „${ displaystyle?}$"uzly (oranžově) začínají na nule, na chvíli se zvětšují a pak se opět pohybují na nulu.

Dějiny

Populační protokoly byly zavedeny Dana Angluin et al.^[4] jako jeden z prvních modely výpočtu být plně decentralizovaný a zapojit agenty s velmi omezenými zdroji, např. ti, kteří se nacházejí v senzorové sítě. Od té doby našel tento abstraktní výpočetní model aplikace v robotika^[5] a chemie.^[6]

Viz také

Swarm Intelligence

Reference