Efficient parallel algorithms on restartable fail-stop processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient parallel algorithms on restartable fail-stop processors

Full text

Pdf (1.40 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the tenth annual ACM symposium on Principles of distributed computing table of contents

Montreal, Quebec, Canada

Pages: 23 - 36

Year of Publication: 1991

ISBN:0-89791-439-2

Authors

Paris C. Kanellakis	Computer Science Dept., Brown University, PO Box 1910, Providence, RI
Alex A. Shvartsman	Computer Science Dept., Brown University, PO Box 1910, Providence, RI

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 8, Citation Count: 14

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/112600.112603 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AAS 87	George B. Adams, III , Dharma P. Agrawal , Howard Jay Seigel, A survey and comparison of fault-tolerant multistage interconnection networks, Computer, v.20 n.6, p.14-27, June 1987 [doi>10.1109/MC.1987.1663586]
	AAPS 87	Y. Afek, B. Awerbuch, S. Plotkin, M. Saks, "Local Management of a Global Resource in a Communication Network", Proc. of the 28th IEEE FOGS, pp. 347-357, 1987.
	AU 90	S. Assaf and E. Upfal, "Fault Tolerant Sorting Network," in Proc. of ~he 31s~ IEEE FOCS, pp. 275-284, 1990.
	CZ 89	R. Cole , O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.169-178, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72954]
	CZ 90	R. Cole , O. Zajicek, The expected advantage of asynchrony, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.85-94, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97673]
	Cri 91	Flavin Cristian, Understanding fault-tolerant distributed systems, Communications of the ACM, v.34 n.2, p.56-78, Feb. 1991 [doi>10.1145/102792.102801]
	DPPU 86	C Dwork , D Peleg , N Pippenger , E Upfal, Fault tolerance in networks of bounded degree, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.370-379, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12169]
	EG 88	David Eppstein , Zvi Galil, Parallel algorithmic techniques for combinatorial computation, Annual review of computer science: vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988
	FW 78	Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
	Gib 89	P. B. Gibbons, A more practical PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72953]
	HP 89	S. W. Hornick , F. P. Preparata, Deterministic P-RAM simulation with constant redundancy, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.103-109, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72947]
	IEEE 90	IEEE Computer, "Fault-Tolerant Systems", a special issue, Vol.23, No.7, 1990.
	K* 90	C. Kaklamanis, A. Karlin, F. Leighton, V. Milenkovic, P. Raghavan, S. Rao, C. Thomborson, A. Tsantilas, "Asymptotically Tight Bounds for Computing with Arrays of Processors," in Proc. of the 318~ IEEE FOCS, pp. 285-296, 1990.
	KS 89	P. C. Kanellakis , A. A. Shvartsman, Efficient parallel algorithms can be made robust, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.211-219, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72996]
	KR 90	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	Mar 91	C. Martel, personal communication, March, 1991.
	KPS 90	Z. M. Kedem , K. V. Palem , P. G. Spirakis, Efficient robust parallel computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.138-148, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100231]
	KPRS 90	Z. M. Kedem , K. V. Palem , A. Raghunathan , P. G. Spirakis, Combining tentative and definite executions for dependable parallel computing, University of Maryland at College Park, College Park, MD, 1990
	KRS 88	Clyde P. Kruskal , Larry Rudolph , Marc Snir, Efficient synchronization of multiprocessors with shared memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.579-601, Oct. 1988 [doi>10.1145/48022.48024]
	LGFG 86	Nancy A Lynch , Nancy D Griffeth , Michael J Fishcher , Leonidas J Guibas, Probabilistic analysis of a network resource allocation algorithm, Information and Control, v.68 n.1-3, p.47-85, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80028-6]
	MSP 90	C. Martel, R. Subramonian, and A. Park, "Asynchronous PRAMs are (Almost) as Good as Synchronous PRAMs," in Proc. 32d iEEE Syrup. on Foundat. of Computer Sci., pp. 590-599, 1990. Also see Tech. Rep. CSE-89-6, Univ. of Calif.- Davis, 1989.
	Nis 90	N. Nishimura, Asynchronous shared memory parallel computation, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.76-84, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97672]
	Pip 85	N. Pippenger, "On networks of noisy gates", Proc. of ~6th IEEE FOCS, pp. 30-38, 1985.
	Ran 87	A. Ranade, "How to Emulate Shared Memory'', Proc. of ~8th IEEE FOCS, pp. 185-194, 1987.
	Rud 85	L. Rudolph, "A Robust Sorting Network", IEEE Trans. on Comp., vol.34, no.4, pp. 326-335, 1985.
	SM 84	D.B. Sarrazin and M. Malek, "Fault-tolerant Semiconductor Memories", IEEE Computer, Vo1.17, No.8, pp. 49-56, 1984.
	SS 83	Richard D. Schlichting , Fred B. Schneider, Fail-stop processors: an approach to designing fault-tolerant computing systems, ACM Transactions on Computer Systems (TOCS), v.1 n.3, p.222-238, August 1983 [doi>10.1145/357369.357371]
	Sch 80	Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
	Shv 89	Alex A. Shvartsman, Achieving Optimal CRCW PRAM Fault-Tolerance, Brown University, Providence, RI, 1989
	Upf 89	E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73030]
	Val 90a	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	Val 90b	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]

