The exhaustion of shared memory: Stochastic results

Robert S. Maier; René Schott

doi:10.1007/3-540-57155-8_274

The exhaustion of shared memory: Stochastic results

Robert S. Maier, René Schott

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

Abstract

We analyse a model of exhaustion of shared memory. The memory usage of a finite number of dynamic data structures is modelled as a Markov chain, and the asymptotics of the expected time until memory exhaustion are worked out, in the limit when memory availability and memory needs scale proportionately, and are taken to infinity. This stochastic model subsumes the model of colliding stacks previously treated by the authors, and gives rise to difficult mathematical problems. However, analytic results can be obtained in the limit. Our analysis uses a technique of matched asymptotic expansions introduced by Naeh et al. [11]. The technique is applicable to other stochastically modelled discrete algorithms.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides
Publisher	Springer-Verlag
Pages	494-505
Number of pages	12
ISBN (Print)	9783540571551
DOIs	https://doi.org/10.1007/3-540-57155-8_274
State	Published - 1993
Event	3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada Duration: Aug 11 1993 → Aug 13 1993

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	709 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	3rd Workshop on Algorithms and Data Structures, WADS 1993
Country/Territory	Canada
City	Montreal
Period	8/11/93 → 8/13/93

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-57155-8_274

Cite this

Maier, R. S., & Schott, R. (1993). The exhaustion of shared memory: Stochastic results. In F. Dehne, J.-R. Sack, N. Santoro, & S. Whitesides (Eds.), Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings (pp. 494-505). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS). Springer-Verlag. https://doi.org/10.1007/3-540-57155-8_274

The exhaustion of shared memory: Stochastic results. / Maier, Robert S.; Schott, René.
Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Nicola Santoro; Sue Whitesides. Springer-Verlag, 1993. p. 494-505 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Maier, RS & Schott, R 1993, The exhaustion of shared memory: Stochastic results. in F Dehne, J-R Sack, N Santoro & S Whitesides (eds), Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 709 LNCS, Springer-Verlag, pp. 494-505, 3rd Workshop on Algorithms and Data Structures, WADS 1993, Montreal, Canada, 8/11/93. https://doi.org/10.1007/3-540-57155-8_274

Maier RS, Schott R. The exhaustion of shared memory: Stochastic results. In Dehne F, Sack JR, Santoro N, Whitesides S, editors, Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Springer-Verlag. 1993. p. 494-505. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-57155-8_274

Maier, Robert S. ; Schott, René. / The exhaustion of shared memory : Stochastic results. Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Nicola Santoro ; Sue Whitesides. Springer-Verlag, 1993. pp. 494-505 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{78724650395746d5b71e9738715dff04,

title = "The exhaustion of shared memory: Stochastic results",

abstract = "We analyse a model of exhaustion of shared memory. The memory usage of a finite number of dynamic data structures is modelled as a Markov chain, and the asymptotics of the expected time until memory exhaustion are worked out, in the limit when memory availability and memory needs scale proportionately, and are taken to infinity. This stochastic model subsumes the model of colliding stacks previously treated by the authors, and gives rise to difficult mathematical problems. However, analytic results can be obtained in the limit. Our analysis uses a technique of matched asymptotic expansions introduced by Naeh et al. [11]. The technique is applicable to other stochastically modelled discrete algorithms.",

author = "Maier, {Robert S.} and Ren{\'e} Schott",

year = "1993",

doi = "10.1007/3-540-57155-8_274",

language = "English (US)",

isbn = "9783540571551",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "494--505",

editor = "Frank Dehne and Jorg-Rudiger Sack and Nicola Santoro and Sue Whitesides",

booktitle = "Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings",

}

TY - GEN

T1 - The exhaustion of shared memory

T2 - 3rd Workshop on Algorithms and Data Structures, WADS 1993

AU - Maier, Robert S.

AU - Schott, René

PY - 1993

Y1 - 1993

N2 - We analyse a model of exhaustion of shared memory. The memory usage of a finite number of dynamic data structures is modelled as a Markov chain, and the asymptotics of the expected time until memory exhaustion are worked out, in the limit when memory availability and memory needs scale proportionately, and are taken to infinity. This stochastic model subsumes the model of colliding stacks previously treated by the authors, and gives rise to difficult mathematical problems. However, analytic results can be obtained in the limit. Our analysis uses a technique of matched asymptotic expansions introduced by Naeh et al. [11]. The technique is applicable to other stochastically modelled discrete algorithms.

AB - We analyse a model of exhaustion of shared memory. The memory usage of a finite number of dynamic data structures is modelled as a Markov chain, and the asymptotics of the expected time until memory exhaustion are worked out, in the limit when memory availability and memory needs scale proportionately, and are taken to infinity. This stochastic model subsumes the model of colliding stacks previously treated by the authors, and gives rise to difficult mathematical problems. However, analytic results can be obtained in the limit. Our analysis uses a technique of matched asymptotic expansions introduced by Naeh et al. [11]. The technique is applicable to other stochastically modelled discrete algorithms.

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

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

U2 - 10.1007/3-540-57155-8_274

DO - 10.1007/3-540-57155-8_274

M3 - Conference contribution

AN - SCOPUS:84916567812

SN - 9783540571551

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 494

EP - 505

BT - Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Santoro, Nicola

A2 - Whitesides, Sue

PB - Springer-Verlag

Y2 - 11 August 1993 through 13 August 1993

ER -

The exhaustion of shared memory: Stochastic results

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this