z-logo
Premium
Distributed algorithms with dynamical random transitions
Author(s) -
GuillotinPlantard Nadine,
Schott René
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10060
Subject(s) - torus , multivariate random variable , random walk , sequence (biology) , space (punctuation) , random variable , combinatorics , mathematics , transformation (genetics) , discrete mathematics , algorithm , computer science , geometry , statistics , biochemistry , chemistry , biology , gene , genetics , operating system
We analyze a model of exhaustion of shared resources where allocation and deallocation requests are modeled by dynamical random variables as follows: Let ( E, , μ, T ) be a dynamical system where( E , , μ) is a probability space and T is a transformation defined on E. Let d ≥ 1 and f 1 , … , f d be functions defined on E with values in [0, \documentclass{article}\pagestyle{empty}\begin{document}${1\over d}$\end{document} ]. Let ( X i ) i≥1 be a sequence of independent random vectors with values in ℤ d . Let x ∈ E and (e j ) 1≤j≤d be the unit coordinate vectors of ℤ d . For every i ≥ 1, the law of the random vector X i is given by\documentclass{article}\usepackage{amsfonts,amsmath}\pagestyle{empty}\begin{document}$$\mathbb{P}(X_i = z) = \begin{cases} f_j(T^ix)& \text{if $z = e_j$,}\\ {1\over d} - f_j(T^ix)& \text{if $z = - e_j$,}\\ 0& \text{otherwise.}\end{cases}$$\end{document} We write\documentclass{article}\pagestyle{empty}\begin{document}$$S_0 = 0, \quad S_n = \sum_{i=1}^n X_i\quad \mathrm{for}\;\; n \geq 1$$\end{document} for the ℤ d ‐random walk generated by the family ( X i ) i ≥1 . When T is a rotation on the torus then explicit calculations are possible. This stochastic model is a (small) step towards the analysis of distributed algorithms when allocation and deallocation requests are time dependent. It subsumes the models of colliding stacks and of exhaustion of shared memory considered in the literature [14, 15, 11, 16, 17, 20] The technique is applicable to other stochastically modeled resource allocation protocols such as option pricing in financial markets and dam management problems. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 371–396, 2002

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here