Large deviations analysis for distributed algorithms in an ergodic Markovian environment.(English)Zbl 1186.60021
This paper deals with a large deviations analysis of deadlock phenomena occurring in distributed systems sharing common resources. In this model transition probabilities of resource allocation and deallocation are time and space dependent.
The organization of this paper is as follows: the authors discuss probabilistic model in Sect. 2. In Sect. 3 they prove a Large Deviations Principle. Deadlock phenomenon analysis is done rigorously with much details in Sect. 4. Then they illustrate with the two-stacks model and show an example where the system has a stable attractor which is a limit cycle.
The organization of this paper is as follows: the authors discuss probabilistic model in Sect. 2. In Sect. 3 they prove a Large Deviations Principle. Deadlock phenomenon analysis is done rigorously with much details in Sect. 4. Then they illustrate with the two-stacks model and show an example where the system has a stable attractor which is a limit cycle.
Reviewer: Nicko G. Gamkrelidze (Moskva)
Cite
References:
| [1] | Atar, R., Dupuis, P.: Large deviations and queueing networks: methods for rate function identification. Stoch. Process. Appl. 84, 255–296 (1999) ·Zbl 0996.60036 ·doi:10.1016/S0304-4149(99)00051-4 |
| [2] | Azencott, R., Ruget, G.: Mélanges d’équations différentielles et grands écarts à la loi des grands nombres. Z. Wahrscheinlichkeitstheor. Verw. Geb. 38, 1–54 (1977) ·Zbl 0372.60082 ·doi:10.1007/BF00534169 |
| [3] | Azencott, R.: Grandes déviations et applications. In: Eighth Saint Flour Probability Summer School–1978. Lecture Notes in Math., vol. 774, pp. 1–176. Springer, Berlin (1980) |
| [4] | Baldi, P.: Large deviations and stochastic homogenization. Ann. Mat. Pura Appl. 151, 161–177 (1988) ·Zbl 0654.60024 ·doi:10.1007/BF01762793 |
| [5] | Bardi, M., Capuzzo-Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Birkhäuser Boston, Boston (1997) ·Zbl 0890.49011 |
| [6] | Barles, G.: Solutions de viscosité des équations de Hamilton-Jacobi. Springer, Paris (1994) ·Zbl 0819.35002 |
| [7] | Capuzzo-Dolcetta, I., Lions, P.-L.: Hamilton-Jacobi equations with state constraints. Trans. Am. Math. Soc. 318, 643–683 (1990) ·Zbl 0702.49019 ·doi:10.2307/2001324 |
| [8] | Comets, F., Delarue, F., Schott, R.: Distributed algorithms in an ergodic Markovian environment. Random Struct. Algorithms 30, 131–167 (2007) ·Zbl 1178.68663 ·doi:10.1002/rsa.20154 |
| [9] | Dembo, A., Zeitouni, O.: Large Deviations Techniques and Applications, 2nd edn. Applications of Mathematics, vol. 38. Springer, New York (1998) ·Zbl 0896.60013 |
| [10] | Dupuis, P.: Large deviations analysis of reflected diffusions and constrained stochastic approximation algorithms in convex sets. Stochastics 21, 63–96 (1987) ·Zbl 0614.60023 |
| [11] | Dupuis, P.: Large deviations analysis of some recursive algorithms with state dependent noise. Ann. Probab. 16, 1509–1536 (1988) ·Zbl 0661.60045 ·doi:10.1214/aop/1176991581 |
| [12] | Dupuis, P., Ellis, R.S.: The large deviations principle for a general class of queueing systems I. Trans. Am. Math. Soc. 347, 2689–2751 (1995) ·Zbl 0869.60022 ·doi:10.2307/2154753 |
| [13] | Dupuis, P., Ramanan, K.: A time-reversed representation for the tail probabilities of stationary reflected Brownian motion. Stoch. Process. Appl. 98, 253–287 (2002) ·Zbl 1059.60030 ·doi:10.1016/S0304-4149(01)00151-X |
| [14] | Feng, J., Kurtz, T.: Large Deviations for Stochastic Processes. Mathematical Surveys and Monographs, vol. 131. American Mathematical Society, Providence (2006) ·Zbl 1113.60002 |
| [15] | Flajolet, P.: The evolution of two stacks in bounded space and random walks in a triangle. In: Proceedings of FCT’86. LNCS, vol. 233, pp. 325–340. Springer, Berlin (1986) ·Zbl 0602.68029 |
| [16] | Freidlin, M., Wentzell, A.D.: Random Perturbations of Dynamical Systems. Grundlehren der Mathematischen Wissenschaften, vol. 260. Springer, New York (1984) ·Zbl 0522.60055 |
| [17] | Guillotin-Plantard, N., Schott, R.: Distributed algorithms with dynamic random transitions. Random Struct. Algorithms 21, 371–396 (2002) ·Zbl 1057.68133 ·doi:10.1002/rsa.10060 |
| [18] | Guillotin-Plantard, N., Schott, R.: Dynamic Random Walks. Theory and Applications. Elsevier, Amsterdam (2006) ·Zbl 1124.60086 |
| [19] | Gulinsky, O., Veretennikov, A.: Large Deviations for Discrete-Time Processes with Averaging. VSP, Utrecht (1993) ·Zbl 0838.60028 |
| [20] | Ignatiouk-Robert, I.: Large deviations for processes with discontinuous statistics. Ann. Probab. 33, 1479–1508 (2005) ·Zbl 1087.60024 ·doi:10.1214/009117905000000189 |
| [21] | Ignatiouk-Robert, I.: Sample path large deviations and convergence parameters. Ann. Appl. Probab. 11, 1292–1329 (2001) ·Zbl 1025.60011 ·doi:10.1214/aoap/1015345404 |
| [22] | Knuth, D.E.: The Art of Computer Programming, vol. 1. Addison–Wesley, Reading (1973) ·Zbl 0191.17903 |
| [23] | Lions, P.-L., Sznitman, A.-S.: Stochastic differential equations with reflecting boundary conditions. Commun. Pure Appl. Math. 37, 511–537 (1984) ·Zbl 0598.60060 ·doi:10.1002/cpa.3160370408 |
| [24] | Lions, P.-L.: Neumann type boundary conditions for Hamilton-Jacobi equations. Duke Math. J. 52, 793–820 (1985) ·Zbl 0599.35025 ·doi:10.1215/S0012-7094-85-05242-1 |
| [25] | Louchard, G.: Some distributed algorithms revisited. Commun. Stat. Stoch. Models 4, 563–586 (1995) ·Zbl 0840.90057 ·doi:10.1080/15326349508807361 |
| [26] | Louchard, G., Schott, R.: Probabilistic analysis of some distributed algorithms. Random Struct. Algorithms 2, 151–186 (1991) ·Zbl 0732.68055 ·doi:10.1002/rsa.3240020203 |
| [27] | Louchard, G., Schott, R., Tolley, M., Zimmermann, P.: Random walks, heat equations and distributed algorithms. Comput. Appl. Math. 53, 243–274 (1994) ·Zbl 0820.68052 ·doi:10.1016/0377-0427(94)90048-5 |
| [28] | Maier, R.: Colliding stacks: a large deviations analysis. Random Struct. Algorithms 2, 379–420 (1991) ·Zbl 0737.60097 ·doi:10.1002/rsa.3240020404 |
| [29] | Olivieri, E., Vares, M.E.: Large Deviations and Metastability. Encyclopedia of Mathematics and its Applications, vol. 100. Cambridge University Press, Cambridge (2005) |
| [30] | Williams, D.: Probability with Martingales. Cambridge University Press, Cambridge (1991) ·Zbl 0722.60001 |
| [31] | Yao, A.: An analysis of a memory allocation scheme for implementing stacks. SIAM J. Comput. 10, 398–403 (1981) ·Zbl 0457.68023 ·doi:10.1137/0210029 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
