On the Impact of Modelling Choices for Distributed Information Spread

Rena Bakhshi, Ansgar Fehnker

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

Abstract

We consider a distributed shuf¿ing algorithm for sharing data in a distributed network. Nodes executing the algorithm periodically contact each other and exchange data. The behavior of the algorithm is probabilistic in nature; a node chooses a random peer and sends a random subset of its local data. Moreover, the algorithm exhibits nondeterministic behavior; the order in which nodes initiate an exchange is not speci¿ed. For the shuf¿ing algorithm we build several formal models using the probabilistic model checker PRISM. Despite of the well known state-space explosion problem, we were able to model a network of up to 15 nodes. In addition, we implement two equational models in MATLAB, a discrete model and its continuous alternative, as well as the algorithm itself in the peer-to-peer network simulator PeerSim. By comparing different modelling frameworks, we further explore the impact of modelling choices, such as different scheduling policies and the notion of rounds. The evaluation of distributed protocols, especially gossiping protocols, is dif¿cult and a comparison of different evaluation techniques is greatly desired, since the evaluation techniques vary a lot and are based on different assumptions. The comparison of different models allowed us to discover hidden assumptions, which helps with the interpretation of the obtained results.
Original languageEnglish
Title of host publicationQEST 2009, Sixth International Conference on the Quantitative Evaluation of Systems, Budapest, Hungary, 13-16 September 2009
PublisherIEEE Computer Society
Pages41-50
Number of pages10
ISBN (Print)978-0-7695-3808-2
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event6th International Conference on Quantitative Evaluation of SysTems, QEST 2009 - Technical University of Budapest, Budapest, Hungary
Duration: 13 Sep 200916 Sep 2009
Conference number: 6
http://www.qest.org/qest2009/

Conference

Conference6th International Conference on Quantitative Evaluation of SysTems, QEST 2009
Abbreviated titleQEST
CountryHungary
CityBudapest
Period13/09/0916/09/09
Internet address

Fingerprint

Network protocols
Peer to peer networks
Electronic data interchange
Set theory
Parallel algorithms
MATLAB
Explosions
Simulators
Scheduling
Statistical Models

Cite this

Bakhshi, R., & Fehnker, A. (2009). On the Impact of Modelling Choices for Distributed Information Spread. In QEST 2009, Sixth International Conference on the Quantitative Evaluation of Systems, Budapest, Hungary, 13-16 September 2009 (pp. 41-50). IEEE Computer Society. https://doi.org/10.1109/QEST.2009.37
Bakhshi, Rena ; Fehnker, Ansgar. / On the Impact of Modelling Choices for Distributed Information Spread. QEST 2009, Sixth International Conference on the Quantitative Evaluation of Systems, Budapest, Hungary, 13-16 September 2009. IEEE Computer Society, 2009. pp. 41-50
@inproceedings{f0a40d7e264a426a992b5118b227c4b7,
title = "On the Impact of Modelling Choices for Distributed Information Spread",
abstract = "We consider a distributed shuf¿ing algorithm for sharing data in a distributed network. Nodes executing the algorithm periodically contact each other and exchange data. The behavior of the algorithm is probabilistic in nature; a node chooses a random peer and sends a random subset of its local data. Moreover, the algorithm exhibits nondeterministic behavior; the order in which nodes initiate an exchange is not speci¿ed. For the shuf¿ing algorithm we build several formal models using the probabilistic model checker PRISM. Despite of the well known state-space explosion problem, we were able to model a network of up to 15 nodes. In addition, we implement two equational models in MATLAB, a discrete model and its continuous alternative, as well as the algorithm itself in the peer-to-peer network simulator PeerSim. By comparing different modelling frameworks, we further explore the impact of modelling choices, such as different scheduling policies and the notion of rounds. The evaluation of distributed protocols, especially gossiping protocols, is dif¿cult and a comparison of different evaluation techniques is greatly desired, since the evaluation techniques vary a lot and are based on different assumptions. The comparison of different models allowed us to discover hidden assumptions, which helps with the interpretation of the obtained results.",
author = "Rena Bakhshi and Ansgar Fehnker",
year = "2009",
doi = "10.1109/QEST.2009.37",
language = "English",
isbn = "978-0-7695-3808-2",
pages = "41--50",
booktitle = "QEST 2009, Sixth International Conference on the Quantitative Evaluation of Systems, Budapest, Hungary, 13-16 September 2009",
publisher = "IEEE Computer Society",
address = "United States",

}

