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

Box plots for the rendezvous time on lattice networks showing the interquartile range, median value, and outliers.It can be observed that the rendezvous times between the buffered and uniform gossip algorithms fall within relatively the same range. This suggests that overall performance is similar among the tested solutions.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0112612-g008: Box plots for the rendezvous time on lattice networks showing the interquartile range, median value, and outliers.It can be observed that the rendezvous times between the buffered and uniform gossip algorithms fall within relatively the same range. This suggests that overall performance is similar among the tested solutions.

Mentions: Figure 8 visualizes our experimental data from 300 randomly generated lattice networks using a standard box plot. The x-axis indicates the state update protocol used by each algorithm. The y-axis indicates the number of steps until consensus is achieved. The y-axis has been transformed logarithmically in order to improve the overall visualization of the data; the data itself has not been transformed. We observe that the uniform gossip algorithm has the lowest median rendezvous time and smallest third quartile. We also observe that the total performance range (including outliers) is similar between a buffered gossip algorithm using maximum frequency selection, a buffered gossip algorithm using proportional selection and the uniform gossip algorithm; although the median value and third quartile of a buffered gossip algorithm using maximum frequency selection is less than the median value and third quartile of the proportional data. These observations suggest that when agents communicate through lattice random networks, the uniform gossip algorithm should produce lower rendezvous times in comparison to a buffered gossip algorithm using maximum frequency selection or proportional selection, but it would not be uncommon for all three algorithms to produce similar results.


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

Hollander CD, Wu AS - PLoS ONE (2014)

Box plots for the rendezvous time on lattice networks showing the interquartile range, median value, and outliers.It can be observed that the rendezvous times between the buffered and uniform gossip algorithms fall within relatively the same range. This suggests that overall performance is similar among the tested solutions.
© Copyright Policy
Related In: Results  -  Collection

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

pone-0112612-g008: Box plots for the rendezvous time on lattice networks showing the interquartile range, median value, and outliers.It can be observed that the rendezvous times between the buffered and uniform gossip algorithms fall within relatively the same range. This suggests that overall performance is similar among the tested solutions.
Mentions: Figure 8 visualizes our experimental data from 300 randomly generated lattice networks using a standard box plot. The x-axis indicates the state update protocol used by each algorithm. The y-axis indicates the number of steps until consensus is achieved. The y-axis has been transformed logarithmically in order to improve the overall visualization of the data; the data itself has not been transformed. We observe that the uniform gossip algorithm has the lowest median rendezvous time and smallest third quartile. We also observe that the total performance range (including outliers) is similar between a buffered gossip algorithm using maximum frequency selection, a buffered gossip algorithm using proportional selection and the uniform gossip algorithm; although the median value and third quartile of a buffered gossip algorithm using maximum frequency selection is less than the median value and third quartile of the proportional data. These observations suggest that when agents communicate through lattice random networks, the uniform gossip algorithm should produce lower rendezvous times in comparison to a buffered gossip algorithm using maximum frequency selection or proportional selection, but it would not be uncommon for all three algorithms to produce similar results.

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