인구 프로토콜

인구 프로토콜은 자원 제한 모바일 에이전트에 의해 형성된 분산 컴퓨팅 모델이며, 상호 작용 그래프에 따라 임의로 만난다.함수는 이전 상태를 기준으로 만날 때마다 에이전트 상태를 업데이트하여 계산하며, 계산 결과는 계산이 수렴된 후 에이전트 상태에서 읽을 수 있다.

모델

$N$${\displaystyle }$= { 1,${\displaystyle 2}$, …${\displaystyle }$,${\displaystyle n\}}$ ${\displaystyle N=\{1$,2$,\ldots,n\} 노드$의 집합이 있다.각 노드는 $s{\displaystyle }$ ${\displaystyle s}$ 상태를$$ 가진 유한 자동이다.모집단 프로토콜의 중요한 클래스는 다수 알고리즘이며, 여기서 목표는 다수의 비트를 계산하는 것이다. 각 노드는${\displaystyle }${ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle \{0,1\}$의 믿음 비트로 시작하고 목표는$$ 모든 노드의 믿음 비트가 정확한 초기 다수 비트가 되는 프로토콜을 설계하는 것이다.

모델의 이산 시간 버전은 다음과 같다: 각 시점$$ $t{\displaystyle }$= ${\displaystyle 1}$,${\displaystyle 2}$,$…[\displaystyle t=1,2,\ldots }$에서 일부 노드 $i{\displaystyle }$ ${\displaystyle$ i$}$를 임의로 선택한다$$.그런 다음 노드는 다른 노드 $j{\displaystyle }$ ${\$$displaystyle$ $j}$과$($와) 일치하며, 노드 $i{\displaystyle }$ ${\$displaystyle $i}$의 인접 집합에서 무작위로 선택된다$.$ 그 후 노드 $i{\displaystyle }$ ${\displaystyle i}$와 $j{\displaystyle }$ ${\displaysty$ j$}$는 메모리 콘텐츠를 교환하고$$ 상태를 업데이트한다.또는 각 노드 $i{\displaystyle }$ ${\displaystyle i}$에 단위 속도로 울리는 포아송 시계가 있는$$ 연속 시간 모델을 고려할 수 있다.노드의 시계가 울리면, 그 노드는 임의의 이웃과 통신한다.

프로토콜은 종종 융합 시간이나 노드 또는 둘 다에 필요한 메모리 양을 최소화하도록 설계된다.^[1]

스리 스테이트 프로토콜

대다수의 계산 문제(컨센서스)에 대해서는 노드당 3개의 메모리 상태만을 필요로 하는 잘 알려진 프로토콜이 있으며, 완전한 상호작용 그래프를 위해 분석되었다.^[2][3]이 프로토콜은 다음과 같이 동작한다.각 노드 $i{\displaystyle }$ ${\displaystyle$ i$}$이(가) 메모리 상태를 초기$$ 믿음 비트 b ${\displaystyle i_{}}$ ${\displaystyle {}_{}}${ ${\displaystyle 0,}$ 1${\displaystyle }$. ${\displaystyle b_{i}\in \{0,1\}}$로 초기화하도록$$ 두 노드가 통신할 때마다 다음 표에 따라 상태를 업데이트한다.행 레이블은 이니시에이터의 상태를 나타내고 열은 응답자의 상태를 표시한다.

IMT-2000 3GPP-상태 프로토콜의 상호작용 규칙

	0	?	1
0	(0,0)	(0,0)	(0,?)
?	(?,0)	(?,?)	(?,1)
1	(1,?)	(1,1)	(1,1)

예를 들어, $신념{\displaystyle \mathrm{}}$ $0{\displaystyle \mathrm{}}$ ${\displaystyle$ 0$}$을(를) 가진 노드가 신념 0 ${\displaystyle 0}$을(를$)$ 가진 노드와 일치할$$ 경우, 두 노드는 믿음을 유지한다. 두 개의 신념이 $모두{\displaystyle \mathrm{}}$ 1 ${\displaystyle$ 1$}$이거나 둘 다${\displaystyle }$?$${\$displaystystyle ?}$인 경우 업데이트는 유사하지만$,$ 이니시에이터의 신념이 0 ${\daystyty$ 0$}$인 경우$$스폰더의 신념은 $?[\displaystyle$ $?\},$ 그 다음 응답자는 그들의 $믿음$을 0 ${\displaystyle 0}$으로 갱신한다$.$ 만약 다른 한편으로 개시자가 신념 $0{\displaystyle \mathrm{}}$ ${\\displaystyle$ $0}$을(를) 가지고 있다면$,$ 응답자는 $그들$의 믿음을 $?{\displaystyle }$ ${\displaystyle ?}$로 바꾼다는 점에 유의하십시오$.$단방향: 모든 상호작용은 응답자 상태에서 변경되므로 단방향 통신으로 구현될 수 있다.

Angluin, Aspnes, Eisenstat[2] 하는 모든"?{\displaystyle?}"s으로 구성되어 있지 않초기 구성에서, 데 대략적인 다수 프로토콜 모든 노드 믿음 0{0\displaystyle} 있는 또는 모든 노드 O(n⋅ 로그⁡ n){\disp 내에 믿음 1{1\displaystyle}에 전진을 보여 주었다.놓다$높은 확률$로 O$(n$\cdot \$log n)$ 스타일 교호작용$$.또한 충분한 마진수만큼 소수점을 초과한다면${\displaystyle }$ 선택한 값은 비" ${\displaystyle ?}$" 초기값이 될 것이다.

다음 그림은 $n{\displaystyle }$= ${\displaystyle 500}$ ${\displaystyle n=500}$ 노드의$$ 세트에 대한 세 가지 상태 프로토콜의 진화를 보여 주며, 노드의 1/3은 초기 믿음 비트 $[\displaystyle 0}$을(를) 가지고 있고$,$ 나머지 3분의 2는 초기 믿음 $비트{\displaystyle \mathrm{}}$ 1$[\displaystyle 1}$을(를)을(를) 가지고 있다$.$"${\displaystyle }$? ${\displaystyle$ $?\}"$ 노드(주황색)의 분율은 0에서 시작하여 한동안 증가하다가 다시 0으로 간다.

역사

인구 프로토콜은 완전히 분산되고 센서 네트워크에서 발견되는 것과 같이 매우 제한된 자원을 가진 에이전트를 포함하는 최초의 연산 모델 중 하나로 Dana Angluin 등에 의해 도입되었다.^[4]그 이후로, 이 추상적인 연산 모델은 로봇과^[5] 화학에서 응용 분야를 발견했다.^[6]

참고 항목

군집 지능

참조