Using tractable and realistic churn models to analyze quiescence behavior of distributed protocols

Steven Y. Ko, Imranul Hoque, Indranil Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Large-scale distributed systems are subject to churn, i.e., continuous arrival, departure and failure of processes. Analysis of protocols under churn requires one to use churn models that are tractable (easy to apply), realistic (apply to deployment settings), and general (apply to many protocols and properties). In this paper, we propose two new churn models - called train and crowd - that together achieve these goals, for a broad class of stability properties called quiescent properties, and for arbitrary distributed protocols. We show (i) how analysis of protocol quiescence in the train model can be extended to the crowd model, (ii) how to apply the train and crowd model to several distributed membership protocols, (iii) how, even under real churn traces, the train and crowd models are reasonably good at predicting system-wide stability metrics for membership protocols.

Original languageEnglish (US)
Title of host publicationProceedings of the 27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008
Pages259-268
Number of pages10
DOIs
StatePublished - Dec 1 2008
Event27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008 - Napoli, Italy
Duration: Oct 6 2008Oct 8 2008

Publication series

NameProceedings of the IEEE Symposium on Reliable Distributed Systems
ISSN (Print)1060-9857

Other

Other27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008
CountryItaly
CityNapoli
Period10/6/0810/8/08

Fingerprint

Distributed Protocol
Model
Large-scale Systems
Distributed Systems
Trace
Metric
Arbitrary

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Ko, S. Y., Hoque, I., & Gupta, I. (2008). Using tractable and realistic churn models to analyze quiescence behavior of distributed protocols. In Proceedings of the 27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008 (pp. 259-268). [4690820] (Proceedings of the IEEE Symposium on Reliable Distributed Systems). https://doi.org/10.1109/SRDS.2008.19

Using tractable and realistic churn models to analyze quiescence behavior of distributed protocols. / Ko, Steven Y.; Hoque, Imranul; Gupta, Indranil.

Proceedings of the 27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008. 2008. p. 259-268 4690820 (Proceedings of the IEEE Symposium on Reliable Distributed Systems).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Ko, SY, Hoque, I & Gupta, I 2008, Using tractable and realistic churn models to analyze quiescence behavior of distributed protocols. in Proceedings of the 27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008., 4690820, Proceedings of the IEEE Symposium on Reliable Distributed Systems, pp. 259-268, 27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008, Napoli, Italy, 10/6/08. https://doi.org/10.1109/SRDS.2008.19
Ko SY, Hoque I, Gupta I. Using tractable and realistic churn models to analyze quiescence behavior of distributed protocols. In Proceedings of the 27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008. 2008. p. 259-268. 4690820. (Proceedings of the IEEE Symposium on Reliable Distributed Systems). https://doi.org/10.1109/SRDS.2008.19
Ko, Steven Y. ; Hoque, Imranul ; Gupta, Indranil. / Using tractable and realistic churn models to analyze quiescence behavior of distributed protocols. Proceedings of the 27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008. 2008. pp. 259-268 (Proceedings of the IEEE Symposium on Reliable Distributed Systems).
@inproceedings{45e4a7532f84406aa083c5f273cf5406,
title = "Using tractable and realistic churn models to analyze quiescence behavior of distributed protocols",
abstract = "Large-scale distributed systems are subject to churn, i.e., continuous arrival, departure and failure of processes. Analysis of protocols under churn requires one to use churn models that are tractable (easy to apply), realistic (apply to deployment settings), and general (apply to many protocols and properties). In this paper, we propose two new churn models - called train and crowd - that together achieve these goals, for a broad class of stability properties called quiescent properties, and for arbitrary distributed protocols. We show (i) how analysis of protocol quiescence in the train model can be extended to the crowd model, (ii) how to apply the train and crowd model to several distributed membership protocols, (iii) how, even under real churn traces, the train and crowd models are reasonably good at predicting system-wide stability metrics for membership protocols.",
author = "Ko, {Steven Y.} and Imranul Hoque and Indranil Gupta",
year = "2008",
month = "12",
day = "1",
doi = "10.1109/SRDS.2008.19",
language = "English (US)",
isbn = "9780769534107",
series = "Proceedings of the IEEE Symposium on Reliable Distributed Systems",
pages = "259--268",
booktitle = "Proceedings of the 27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008",

}

TY - GEN

T1 - Using tractable and realistic churn models to analyze quiescence behavior of distributed protocols

AU - Ko, Steven Y.

AU - Hoque, Imranul

AU - Gupta, Indranil

PY - 2008/12/1

Y1 - 2008/12/1

N2 - Large-scale distributed systems are subject to churn, i.e., continuous arrival, departure and failure of processes. Analysis of protocols under churn requires one to use churn models that are tractable (easy to apply), realistic (apply to deployment settings), and general (apply to many protocols and properties). In this paper, we propose two new churn models - called train and crowd - that together achieve these goals, for a broad class of stability properties called quiescent properties, and for arbitrary distributed protocols. We show (i) how analysis of protocol quiescence in the train model can be extended to the crowd model, (ii) how to apply the train and crowd model to several distributed membership protocols, (iii) how, even under real churn traces, the train and crowd models are reasonably good at predicting system-wide stability metrics for membership protocols.

AB - Large-scale distributed systems are subject to churn, i.e., continuous arrival, departure and failure of processes. Analysis of protocols under churn requires one to use churn models that are tractable (easy to apply), realistic (apply to deployment settings), and general (apply to many protocols and properties). In this paper, we propose two new churn models - called train and crowd - that together achieve these goals, for a broad class of stability properties called quiescent properties, and for arbitrary distributed protocols. We show (i) how analysis of protocol quiescence in the train model can be extended to the crowd model, (ii) how to apply the train and crowd model to several distributed membership protocols, (iii) how, even under real churn traces, the train and crowd models are reasonably good at predicting system-wide stability metrics for membership protocols.

UR - http://www.scopus.com/inward/record.url?scp=58149092776&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58149092776&partnerID=8YFLogxK

U2 - 10.1109/SRDS.2008.19

DO - 10.1109/SRDS.2008.19

M3 - Conference contribution

AN - SCOPUS:58149092776

SN - 9780769534107

T3 - Proceedings of the IEEE Symposium on Reliable Distributed Systems

SP - 259

EP - 268

BT - Proceedings of the 27th IEEE International Symposium on Reliable Distributed Systems, SRDS 2008

ER -