Mean-field framework for performance evaluation of push–pull gossip protocols

Rena Bakhshi, L. Cloth, Wan Fokkink, Boudewijn R.H.M. Haverkort

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Gossip protocols are designed to operate in very large, decentralised networks. A node in such a network bases its decision to interact (gossip) with another node on its partial view of the global system. Because of the size of these networks, analysis of gossip protocols is mostly done using simulations, but these tend to be expensive in computation time and memory consumption. We employ mean-field analysis techniques for the evaluation of gossip protocols. Nodes in the network are represented by small identical stochastic processes. Joining all nodes would result in an enormous stochastic process. If the number of nodes goes to infinity, however, mean-field analysis allows us to replace this intractably large stochastic process by a small deterministic process. This process approximates the behaviour of very large gossip networks, and can be evaluated using simple matrix-vector multiplications.
Original languageEnglish
Pages (from-to)157-179
Number of pages23
JournalPerformance Evaluation
Volume68
Issue number2
DOIs
Publication statusPublished - Feb 2011
Externally publishedYes

Fingerprint

Gossip
Random processes
Mean Field
Performance Evaluation
Stochastic Processes
Vertex of a graph
Electric network analysis
Joining
Matrix-vector multiplication
Network Analysis
Data storage equipment
Decentralized
Infinity
Framework
Tend
Partial
Evaluation
Simulation

Keywords

  • Quantitative evaluation
  • EWI-21074
  • IR-79138
  • Mean-field approximation
  • METIS-284936
  • Gossip protocols

Cite this

@article{f99161ac104542eda67f5b64e69350e3,
title = "Mean-field framework for performance evaluation of push–pull gossip protocols",
abstract = "Gossip protocols are designed to operate in very large, decentralised networks. A node in such a network bases its decision to interact (gossip) with another node on its partial view of the global system. Because of the size of these networks, analysis of gossip protocols is mostly done using simulations, but these tend to be expensive in computation time and memory consumption. We employ mean-field analysis techniques for the evaluation of gossip protocols. Nodes in the network are represented by small identical stochastic processes. Joining all nodes would result in an enormous stochastic process. If the number of nodes goes to infinity, however, mean-field analysis allows us to replace this intractably large stochastic process by a small deterministic process. This process approximates the behaviour of very large gossip networks, and can be evaluated using simple matrix-vector multiplications.",
keywords = "Quantitative evaluation, EWI-21074, IR-79138, Mean-field approximation, METIS-284936, Gossip protocols",
author = "Rena Bakhshi and L. Cloth and Wan Fokkink and Haverkort, {Boudewijn R.H.M.}",
note = "10.1016/j.peva.2010.08.025",
year = "2011",
month = "2",
doi = "10.1016/j.peva.2010.08.025",
language = "English",
volume = "68",
pages = "157--179",
journal = "Performance Evaluation",
issn = "0166-5316",
publisher = "Elsevier",
number = "2",

}

Mean-field framework for performance evaluation of push–pull gossip protocols. / Bakhshi, Rena; Cloth, L.; Fokkink, Wan; Haverkort, Boudewijn R.H.M.

In: Performance Evaluation, Vol. 68, No. 2, 02.2011, p. 157-179.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Mean-field framework for performance evaluation of push–pull gossip protocols

AU - Bakhshi, Rena

AU - Cloth, L.

AU - Fokkink, Wan

AU - Haverkort, Boudewijn R.H.M.

N1 - 10.1016/j.peva.2010.08.025

PY - 2011/2

Y1 - 2011/2

N2 - Gossip protocols are designed to operate in very large, decentralised networks. A node in such a network bases its decision to interact (gossip) with another node on its partial view of the global system. Because of the size of these networks, analysis of gossip protocols is mostly done using simulations, but these tend to be expensive in computation time and memory consumption. We employ mean-field analysis techniques for the evaluation of gossip protocols. Nodes in the network are represented by small identical stochastic processes. Joining all nodes would result in an enormous stochastic process. If the number of nodes goes to infinity, however, mean-field analysis allows us to replace this intractably large stochastic process by a small deterministic process. This process approximates the behaviour of very large gossip networks, and can be evaluated using simple matrix-vector multiplications.

AB - Gossip protocols are designed to operate in very large, decentralised networks. A node in such a network bases its decision to interact (gossip) with another node on its partial view of the global system. Because of the size of these networks, analysis of gossip protocols is mostly done using simulations, but these tend to be expensive in computation time and memory consumption. We employ mean-field analysis techniques for the evaluation of gossip protocols. Nodes in the network are represented by small identical stochastic processes. Joining all nodes would result in an enormous stochastic process. If the number of nodes goes to infinity, however, mean-field analysis allows us to replace this intractably large stochastic process by a small deterministic process. This process approximates the behaviour of very large gossip networks, and can be evaluated using simple matrix-vector multiplications.

KW - Quantitative evaluation

KW - EWI-21074

KW - IR-79138

KW - Mean-field approximation

KW - METIS-284936

KW - Gossip protocols

U2 - 10.1016/j.peva.2010.08.025

DO - 10.1016/j.peva.2010.08.025

M3 - Article

VL - 68

SP - 157

EP - 179

JO - Performance Evaluation

JF - Performance Evaluation

SN - 0166-5316

IS - 2

ER -