CITED BY 14

	Cynthia Dwork , Joseph Y. Halpern , Orli Waarts, Performing work efficiently in the presence of faults, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.91-102, August 10-12, 1992, Vancouver, British Columbia, Canada
	Ramesh Subramonian, Designing synchronous algorithms for asynchronous processors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.189-198, June 29-July 01, 1992, San Diego, California, United States
	Serge Abiteboul , Gabriel M. Kuper , Harry G. Mairson , Alexander A. Shvartsman , Moshe Y. Vardi, In memoriam Paris C. Kanellakis, ACM Computing Surveys (CSUR), v.28 n.1, p.3-15, March 1996
	Z. M. Kedem , K. V. Palem , M. O. Rabin , A. Raghunathan, Efficient program transformations for resilient parallel computation via randomization (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.306-317, May 04-06, 1992, Victoria, British Columbia, Canada
	Spyros C. Kontogiannis , Grammati E. Pantziou , Paul G. Spirakis , Moti Yung, “Dynamic-fault-prone BSP”: a paradigm for robust computations in changing environments, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.37-46, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Elizabeth Borowsky , Eli Gafni, Immediate atomic snapshots and fast renaming, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.41-51, August 15-18, 1993, Ithaca, New York, United States
	Yonatan Aumann , Michael A. Bender , Lisa Zhang, Efficient execution of nondeterministic parallel programs on asynchronous systems, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.270-276, June 24-26, 1996, Padua, Italy
	Michael A. Bender , Michael O. Rabin, Scheduling Cilk multithreaded parallel programs on processors of different speeds, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.13-21, July 09-13, 2000, Bar Harbor, Maine, United States
	Serge Abiteboul , Gabriel M. Kuper , Harry G. Mairson , Alexander A. Shvartsman , Moshe Y. Vardi, In Memoriam: Paris C. Kanellakis, Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge: Paris C. Kanellakis memorial workshop on the occasion of his 50th birthday, p.1-8, June 08-08, 2003, San Diego, California, USA
	Paris C. Kanellakis , Dimitrios Michailidis , Alex Allister Shvartsman, Controlling memory access concurrency in efficient fault-tolerant parallel algorithms, Nordic Journal of Computing, v.2 n.2, p.146-180, Summer 1995
	Spyros C. Kontogiannis , Grammati E. Pantziou , Paul G. Spirakis, Efficient computations on fault-prone BSP machines, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.84-93, June 23-25, 1997, Newport, Rhode Island, United States
	Shlomi Dolev, Possible and Impossible Self-Stabilizing Digital ClockSynchronization in General Graphs, Real-Time Systems, v.12 n.1, p.95-107, Jan. 1997
	Paris C. Kanellakis , Alex A. Shvartsman, Efficient parallel algorithms can be made robust, Distributed Computing, v.5 n.4, p.201-217, April 1992
	Cynthia Dwork, Distributed computing column, ACM SIGACT News, v.27 n.3, p.50-54, Sept. 1996