Bakhshi, R & Fehnker, A 2009, On the Impact of Modelling Choices for Distributed Information Spread. in QEST 2009, Sixth International Conference on the Quantitative Evaluation of Systems, Budapest, Hungary, 13-16 September 2009. IEEE Computer Society, pp. 41-50, 6th International Conference on Quantitative Evaluation of SysTems, QEST 2009, Budapest, Hungary, 13/09/09. https://doi.org/10.1109/QEST.2009.37

On the Impact of Modelling Choices for Distributed Information Spread. / Bakhshi, Rena; Fehnker, Ansgar.

QEST 2009, Sixth International Conference on the Quantitative Evaluation of Systems, Budapest, Hungary, 13-16 September 2009. IEEE Computer Society, 2009. p. 41-50.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - On the Impact of Modelling Choices for Distributed Information Spread

AU - Bakhshi, Rena

AU - Fehnker, Ansgar

PY - 2009

Y1 - 2009

N2 - We consider a distributed shuf¿ing algorithm for sharing data in a distributed network. Nodes executing the algorithm periodically contact each other and exchange data. The behavior of the algorithm is probabilistic in nature; a node chooses a random peer and sends a random subset of its local data. Moreover, the algorithm exhibits nondeterministic behavior; the order in which nodes initiate an exchange is not speci¿ed. For the shuf¿ing algorithm we build several formal models using the probabilistic model checker PRISM. Despite of the well known state-space explosion problem, we were able to model a network of up to 15 nodes. In addition, we implement two equational models in MATLAB, a discrete model and its continuous alternative, as well as the algorithm itself in the peer-to-peer network simulator PeerSim. By comparing different modelling frameworks, we further explore the impact of modelling choices, such as different scheduling policies and the notion of rounds. The evaluation of distributed protocols, especially gossiping protocols, is dif¿cult and a comparison of different evaluation techniques is greatly desired, since the evaluation techniques vary a lot and are based on different assumptions. The comparison of different models allowed us to discover hidden assumptions, which helps with the interpretation of the obtained results.

AB - We consider a distributed shuf¿ing algorithm for sharing data in a distributed network. Nodes executing the algorithm periodically contact each other and exchange data. The behavior of the algorithm is probabilistic in nature; a node chooses a random peer and sends a random subset of its local data. Moreover, the algorithm exhibits nondeterministic behavior; the order in which nodes initiate an exchange is not speci¿ed. For the shuf¿ing algorithm we build several formal models using the probabilistic model checker PRISM. Despite of the well known state-space explosion problem, we were able to model a network of up to 15 nodes. In addition, we implement two equational models in MATLAB, a discrete model and its continuous alternative, as well as the algorithm itself in the peer-to-peer network simulator PeerSim. By comparing different modelling frameworks, we further explore the impact of modelling choices, such as different scheduling policies and the notion of rounds. The evaluation of distributed protocols, especially gossiping protocols, is dif¿cult and a comparison of different evaluation techniques is greatly desired, since the evaluation techniques vary a lot and are based on different assumptions. The comparison of different models allowed us to discover hidden assumptions, which helps with the interpretation of the obtained results.

U2 - 10.1109/QEST.2009.37

DO - 10.1109/QEST.2009.37

M3 - Conference contribution

SN - 978-0-7695-3808-2

SP - 41

EP - 50

BT - QEST 2009, Sixth International Conference on the Quantitative Evaluation of Systems, Budapest, Hungary, 13-16 September 2009

PB - IEEE Computer Society

ER -

Bakhshi R, Fehnker A. On the Impact of Modelling Choices for Distributed Information Spread. In QEST 2009, Sixth International Conference on the Quantitative Evaluation of Systems, Budapest, Hungary, 13-16 September 2009. IEEE Computer Society. 2009. p. 41-50 https://doi.org/10.1109/QEST.2009.37