Limits...
Gossip-based solutions for discrete rendezvous in populations of communicating agents.

Hollander CD, Wu AS - PLoS ONE (2014)

Bottom Line: The objective of the rendezvous problem is to construct a method that enables a population of agents to agree on a spatial (and possibly temporal) meeting location.We use these results to verify that the uniform gossip algorithm also solves the rendezvous problem.We then use a multi-agent simulation to conduct a series of simulation experiments to compare the performance between the buffered and uniform gossip algorithms.

View Article: PubMed Central - PubMed

Affiliation: Department of Electrical Engineering and Computer Science, University of Central Florida, Orlando, FL, United States of America.

ABSTRACT
The objective of the rendezvous problem is to construct a method that enables a population of agents to agree on a spatial (and possibly temporal) meeting location. We introduce the buffered gossip algorithm as a general solution to the rendezvous problem in a discrete domain with direct communication between decentralized agents. We compare the performance of the buffered gossip algorithm against the well known uniform gossip algorithm. We believe that a buffered solution is preferable to an unbuffered solution, such as the uniform gossip algorithm, because the use of a buffer allows an agent to use multiple information sources when determining its desired rendezvous point, and that access to multiple information sources may improve agent decision making by reinforcing or contradicting an initial choice. To show that the buffered gossip algorithm is an actual solution for the rendezvous problem, we construct a theoretical proof of convergence and derive the conditions under which the buffered gossip algorithm is guaranteed to produce a consensus on rendezvous location. We use these results to verify that the uniform gossip algorithm also solves the rendezvous problem. We then use a multi-agent simulation to conduct a series of simulation experiments to compare the performance between the buffered and uniform gossip algorithms. Our results suggest that the buffered gossip algorithm can solve the rendezvous problem faster than the uniform gossip algorithm; however, the relative performance between these two solutions depends on the specific constraints of the problem and the parameters of the buffered gossip algorithm.

Show MeSH

Related in: MedlinePlus

Errorbar plots of the 95% confidence intervals for the mean rendezvous time on Erdös-Renyi random networks.It can be observed that a buffered gossip algorithm using maximum frequency selection has a mean rendezvous time less than a buffered gossip algorithm using proportional selection or the uniform gossip algorithm. Furthermore, the mean rendezvous time of a buffered gossip algorithm using proportional selection is not equal to the mean rendezvous time of the uniform gossip algorithm.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4232358&req=5

pone-0112612-g003: Errorbar plots of the 95% confidence intervals for the mean rendezvous time on Erdös-Renyi random networks.It can be observed that a buffered gossip algorithm using maximum frequency selection has a mean rendezvous time less than a buffered gossip algorithm using proportional selection or the uniform gossip algorithm. Furthermore, the mean rendezvous time of a buffered gossip algorithm using proportional selection is not equal to the mean rendezvous time of the uniform gossip algorithm.

Mentions: Figure 3 visualizes the mean rendezvous time of our random network data along with the 95% confidence interval of each mean. The x-axis indicates the state update protocol used by each algorithm. The y-axis indicates the number of steps until consensus is achieved. We test hypotheses (), (), and () in the context of Erdös-Renyi random networks using the data visualized in Figure 3. We reject hypotheses and ( for both). This suggests that there is evidence to support the claim that the mean rendezvous time of a buffered gossip algorithm using maximum frequency selection () is less than the the mean rendezvous time of a buffered gossip algorithm using proportional selection () and less than the mean rendezvous time of the uniform gossip algorithm (). We also reject (), and so there is not evidence to support the claim that the mean rendezvous time of a buffered gossip algorithm using proportional selection () is equal to the the mean rendezvous time of the uniform gossip algorithm (). Instead, the evidence suggests that the mean rendezvous time of the uniform gossip algorithm is less than the mean rendezvous time of a buffered gossip algorithm using proportional selection. The rejection of may suggest that even though randomness is central to proportional selection and the uniform gossip algorithm, there are other factors that we have not yet examined that may influence the length of time required to rendezvous.


