Deterministic Computations on a PRAM with Static Processor and Memory Faults

• Autorzy: Chlebus E. , Gąsieniec L. , Pelc A.
• Języki publikacji: EN

Abstrakty

EN

We consider Parallel Random Access Machine ( pram) which has some processors and memory cells faulty. The faults considered are static, i.e., once the machine starts to operate, the operational/faulty status of pram components does not change. We develop a deterministic simulation of a fully operational pram on a similar faulty machine which has constant fractions of faults among processors and memory cells. The simulating pram has n processors and m memory cells, and simulates a pram with n processors and a constant fraction of m memory cells. The simulation is in two phases: it starts with preprocessing, which is followed by the simulation proper performed in a step-by-step fashion. Preprocessing is performed in time O((m/n+ logn)logn). The slowdown of a step-by-step part of the simulation is O(logm).

Słowa kluczowe

EN

Parallel Random Access Machine (PRAM); simulation; preprocessing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 55, nr 3,4
• Strony: 285--306
• Opis fizyczny: bibliogr. 42 poz.

Twórcy

autor

Chlebus E.

autor

Gąsieniec L.

autor

Pelc A.

• Department of Computer Science and Engineering, University of Colorado at Denver, Campus Box 109, Denver, CO 80217-3364, USA

Bibliografia

