View in EDS

Fighting fire with fire: using randomized gossip to combat stochastic scalability limits.

Saved in:

Bibliographic Details
Title:	Fighting fire with fire: using randomized gossip to combat stochastic scalability limits.
Authors:	Gupta, Indranil¹, Birman, Kenneth P.¹ ken@cs.cornell.edu, Van Renesse, Robbert¹
Source:	Quality & Reliability Engineering International. May2002, Vol. 18 Issue 3, p165-184. 20p. 5 Diagrams, 2 Charts, 10 Graphs.
Subjects:	Computer networks, Scalability, Reliability in engineering, Distributed computing, Multicasting (Computer networks), Systems engineering
Abstract:	The mechanisms used to improve the reliability of distributed systems often limit performance and scalability. Focusing on one widely-used definition of reliability, we explore the origins of this phenomenon and conclude that it reflects a tradeoff arising deep within the typical protocol stack. Specifically, we suggest that protocol designs often disregard the high cost of infrequent events. When a distributed system is scaled, both the frequency and the overall cost of such events often grow with the size of the system. This triggers an O($n^{2}$) phenomenon, which becomes visible above some threshold sizes. Our findings suggest that it would be more effective to construct large-scale reliable systems where, unlike traditional protocol stacks, lower layers use randomized mechanisms, with probabilistic guarantees, to overcome low-probability events. Reliability and other end-to-end properties are introduced closer to the application. We employ a back-of-the-envelope analysis to quantify this phenomenon for a class of strongly reliable multicast problems. We construct a non-traditional stack, as described above, that implements virtually synchronous multicast. Experimental results reveal that virtual synchrony over a non-traditional, probabilistic stack helps break through the scalability barrier faced by traditional implementations of the protocol. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
	Copyright of Quality & Reliability Engineering International is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

FullText	Text: Availability: 0
Header	DbId: egs DbLabel: Engineering Source An: 13381473 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0
IllustrationInfo
Items	– Name: Title Label: Title Group: Ti Data: Fighting fire with fire: using randomized gossip to combat stochastic scalability limits. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Gupta%2C+Indranil%22">Gupta, Indranil</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Birman%2C+Kenneth+P%2E%22">Birman, Kenneth P.</searchLink><relatesTo>1</relatesTo><i> ken@cs.cornell.edu</i><br /><searchLink fieldCode="AR" term="%22Van+Renesse%2C+Robbert%22">Van Renesse, Robbert</searchLink><relatesTo>1</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Quality+%26+Reliability+Engineering+International%22">Quality & Reliability Engineering International</searchLink>. May2002, Vol. 18 Issue 3, p165-184. 20p. 5 Diagrams, 2 Charts, 10 Graphs. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Computer+networks%22">Computer networks</searchLink><br /><searchLink fieldCode="DE" term="%22Scalability%22">Scalability</searchLink><br /><searchLink fieldCode="DE" term="%22Reliability+in+engineering%22">Reliability in engineering</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed+computing%22">Distributed computing</searchLink><br /><searchLink fieldCode="DE" term="%22Multicasting+%28Computer+networks%29%22">Multicasting (Computer networks)</searchLink><br /><searchLink fieldCode="DE" term="%22Systems+engineering%22">Systems engineering</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: The mechanisms used to improve the reliability of distributed systems often limit performance and scalability. Focusing on one widely-used definition of reliability, we explore the origins of this phenomenon and conclude that it reflects a tradeoff arising deep within the typical protocol stack. Specifically, we suggest that protocol designs often disregard the high cost of infrequent events. When a distributed system is scaled, both the frequency and the overall cost of such events often grow with the size of the system. This triggers an O(<UEQN>$n^{2}$</UEQN>) phenomenon, which becomes visible above some threshold sizes. Our findings suggest that it would be more effective to construct large-scale reliable systems where, unlike traditional protocol stacks, lower layers use randomized mechanisms, with probabilistic guarantees, to overcome low-probability events. Reliability and other end-to-end properties are introduced closer to the application. We employ a back-of-the-envelope analysis to quantify this phenomenon for a class of strongly reliable multicast problems. We construct a non-traditional stack, as described above, that implements virtually synchronous multicast. Experimental results reveal that virtual synchrony over a non-traditional, probabilistic stack helps break through the scalability barrier faced by traditional implementations of the protocol. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Quality & Reliability Engineering International is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink	https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=13381473
RecordInfo	BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1002/qre.473 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 20 StartPage: 165 Subjects: – SubjectFull: Computer networks Type: general – SubjectFull: Scalability Type: general – SubjectFull: Reliability in engineering Type: general – SubjectFull: Distributed computing Type: general – SubjectFull: Multicasting (Computer networks) Type: general – SubjectFull: Systems engineering Type: general Titles: – TitleFull: Fighting fire with fire: using randomized gossip to combat stochastic scalability limits. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Gupta, Indranil – PersonEntity: Name: NameFull: Birman, Kenneth P. – PersonEntity: Name: NameFull: Van Renesse, Robbert IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 05 Text: May2002 Type: published Y: 2002 Identifiers: – Type: issn-print Value: 07488017 Numbering: – Type: volume Value: 18 – Type: issue Value: 3 Titles: – TitleFull: Quality & Reliability Engineering International Type: main
ResultId	1