Протокол популяции

A Протокол популяции является модель распределенных вычислений, сформированная мобильными агентами с ограниченными ресурсами, которые встречаются случайным образом в соответствии с. Функции вычисляются путем обновления состояния агентов всякий раз, когда они встречаются, на основе их предыдущего состояния, и результат вычисления может быть прочитан в состояниях агентов после того, как вычисления сойдутся.

• 1 Модель
• 2 Протокол трех состояний
• 3 История
• 4 См. Также
• 5 Ссылки

Имеется набор $N\; =\; \{1,\; 2,\dots ,\; n\; \}\; \{\backslash \; displaystyle\; N\; =\; \backslash \; \{1,2,\; \backslash \; ldots,\; n\; \backslash \}\}$узлов. Каждый узел представляет собой конечный автомат с состояниями $s\; \{\backslash \; displaystyle\; s\}$. Важным классом протоколов популяции являются алгоритмы большинства, целью которых является вычисление бита большинства: каждый узел начинается с бита доверия в $\{0,\; 1\}\; \{\backslash \; displaystyle\; \backslash \; \{0,1\; \backslash \}\}$, и цель состоит в том, чтобы разработать протокол, в конце которого бит доверия каждого узла является правильным начальным битом большинства.

Версия модели с дискретным временем выглядит следующим образом: в каждой точке $t\; =\; 1,\; 2,\dots \; \{\backslash \; displaystyle\; t\; =\; 1,2,\; \backslash \; ldots\}$во времени, некоторый узел $i\; \{\backslash \; displaystyle\; i\}$выбирается равномерно случайным образом. Затем узел сопоставляется с другим узлом $j\; \{\backslash \; displaystyle\; j\}$, который выбирается равномерно случайным образом из набора соседей узла $i\; \{\backslash \; displaystyle\; i\}$. После этого узлы $i\; \{\backslash \; displaystyle\; i\}$и $j\; \{\backslash \; displaystyle\; j\}$обмениваются содержимым памяти и обновляют свои состояния. В качестве альтернативы можно рассмотреть модель непрерывного времени, в которой каждый узел $i\; \{\backslash \; displaystyle\; i\}$имеет часы Пуассона, которые звонят с единичной скоростью. Когда часы узла звонят, этот узел связывается со случайным соседом.

Протоколы часто разрабатываются так, чтобы минимизировать время сходимости или объем памяти, требуемый на узел, или и то, и другое.

Для проблемы вычисления большинства (консенсус) существует хорошо известный протокол, который требует только три состояния памяти на узел и был проанализирован на предмет полных графов взаимодействия. Этот протокол работает следующим образом. Пусть каждый узел $i\; \{\backslash \; displaystyle\; i\}$инициализирует свое состояние памяти своим начальным битом доверия $b\; i\; \in \; \{0,\; 1\}.\; \{\backslash \; displaystyle\; b\_\; \{i\}\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}.\}$В каждый момент времени, когда два узла обмениваются данными, они обновляют свое состояние в соответствии со следующей таблицей. Метки строк показывают состояние инициатора, а столбец - состояние респондента.

Например, если узел с убеждением $0\; \{\backslash \; displaystyle\; 0\}$соответствует узлу с убеждением $0\; \{\backslash \; displaystyle\; 0\}$, тогда оба узла сохраняют свою веру; обновление аналогично, если оба убеждения равны $1\; \{\backslash \; displaystyle\; 1\}$или оба равны $?\; \{\backslash \; displaystyle?\}$. Однако, если мнение инициатора равно $0\; \{\backslash \; displaystyle\; 0\}$, а мнение респондента $?\; \{\backslash \; displaystyle?\}$, тогда респондент изменяет свое мнение на $0\; \{\backslash \; displaystyle\; 0\}$. Если, с другой стороны, у инициатора есть убеждение $0\; \{\backslash \; displaystyle\; 0\}$, а у респондента есть убеждение $1\; \{\backslash \; displaystyle\; 1\}$, то отвечающий изменяет свое вера в $?\; \{\backslash \; displaystyle?\}$. Обратите внимание, что этот протокол односторонний: каждое взаимодействие изменяет самое большее состояние респондента; таким образом, это может быть реализовано с односторонней связью.

Angluin, Aspnes и Eisenstat показали, что из любой начальной конфигурации, которая не состоит из всех "$?\; \{\backslash \; Displaystyle?\}$", приблизительное большинство из трех состояний протокол сходится либо ко всем узлам, имеющим убеждение $0\; \{\backslash \; displaystyle\; 0\}$, либо ко всем узлам, имеющим убеждение $1\; \{\backslash \; displaystyle\; 1\}$в пределах $O\; (n\; \cdot \; журнал\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; cdot\; \backslash \; log\; n)\}$взаимодействий с высокой вероятностью. Кроме того, выбранное значение будет не- "$?\; \{\backslash \; Displaystyle?\}$" начальным значением большинства, при условии, что оно превышает меньшинство с достаточным запасом.

На следующем рисунке показано развитие протокола с тремя состояниями в наборе из $n\; =\; 500\; \{\backslash \; displaystyle\; n\; =\; 500\}$узлов, где одна треть узлов имеет начальные бит доверия $0\; \{\backslash \; displaystyle\; 0\}$, в то время как оставшиеся две трети имеют начальный бит доверия $1\; \{\backslash \; displaystyle\; 1\}$. Доля узлов «$?\; \{\backslash \; Displaystyle?\}$» (отмечена оранжевым) начинается с нуля, некоторое время увеличивается, а затем снова возвращается к нулю.

.

Протоколы популяции были представлены Dana Angluin et al. как одна из первых моделей вычислений, которая должна быть полностью децентрализована и задействовать агентов с сильно ограниченными ресурсами, например, тех, которые встречаются в сенсорных сетях. С тех пор эта абстрактная модель вычислений нашла применение в робототехнике и химии.

Swarm Intelligence

1. ^Alistarh, Dan; Аспнес, Джеймс; Эйзенстат, Дэвид; Гелашвили, Рати; Ривест, Рональд Л. (2017-01-16). "Компромисс между пространством и временем в протоколах заполнения". Сода 17 года. Общество промышленной и прикладной математики: 2560–2579. arXiv : 1602.08032. Bibcode : 2016arXiv160208032A. Cite journal требует | journal =()
2. ^ Angluin, Dana; Aspnes, James; Eisenstat, David (2007), «Простой протокол популяции для быстрого и надежного приблизительного большинства», Распределенные вычисления, Лекционные заметки по компьютерным наукам, 4731, Springer Berlin Heidelberg, стр. 20–32, doi : 10.1007 / 978-3-540-75142-7_5, ISBN 9783540751410
3. ^Perron, E.; Vasudevan, D.; Vojnovic, M. (апрель 2009 г. «Использование трех состояний для двоичного консенсуса на полных графах». IEEE INFOCOM 2009 - 28-я конференция по компьютерным коммуникациям. IEEE: 2527–2535. doi : 10.1109 / infcom.2009.5062181. ISBN 9781424435128.
4. ^Дана Англуин, Джеймс Аспнес, Зои Диамади, Майкл Дж. Фишер, Рене Перальта. Вычисления в сетях пассивно мобильных конечных состояний. датчики. Распределенные вычисления, 2006. [1]
5. ^Грегори Дудек, Майкл Дженкин. Вычислительные принципы мобильной робототехники, Глава 10.
6. ^Хо-Лин Чен, Дэвид Доти, Дэвид Соловейчик. Вычисление детерминированных функций с помощью сетей химических реакций. Natural Computing, 2014. [2pting