Probabilistic Analysis of Some Distributed Algorithms
Identifieur interne : 000B53 ( Crin/Curation ); précédent : 000B52; suivant : 000B54Probabilistic Analysis of Some Distributed Algorithms
Auteurs : G. Louchard ; R. SchottSource :
- Random Structures and Algorithms ; 1991.
English descriptors
- KwdEn :
Abstract
In this paper, we analyze\, : (i)a storage allocation algorithm which permits one to maintain two stacks inside a shared (continuous) memory area of a fixed size, and (ii) the well-known banker algorithm which plays a fundamental role in parallel processing. The natural formulation of the problems to be solved here is in terms of random walks. For (i) the random walk Y_{m}(.) takes place in a triangle in a two-dimensional lattice space with two reflecting barriers along the axes (a deletion has no effect on an empty stack) and one absorbing barrier along the diagonal (the algorithm stops when the combined sizes of the stacks exhaust the available storage). For (ii) the random walk takes place in a rectangle with broken corner and has four reflecting barriers and one absorbing varrier. With the help of diffusion techniques, we obtain, asymptotically as m\rightarrow^{x}\, : \begin{itemize} \item[-]the distribution of the hitting place (Z_{m}) and hitting time (T_{m}) on the absorbing boundary, \item[-]the joint distribution of Z_{m} and T_{m}, \item[-]the distribution P(Y_{m}(n) \leq y_{m}, n < T_{m}), \end{itemize} where m is a parameter that measures the size of the triangle or rectangle and represents the storage capacity or amount of available resource. The two stacks problem has been partially investigated by Yao and more recently by Flajolet with different tools. We provide here an analysis of the general case with new limiting distribution. To the best of our knowledge, such an analysis has never been done before for the banker algorithm.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000B53
Links to Exploration step
CRIN:louchard91bLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="260">Probabilistic Analysis of Some Distributed Algorithms</title></titleStmt><publicationStmt><idno type="RBID">CRIN:louchard91b</idno><date when="1991" year="1991">1991</date><idno type="wicri:Area/Crin/Corpus">000B53</idno><idno type="wicri:Area/Crin/Curation">000B53</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">000B53</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Probabilistic Analysis of Some Distributed Algorithms</title><author><name sortKey="Louchard, G" sort="Louchard, G" uniqKey="Louchard G" first="G." last="Louchard">G. Louchard</name></author><author><name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name></author></analytic><series><title level="j">Random Structures and Algorithms</title><imprint><date when="1991" type="published">1991</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>banker algorithm</term><term>diffusion processes</term><term>distributed algorithms</term><term>limiting distributions</term><term>twostacks problem</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="5885">In this paper, we analyze\, : (i)a storage allocation algorithm which permits one to maintain two stacks inside a shared (continuous) memory area of a fixed size, and (ii) the well-known banker algorithm which plays a fundamental role in parallel processing. The natural formulation of the problems to be solved here is in terms of random walks. For (i) the random walk Y_{m}(.) takes place in a triangle in a two-dimensional lattice space with two reflecting barriers along the axes (a deletion has no effect on an empty stack) and one absorbing barrier along the diagonal (the algorithm stops when the combined sizes of the stacks exhaust the available storage). For (ii) the random walk takes place in a rectangle with broken corner and has four reflecting barriers and one absorbing varrier. With the help of diffusion techniques, we obtain, asymptotically as m\rightarrow^{x}\, : \begin{itemize} \item[-]the distribution of the hitting place (Z_{m}) and hitting time (T_{m}) on the absorbing boundary, \item[-]the joint distribution of Z_{m} and T_{m}, \item[-]the distribution P(Y_{m}(n) \leq y_{m}, n < T_{m}), \end{itemize} where m is a parameter that measures the size of the triangle or rectangle and represents the storage capacity or amount of available resource. The two stacks problem has been partially investigated by Yao and more recently by Flajolet with different tools. We provide here an analysis of the general case with new limiting distribution. To the best of our knowledge, such an analysis has never been done before for the banker algorithm.</div></front></TEI><BibTex type="article"><ref>louchard91b</ref><crinnumber>91-R-077</crinnumber><category>1</category><equipe>EURECA</equipe><author><e>Louchard, G.</e><e>Schott, R.</e></author><title>Probabilistic Analysis of Some Distributed Algorithms</title><journal>Random Structures and Algorithms</journal><year>1991</year><volume>2</volume><number>2</number><pages>151-186</pages><keywords><e>distributed algorithms</e><e>diffusion processes</e><e>twostacks problem</e><e>banker algorithm</e><e>limiting distributions</e></keywords><abstract>In this paper, we analyze\, : (i)a storage allocation algorithm which permits one to maintain two stacks inside a shared (continuous) memory area of a fixed size, and (ii) the well-known banker algorithm which plays a fundamental role in parallel processing. The natural formulation of the problems to be solved here is in terms of random walks. For (i) the random walk Y_{m}(.) takes place in a triangle in a two-dimensional lattice space with two reflecting barriers along the axes (a deletion has no effect on an empty stack) and one absorbing barrier along the diagonal (the algorithm stops when the combined sizes of the stacks exhaust the available storage). For (ii) the random walk takes place in a rectangle with broken corner and has four reflecting barriers and one absorbing varrier. With the help of diffusion techniques, we obtain, asymptotically as m\rightarrow^{x}\, : \begin{itemize} \item[-]the distribution of the hitting place (Z_{m}) and hitting time (T_{m}) on the absorbing boundary, \item[-]the joint distribution of Z_{m} and T_{m}, \item[-]the distribution P(Y_{m}(n) \leq y_{m}, n < T_{m}), \end{itemize} where m is a parameter that measures the size of the triangle or rectangle and represents the storage capacity or amount of available resource. The two stacks problem has been partially investigated by Yao and more recently by Flajolet with different tools. We provide here an analysis of the general case with new limiting distribution. To the best of our knowledge, such an analysis has never been done before for the banker algorithm.</abstract></BibTex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000B53 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Curation/biblio.hfd -nk 000B53 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Crin
|étape= Curation
|type= RBID
|clé= CRIN:louchard91b
|texte= Probabilistic Analysis of Some Distributed Algorithms
}}
| This area was generated with Dilib version V0.6.33. |  |