• [1] R.J. Anderson, and H. Woll, Algorithms for the certified write-all problem, SIAM J. on Computing, 26 (1997) 1277 - 1283.
• [2] J. Aspnes, and M. Herlihy, Wait-free data structures in the asynchronous PRAM model, in Proc., nd ACM Symposium on Parallel Algorithms and Architectures, 1990, pp. 340 - 349.
• [3] H. Attiya, and J.L. Welch, “Distributed Computing: Fundamentals, Simulations, and Advaced Topics,” McGraw-Hill, 1998.
• [4] Y. Aumann, and M. Ben-Or, Asymptotically optimal PRAM emulation on faulty hypercubes, in Proc., 32 nd IEEE Symposium on Foundations of Computer Science, 1991, pp. 440 - 446.
• [5] Y. Aumann, Z. Kedem, K. Palem, and M.O. Rabin, Highly efficient asynchronous execution of large-grained parallel programs, in Proc., th IEEE Symposium on Foundations of Computer Science, 1993, pp. 271-280.
• [6] M. Ben-Or, S. Goldwasser, and A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computations, in Proc., th ACM Symposium on Theory of Computing, 1988, pp. 1 - 10.
• [7] P. Berenbrink, F. Meyer auf der Heide, and V. Stemann, Fault-tolerant shared memory simulations, in Proc., 13 th Symposium on Theoretical Aspects of Computer Science, 1996, Springer LNCS 1046, pp. 181 - 192.
• [8] J. Buss, P.C. Kanellakis, P. Ragde, and A.A. Shvartsman, Parallel algorithms with processor failures and delays, J. Algorithms, 20 (1996) 45 - 86.
• [9] B.S. Chlebus, S. Dobrev, D.R. Kowalski, G. Malewicz, A.A. Shvartsman, and I. Vrto, Towards practical deterministic write-all algorithms, in Proc., th ACM Symposium on Parallel Algorithms and Architectures, 2001, pp. 271 - 280.
• [10] B.S. Chlebus, A. Gambin, and P. Indyk, PRAM computations resilient to memory faults, in Proc., nd European Symposium on Algorithms, 1994, Springer LNCS 855, pp. 401 - 412.
• [11] B.S. Chlebus, A. Gambin, and P. Indyk, Shared-memory simulations on a faulty-memory DMM, in Proc., 23rd Int.. Colloquium on Automata, Languages and Programming, 1996, Springer LNCS 1099, pp. 586 -597.
• [12] R. Cole, and O. Zajicek, The APRAM: incorporating the asynchrony into the PRAM model, in Proc., 1st ACM Symposium on Parallel Algorithms and Architectures, 1989, pp. 169 - 178.
• [13] K. Diks and A. Pelc, Optimal adaptive broadcasting with a bounded fraction of faulty nodes, Algorithmica, 28 (2000) 37 - 50.
• [14] K. Diks and A. Pelc, Reliable computations on faulty EREW PRAM, Theoretical Computer Science, 164 (1996) 107 - 122.
• [15] C. Dwork, J. Halpern, and O. Waarts, Performing work efficiently in the presence of faults, SIAM J. on Computing, 27 (1998) 1457 - 1491.
• [16] L. Gąsieniec and P. Indyk, Efficient parallel computing with memory faults, in Proc., 11th Symposium on Fundamentals of Computation Theory, 1997, Springer LNCS 1279, pp. 188 - 197.
• [17] L. Gąsieniec and A. Pelc, Adaptive broadcasting with faulty nodes, Parallel Computing, 22 (1996) 903 - 912.
• [18] P. Gibbons, A more practical PRAM model, in Proc., 1st ACM Symposium on Parallel Algorithms and Architectures, 1989, pp. 158 - 168.
• [19] J.F. Groote, W.H. Hesselink, S. Mauw, and R. Vermeulen, An algorithm for the asynchronous write-all problem based on process collision, Distributed Computing, 14 (2001) 75 - 81.
• [20] T.J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys, 26 (1994) 187 - 206.
• [21] M. Herlihy, Impossibility results for asynchronous PRAM, in Proc., 3rd ACM Symposium on Parallel Algorithms and Architectures, 1991, pp. 327 - 336.
• [22] P. Indyk, On word-level parallelism in fault-tolerant computing, in Proc., 13th Symposium on Theoretical Aspects of Computer Science, 1996, Springer LNCS 1046, pp. 193 - 204.
• [23] J. JaJa, “An Introduction to Parallel Algorithms,” Addison Wesley, 1992.
• [24] P.C. Kanellakis and A.A. Shvartsman, Efficient parallel algorithms can be made robust, Distributed Computing, 5 (1992) 201 - 217.
• [25] P.C. Kanellakis and A.A. Shvartsman, “Fault-Tolerant Parallel Computation,” Kluwer Academic Publishers, 1997.
• [26] Z.M. Kedem, K.V. Palem, A. Raghunathan, and P. Spirakis, Combining tentative and definite executions for dependable parallel computing, in Proc., 23rd ACM Symposium on Theory of Computing, 1991, pp. 381 -390.
• [27] Z.M. Kedem, K.V. Palem, and P. Spirakis, Efficient robust parallel computations, in Proc., nd ACM Symposium on Theory of Computing, 1990, pp. 138 - 148.
• [28] S. Kontogiannis, G. Pantziou, P. Spirakis, and M. Yung, Robust parallel computations through randomization, Theory of Computing Systems, 33 (2000) 427 - 464.
• [29] F.T. Leighton, “Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes,” Morgan Kaufman Publishers, 1991.
• [30] Y.-D. Lyuu, “Information Dispersal and Parallel Computation,” Cambridge University Press, 1992.
• [31] F.J. MacWilliams, and N.J.A. Sloan, “The Theory of Error Correcting Codes,” North-Holland, 1977.
• [32] R.J. McEliece, and D.V. Sarwate, On sharing secrets and Reed-Solomon codes, Comm. ACM, 24 (1981) 583 - 584.
• [33] C. Martel and R. Subramonian, On the complexity of certified write-all algorithms, J. Algorithms, 16 (1994) 361 - 387.
• [34] C. Martel, A. Park, and R. Subramonian, Work-optimal asynchronous algorithms for shared memory parallel computers, SIAM J. on Computing, 21 (1992) 1070 - 1099.
• [35] F. Meyer auf der Heide, Hashing strategies for simulating shared memory on distributed memory machines, in Proc., 1st Heinz Nixdorf Symposium “Parallel Architectures and their Efficient Use,” 1992, Springer LNCS 678, pp. 20 - 29.
• [36] J. Naor, and R.M. Roth, Constructions of permutations arrays for certain scheduling cost measures, Random Structures and Algorithms, 6 (1995) 39 - 50.
• [37] F.P. Preparata, Holographic dispersal and recovery of information, IEEE Trans. on Information Theory, 35 (1989) 1123 - 1124.
• [38] M.O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, J. ACM, 36 (1989) 335 - 348.
• [39] E. Shamir, How to share a secret, Comm. ACM, 22 (1979) 612 - 613.
• [40] A.A. Shvartsman, Achieving optimal CRCW PRAM fault-tolerance, Information Processing Letters, 39 (1991) 59 - 66.
• [41] L.G. Valiant, A bridging model for parallel computation, Comm. ACM, 33 (1990) 103 - 111.
• [42] L.G. Valiant, General purpose parallel architectures, in “Handbook of Theoretical Computer Science,” J. van Leeuwen (Ed.), Elsevier, 1990, vol. A, pp. 869 - 941.