%0 Conference Paper %1 conf/wdag/AngluinAE06 %A Angluin, Dana %A Aspnes, James %A Eisenstat, David %B IN DISTRIBUTED COMPUTING: 20TH INTERNATIONAL SYMPOSIUM, DISC 2006 %D 2006 %E Dolev, Shlomi %I Springer %K distributed populationprotocols %P 61-75 %T Fast computation by population protocols with a leader %U http://www.cs.yale.edu/homes/aspnes/papers/disc2006-journal.pdf %V 4167 %X Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in pairs under the control of an adversary scheduler—where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual register machine in which standard arithmetic operations like comparison, addition, subtraction, multiplication, and division can be simulated in O(n log 4 n) interactions with high probability. Applications include a reduction of the cost of computing a semilinear predicate to O(n log 4 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Turing machine using the same O(n log 4 n) interactions per step. These bounds on interactions translate into O(log 4 n) time per step in a natural model in which each agent participates in an expected Θ(1) interactions per time unit. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete.

@inproceedings{conf/wdag/AngluinAE06, abstract = {Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in pairs under the control of an adversary scheduler—where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual register machine in which standard arithmetic operations like comparison, addition, subtraction, multiplication, and division can be simulated in O(n log 4 n) interactions with high probability. Applications include a reduction of the cost of computing a semilinear predicate to O(n log 4 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Turing machine using the same O(n log 4 n) interactions per step. These bounds on interactions translate into O(log 4 n) time per step in a natural model in which each agent participates in an expected Θ(1) interactions per time unit. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete. }, added-at = {2019-02-01T13:36:02.000+0100}, author = {Angluin, Dana and Aspnes, James and Eisenstat, David}, biburl = {https://www.bibsonomy.org/bibtex/2361e93cd521befab2aac2cacdd182681/paves_intern}, booktitle = {IN DISTRIBUTED COMPUTING: 20TH INTERNATIONAL SYMPOSIUM, DISC 2006}, description = {#leader #population-protocol}, editor = {Dolev, Shlomi}, interhash = {0feb3d551359e0ffc1bf1f05a75f6ad8}, intrahash = {361e93cd521befab2aac2cacdd182681}, keywords = {distributed populationprotocols}, pages = {61-75}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, timestamp = {2019-02-12T15:58:27.000+0100}, title = {Fast computation by population protocols with a leader}, url = {http://www.cs.yale.edu/homes/aspnes/papers/disc2006-journal.pdf}, volume = 4167, year = 2006 }