Probabilistic Analysis of Some Distributed Algorithms
Identifieur interne : 00DC77 ( Main/Exploration ); précédent : 00DC76; suivant : 00DC78Probabilistic 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.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 000843
- to stream Crin, to step Curation: 000843
- to stream Crin, to step Checkpoint: 003C22
- to stream Main, to step Merge: 00E557
- to stream Main, to step Curation: 00DC77
Le 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>
<idno type="wicri:Area/Crin/Curation">000843</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">000843</idno>
<idno type="wicri:Area/Crin/Checkpoint">003C22</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">003C22</idno>
<idno type="wicri:Area/Main/Merge">00E557</idno>
<idno type="wicri:Area/Main/Curation">00DC77</idno>
<idno type="wicri:Area/Main/Exploration">00DC77</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>
<affiliations><list></list>
<tree><noCountry><name sortKey="Louchard, G" sort="Louchard, G" uniqKey="Louchard G" first="G." last="Louchard">G. Louchard</name>
<name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name>
</noCountry>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00DC77 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00DC77 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= CRIN:louchard90a |texte= Probabilistic Analysis of Some Distributed Algorithms }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |