Distributed Algorithms with Dynamical Random Transitions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Random Structures and Algorithms Année : 2002

Distributed Algorithms with Dynamical Random Transitions

Résumé

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 f1, , fd be functions defined on E with values in [0, ]. Let (Xi)i1 be a sequence of independent random vectors with values in d. Let x E and (ej)1jd be the unit coordinate vectors of d. For every i 1, the law of the random vector Xi is given by We write for the d-random walk generated by the family (Xi)i1. 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.

Dates et versions

inria-00000270 , version 1 (21-09-2005)

Identifiants

Citer

Nadine Guillotin-Plantard, René Schott. Distributed Algorithms with Dynamical Random Transitions. Random Structures and Algorithms, 2002, 21 (3-4), pp.371-396. ⟨10.1002/rsa.20091⟩. ⟨inria-00000270⟩
28 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More