Gossip-based solutions for discrete rendezvous in populations of communicating agents.

Hollander CD, Wu AS - PLoS ONE (2014)

Errorbar plots of the 95% confidence intervals for the mean rendezvous time on Erdös-Renyi random networks.It can be observed that a buffered gossip algorithm using maximum frequency selection has a mean rendezvous time less than a buffered gossip algorithm using proportional selection or the uniform gossip algorithm. Furthermore, the mean rendezvous time of a buffered gossip algorithm using proportional selection is not equal to the mean rendezvous time of the uniform gossip algorithm.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4232358&req=5

pone-0112612-g003: Errorbar plots of the 95% confidence intervals for the mean rendezvous time on Erdös-Renyi random networks.It can be observed that a buffered gossip algorithm using maximum frequency selection has a mean rendezvous time less than a buffered gossip algorithm using proportional selection or the uniform gossip algorithm. Furthermore, the mean rendezvous time of a buffered gossip algorithm using proportional selection is not equal to the mean rendezvous time of the uniform gossip algorithm.
Mentions: Figure 3 visualizes the mean rendezvous time of our random network data along with the 95% confidence interval of each mean. The x-axis indicates the state update protocol used by each algorithm. The y-axis indicates the number of steps until consensus is achieved. We test hypotheses (), (), and () in the context of Erdös-Renyi random networks using the data visualized in Figure 3. We reject hypotheses and ( for both). This suggests that there is evidence to support the claim that the mean rendezvous time of a buffered gossip algorithm using maximum frequency selection () is less than the the mean rendezvous time of a buffered gossip algorithm using proportional selection () and less than the mean rendezvous time of the uniform gossip algorithm (). We also reject (), and so there is not evidence to support the claim that the mean rendezvous time of a buffered gossip algorithm using proportional selection () is equal to the the mean rendezvous time of the uniform gossip algorithm (). Instead, the evidence suggests that the mean rendezvous time of the uniform gossip algorithm is less than the mean rendezvous time of a buffered gossip algorithm using proportional selection. The rejection of may suggest that even though randomness is central to proportional selection and the uniform gossip algorithm, there are other factors that we have not yet examined that may influence the length of time required to rendezvous.

Bottom Line: The objective of the rendezvous problem is to construct a method that enables a population of agents to agree on a spatial (and possibly temporal) meeting location.We use these results to verify that the uniform gossip algorithm also solves the rendezvous problem.We then use a multi-agent simulation to conduct a series of simulation experiments to compare the performance between the buffered and uniform gossip algorithms.

View Article: PubMed Central - PubMed

Affiliation: Department of Electrical Engineering and Computer Science, University of Central Florida, Orlando, FL, United States of America.

ABSTRACT
The objective of the rendezvous problem is to construct a method that enables a population of agents to agree on a spatial (and possibly temporal) meeting location. We introduce the buffered gossip algorithm as a general solution to the rendezvous problem in a discrete domain with direct communication between decentralized agents. We compare the performance of the buffered gossip algorithm against the well known uniform gossip algorithm. We believe that a buffered solution is preferable to an unbuffered solution, such as the uniform gossip algorithm, because the use of a buffer allows an agent to use multiple information sources when determining its desired rendezvous point, and that access to multiple information sources may improve agent decision making by reinforcing or contradicting an initial choice. To show that the buffered gossip algorithm is an actual solution for the rendezvous problem, we construct a theoretical proof of convergence and derive the conditions under which the buffered gossip algorithm is guaranteed to produce a consensus on rendezvous location. We use these results to verify that the uniform gossip algorithm also solves the rendezvous problem. We then use a multi-agent simulation to conduct a series of simulation experiments to compare the performance between the buffered and uniform gossip algorithms. Our results suggest that the buffered gossip algorithm can solve the rendezvous problem faster than the uniform gossip algorithm; however, the relative performance between these two solutions depends on the specific constraints of the problem and the parameters of the buffered gossip algorithm.

Show MeSH
Related in: MedlinePlus