Maurice Herlihy
Nir Shavit
- AFEK, Y., ATTIYA, H., DOLEV, D., GAFNI, E., MERRITT, M., AND SHAVIT, N. 1990. Atomic snapshots of shared memory. In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing (Quebec City, Que., Canada, Aug. 22-24). ACM, New York, pp. 1-14. Google Scholar
- AFEK, Y., AND STUPP, G. 1993. Synchronization power depends on the register size (preliminary version). In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif. 195-205.Google Scholar
- ANDERSON, J. 1990. Composite registers. In Proceedings of the 9th ACM Symposium on Principles of Distributed Computing (Quebec City, Que., Canada, Aug. 22-24). ACM, New York, pp. 15-30. Google Scholar
- ATTIYA, n., BAR-NOY, A., DOLEV, D., PELEG, D., AND REISCHUK, R. 1990. Renaming in an asynchronous environment. J. ACM, July. Google Scholar
- ATTIYA, H., LYNCH, N., AND SHAVIT, N. 1990. Are wait-free algorithms fast? In Proceedings of the 31st Annual Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. 55-64.Google Scholar
- ATTIYA, n., AND RAJSBAUM, S. 1995. A combinatorial topology framework for wait-free computability. Preprint.Google Scholar
- ATTIYA, H., AND WELCH, J. 1998. Distributed Computing: fundamentals, simulations and advanced topics. McGraw-Hill, London, England. ISBN 0-07-7093526. Google Scholar
- BAR-NOY, A., AND DOLEV, D. 1989. Shared-memory vs. message-passing in an asynchronous distributed environment. In Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing (Edmonton, Alb., Canada, Aug. 14-16). ACM, New York, pp. 307-318. Google Scholar
- BmAN, O., MORAN, S., AND ZAKS, S. 1988. A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (Toronto, Ont., Canada, Aug. 15-17). ACM, New York, pp. 263-275. Google Scholar
- BOROWSKY, E. 1995. Capturing the power of resiliency and set consensus in distributed systems. Tech. rep., University of California Los Angeles, Los Angeles, Calif.Google Scholar
- BOROWSKY, E., AND GAFNI, E. 1993. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 91-100. Google Scholar
- BOROWSKY, E., AND GAFNI, E. 1993. Immediate atomic snapshots and fast renaming. In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing (Ithaca, N.Y., Aug. 15-18). ACM, New York, pp. 41-52. Google Scholar
- CHAUDHURI, S. 1990. Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing (Quebec City, Que., Canada, Aug. 22-24). ACM, New York, pp. 311-324. Google Scholar
- CHAUDHURI, S., HERLIHY, M. P., LYNCH, N., AND TUTTLE, M.R. 1993. A tight lower bound for k-set agreement. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (Oct.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 206-215.Google Scholar
- CHOR, B., ISRAELI, A., AND LI, M. 1987. On processor coordination using asynchronous hardware. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 10-12). ACM, New York, pp. 86-97. Google Scholar
- CHOR, B., AND MOSCOVICI, L. 1989. Solvability in asynchronous environments. In IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif., pp. 422-427.Google Scholar
- DOLEV, D., DWORK, C., AND STOCKMEYER, L. 1987. On the minimal synchronism needed for distributed consensus. J. ACM 34, 1 (Jan.), 77-97. Google Scholar
- FEKETE, A. 1986. Asymptotically optimal algorithms for approximate agreement. In Proceedings of the 5th Annual ACM Symposium on Principles of Distributed Computing (Calgary, Alb., Canada, Aug. 11-13). ACM, New York, pp. 73-87. Google Scholar
- FISCHER, M., LYNCH, N. A., AND PATERSON, M.S. 1985. Impossibility of distributed commit with one faulty process. J. ACM 32, 2 (Apr.). Google Scholar
- GAFNI, E., AND KOUTSOUPIAS, E. 1996. Three-processor tasks are undecidable, http://daphne.cs.ucla.edu/eli/undec.ps.Google Scholar
- GLASER, L. C. 1970. Geometrical Combinatorial Topology, Vol. 1. Van Nostrand Reinhold, New York.Google Scholar
- HERLIHY, M. P. 1991. Wait-free synchronization. ACM Trans. Prog. Lang. Syst. 13, 1 (Jan.), 123-149. Google Scholar
- HERLmY, M. P., AND RAJSBAUM, S. 1994. Set consensus using arbitrary objects. In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (Los Angeles, Calif., Aug. 14-17). ACM, New York, pp. 324-333. Google Scholar
- HERLIHY, M., AND RAJSBAUM, S. 1995. Algebraic spans. In Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing (Ottawa, Ont., Canada, Aug. 20-23). ACM, New York, pp. 90-99. Google Scholar
- HERLIHY, M. P., AND RAJSBAUM, S. 1997. The decidability of distributed decision tasks. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 589-598. Google Scholar
- HERLIHY, M., AND RAJSBAUM, S. 1998. A wait-free classification of loop agreement tasks. In Proceedings of the 12th International Symposium on Distributed Computing (Sept.). Springer-Verlag, New York, pp. 175-185. Google Scholar
- HERLIHY, M. P., RAJSBAUM, S., AND TUTTLE, M.R. 1998. Unifying synchronous and asynchronous message-passing models. In Proceedings of the 12th International Symposium on Distributed Computing (Sept.). Google Scholar
- HERLIHY, M. P., AND SHAVIT, N. 1993. The asynchronous computability theorem for t-resilient tasks. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 111-120. Google Scholar
- HERLIHY, M. P., AND SHAVIT, N. 1994. A simple constructive computability theorem for wait-free computation. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 243-252. Google Scholar
- HERLIHY, M. P., AND WING, J.M. 1990. Linearizability: A correctness condition for concurrent objects. ACM Trans. Prog. Lang. Syst. 12, 3 (July), 463-492. Google Scholar
- HOEST, G. 1997. Towards a Topological Characterization of Asynchronous Complexity. Ph.D. dissertation. Mass. Institute of Technology, Cambridge, Mass.Google Scholar
- HOEST, G., AND SHAVIT, N. 1997. Towards a topological characterization of asynchronous complexity. In Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (Santa Barbara, Calif., Aug. 21-24). ACM, New York, pp. 199-208. Google Scholar
- LEFSCHETZ, S. 1949. Introduction to Topology. Princeton University Press, Princeton, N.J.Google Scholar
- LouI, M. C., AND ABU-AMARA, H.H. 1987. Memory Requirements for Agreement Among Unreliable Asynchronous Processes, vol. 4. JAI Press, Greenwich, Conn., pp. 163-183.Google Scholar
- LYNCH, N.A. 1996. Distributed Algorithms. Morgan-Kaufmann, New York. Google Scholar
- LYNCH, N. A., AND TUTTLE, M.R. 1988. An introduction to input/output automata. Tech. Rep. MIT/LCS/TM-373. HIT Laboratory for Computer Science, Cambridge, Mass.Google Scholar
- MUNKaES, J. R. 1984. Elements of Algebraic Topology. Addison-Wesley, Reading, Mass. ISBN 0-201-04586-9.Google Scholar
- SAKS, M., AND ZAHAROGLOU, F. 1993. Wait-free k-set agreement is impossible: The topology of public knowledge. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 101-110. Google Scholar
- SPANIER, E.H. 1966. Algebraic Topology. Springer-Verlag, New York.Google Scholar
Index Terms
- The topological structure of asynchronous computability
Recommendations
Enriched homology and cohomology modules of simiplicial complexes
For a simplicial complex Δ on {1, 2, , n } we define enriched homology and cohomology modules. They are graded modules over k [ x 1 , , x n ] whose ranks are equal to the dimensions of the reduced homology and cohomology groups.
We ...
Note: Combinatorial Alexander Duality--A Short and Elementary Proof
Let X be a simplicial complex with ground set V. Define its Alexander dual as the simplicial complex X*={ź⊆VźVźźźX}. The combinatorial Alexander duality states that the ith reduced homology group of X is isomorphic to the (|V|źiź3)th reduced cohomology ...
Computable obstructions to wait-free computability
We present an algorithmic test for deterministic wait-free solvability of decision tasks in asynchronous distributed systems whose processes communicate via read-write shared memory. Input to the test is a formal representation of the decision task as a ...
Comments