Probabilistic Analysis of Some Distributed Algorithms
Identifieur interne : 000843 ( Crin/Corpus ); précédent : 000842; suivant : 000844Probabilistic Analysis of Some Distributed Algorithms
Auteurs : G. Louchard ; R. SchottSource :
English descriptors
- KwdEn :
Abstract
In this paper, we analyse\, : \begin{enumerate} \item a storage allocation algorithm which permits to maintain two stacks inside a shared (contiguous) memory area of a fixed size, \item the well-known banker algorithm which plays a fundamental role in parallel processing. \end{enumerate} The natural formulation of the problems to be solved here is in terms of random walks. For (1) the random walk Y_{m}(.) takes place in a triangle in a 2-dimensional lattice space with two reflecting barriers along the axes (a deletion takes no effect on an empty stack) and one absorbing barrier parallel to the second diagonal (the algorithm stops when the combined sizes of the stacks exhaust the available storage). For (2) the random walk takes place in a rectangle with breaked corner and has four reflecting barriers and one absorbing barrier. With the help of diffusions techniques, we obtain, asymptotically\, : \begin{itemize} \item[-] the hitting place (Z_{m}) and time (T_{m}) distributions on the absorbing boundary, \item[-] the joined distribution of Z_{m} and T_{m}, \item[-] the distribution PY_{m}(n)\leq y_{m}, n f(g(f(x))). Eventually, an attempt to extend the recursive path ordering is proposed.
Links to Exploration step
CRIN:louchard90aLe 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:louchard90a</idno><date when="1990" year="1990">1990</date><idno type="wicri:Area/Crin/Corpus">000843</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></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>banker algorithm</term><term>diffusions</term><term>distributed algorithms</term><term>hitting place and time</term><term>limit distributions</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="4217">In this paper, we analyse\, : \begin{enumerate} \item a storage allocation algorithm which permits to maintain two stacks inside a shared (contiguous) memory area of a fixed size, \item the well-known banker algorithm which plays a fundamental role in parallel processing. \end{enumerate} The natural formulation of the problems to be solved here is in terms of random walks. For (1) the random walk Y_{m}(.) takes place in a triangle in a 2-dimensional lattice space with two reflecting barriers along the axes (a deletion takes no effect on an empty stack) and one absorbing barrier parallel to the second diagonal (the algorithm stops when the combined sizes of the stacks exhaust the available storage). For (2) the random walk takes place in a rectangle with breaked corner and has four reflecting barriers and one absorbing barrier. With the help of diffusions techniques, we obtain, asymptotically\, : \begin{itemize} \item[-] the hitting place (Z_{m}) and time (T_{m}) distributions on the absorbing boundary, \item[-] the joined distribution of Z_{m} and T_{m}, \item[-] the distribution PY_{m}(n)\leq y_{m}, n f(g(f(x))). Eventually, an attempt to extend the recursive path ordering is proposed.</div></front></TEI><BibTex type="inproceedings"><ref>louchard90a</ref><crinnumber>89-R-177</crinnumber><category>3</category><equipe>EURECA</equipe><author><e>Louchard, G.</e><e>Schott, R.</e></author><title>Probabilistic Analysis of Some Distributed Algorithms</title><booktitle>{Proceedings CAALP'90, Copenhagen (Denmark)}</booktitle><year>1990</year><editor>A. Arnold</editor><volume>431</volume><series>Lecture Notes in Computer Science</series><pages>239-253</pages><month>may</month><publisher>Springer Verlag</publisher><keywords><e>distributed algorithms</e><e>diffusions</e><e>hitting place and time</e><e>limit distributions</e><e>banker algorithm</e></keywords><abstract>In this paper, we analyse\, : \begin{enumerate} \item a storage allocation algorithm which permits to maintain two stacks inside a shared (contiguous) memory area of a fixed size, \item the well-known banker algorithm which plays a fundamental role in parallel processing. \end{enumerate} The natural formulation of the problems to be solved here is in terms of random walks. For (1) the random walk Y_{m}(.) takes place in a triangle in a 2-dimensional lattice space with two reflecting barriers along the axes (a deletion takes no effect on an empty stack) and one absorbing barrier parallel to the second diagonal (the algorithm stops when the combined sizes of the stacks exhaust the available storage). For (2) the random walk takes place in a rectangle with breaked corner and has four reflecting barriers and one absorbing barrier. With the help of diffusions techniques, we obtain, asymptotically\, : \begin{itemize} \item[-] the hitting place (Z_{m}) and time (T_{m}) distributions on the absorbing boundary, \item[-] the joined distribution of Z_{m} and T_{m}, \item[-] the distribution PY_{m}(n)\leq y_{m}, n f(g(f(x))). Eventually, an attempt to extend the recursive path ordering is proposed.</abstract></BibTex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000843 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Corpus/biblio.hfd -nk 000843 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Crin
|étape= Corpus
|type= RBID
|clé= CRIN:louchard90a
|texte= Probabilistic Analysis of Some Distributed Algorithms
}}
| This area was generated with Dilib version V0.6.33. |  |