Distributed Computing
Solving coordination problems in the presence of failures and delays
Project status: Active
Research Areas
People
| Maurice Herlihy |
Publications
Moreshet, T., Bahar, R. I., and Herlihy, M. Energy Reduction in Multiprocessor Systems Using Transactional Memory. In Proceedings of the International Symposium on Low Power Electronics and Design (Aug. 2005), pp. 331-334. [ pdf ]
Dvir, O., Herlihy, M., and Shavit, N. Virtual Leashing: Internet-Based Software Piracy Protection. In Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS) (2005), pp. 283-292. [ pdf ]
Fatourou, P., and Herlihy, M. Read-modify-write Networks. Distributed Computing 17, 1 (2004), 33-46. [ pdf ]
Herlihy, M., and Tirthapura, S. Self-Stabilizing Smoothing and Counting. In Proceedings of the 23rd International Conference on Distributed Computing Systems (May 2003), pp. 4-11. [ pdf ]
Herlihy, M., and Penso, L. D. Tight Bounds for k-Set Agreement with Limited-scope Failure Detectors. In Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing (PODC-03) (New York, NY, USA, 2003), ACM Press, p. 221. [ pdf ]
Herlihy, M., and Rajsbaum, S. A Classification of Wait-Free Loop Agreement Tasks. Theoretical Computer Science 291, 1 (Nov. 2002), 55-77. [ pdf ]
Herlihy, M., Luchangco, V., and Moir, M. The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structure. In Proceedings of the 16th International Symposium on Distributed Computing (Oct. 2002), pp. 339-353. [ pdf ]
Busch, C., and Herlihy, M. Sorting and Counting Networks of Small Depth and Arbitrary Width. Theory of Computing Systems 35, 2 (2002), 99-138. [ pdf ]
Busch, C., Demetriou, N., Herlihy, M., and Mavronicolas, M. Threshold Counters with Increments and Decrements. Theoretical Computer Science 270, 1-2D (Jan. 2002), 811-826. [ pdf ]
Fatourou, P., and Herlihy, M. Adding Networks. In Proceedings of the 15th International Symposium on Distributed Computing (DISC 2001), Lisbon, Portugal (Oct. 2001), pp. 330-342. [ pdf ]
Herlihy, M., Rajsbaum, S., and Tuttle, M. A New Synchronous Lower Bound for Set Agreement. In Proceedings of the 15th International Symposium on Distributed Computing (DISC 2001), Lisbon, Portugal (Oct. 2001), pp. 136-150. [ pdf ]
Herlihy, M., and Tirthapura, S. Self-Stabilizing Distributed Queueing. In Proceedings of the 15th International Symposium on Distributed Computing (Oct. 2001), pp. 209-223. [ pdf ]
Busch, C., Herlihy, M., and Wattenhofer, R. Routing without Flow Control. In Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, Hersonissos, Greece (July 2001), pp. 11-20. [ pdf ]
Herlihy, M. On Beyond Registers: Wait-free Readable Objects. In Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing (PODC 01) (2001), ACM Press, pp. 26-42. [ pdf ]
Herlihy, M., Tirthapura, S., and Wattenhofer, R. Ordered Multicast and Distributed Swap. Operating Systems Review 35, 1 (2001), 85-95. [ pdf ]
Herlihy, M., and Ruppert, E. On the Existence of Booster Types. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science (FOCS) (Nov. 2000), pp. 653-663. [ pdf ]
Busch, C., Demetriou, N., Herlihy, M., and Mavronicolas, M. A Combinatorial Characterization of Properties Preserved by Antitokens. Bulletin of the European Association for Theoretical Computer Science, 71 (June 2000), 114-132. [ pdf ]
Aiello, W., Busch, C., Herlihy, M., Mavronicolas, M., Shavit, N., and Touitou, D. Supporting Increment and Decrement Operations in Balancing Networks. Chicago Journal of Theoretical Computer Science (2000). [ pdf ]
Busch, C., Herlihy, M., and Wattenhofer, R. Hard-Potato Routing. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (2000), ACM Press, pp. 278-285. [ pdf ]
Busch, C., Herlihy, M., and Wattenhofer, R. Randomized Greedy Hot-Potato Routing. In Proceedings of the 11th Annual ACM Society for Industrial and Applied Mathematics (SIAM) Symposium on Discrete Algorithms (2000), ACM Press, pp. 458-466. [ pdf ]
Herlihy, M., and Rajsbaum, S. Algebraic Spans. Mathematical Structures in Computer Science 10, 4 (2000), 549-573. [ pdf ]
Herlihy, M., and Warres, M. P. A Tale of Two Directories: Implementing Distributed Shared Objects in Java. Concurrency: Practice and Experience 12, 7 (2000), 555-572. [ pdf ]
Herlihy, M., and Rajsbaum, S. New Perspectives in Distributed Computing. In Mathematical Foundations of Computer Science (Sept. 1999), pp. 170-186. [ pdf ]
Soma Chaudhuri, M. H., and Tuttle, M. R. Wait-free Implementations in Message-passing Systems. Theoretical Computer Science 220 (June 1999), 211-245. [ pdf ]
Busch, C., and Herlihy, M. Sorting and Counting Networks of Small Depth and Arbitrary Width. In Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures (1999), ACM Press, pp. 64-73. [ pdf ]
Herlihy, M. The Aleph Toolkit: Support for Scalable Distributed Shared Objects. In Proceedings of the Workshop on Communication, Architecture, and Applications for Network-based Parallel Computing (Jan. 1999), pp. 137-149.
Herlihy, M., and Shavit, N. The Topological Structure of Asynchronous Computability. Journal of the Association for Computing Machinery (ACM) 46, 6 (1999), 858-923. [ pdf ]
Herlihy, M., and Rajsbaum, S. A Wait-Free Classification of Loop Agreement Tasks. In Proceedings of the 12th International Symposium on Distributed Computing (DISC98) Andros, Greece (Sept. 1998), pp. 175-185. [ pdf ]
Fich, F., Herlihy, M., and Shavit, N. On the Space Complexity of Randomized Synchronization. Journal of the Association for Computing Machinery (ACM) 45, 5 (1998), 843-862. [ pdf ]
Herlihy, M., Rajsbaum, S., and Tuttle, M. R. Unifying Synchronous and Asynchronous Message-passing Models. In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing (1998), ACM Press, pp. 133-142. [ pdf ]
Dwork, C., Herlihy, M., and Waarts, O. Contention in Shared Memory Algorithms. Journal of the Association for Computing Machinery (ACM) 44, 6 (1997), 779-805. [ pdf ]
Herlihy, M., and Rajsbaum, S. The Decidability of Distributed Decision Tasks (Extended Abstract). In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (1997), ACM Press, pp. 589-598. [ pdf ]
Herlihy, M., and Rajsbaum, S. Algebraic Topology and Distributed Computing - a Primer. In Computer Science Today - Recent Trends and Developments, J. van Leeuwen, Ed. Springer-Verlag, 1996. [ pdf ]
Herlihy, M., Shavit, N., and Waarts, O. Linearizable Counting Networks. Distributed Computing 9, 4 (1996). [ pdf ]
Attiya, H., Herlihy, M., and Rachman, O. Atomic Snapshots in Expected O(n) Operations Using Lattice Agreement. Distributed Computing 8, 3 (Mar. 1995), 121-132.
Herlihy, M., Lim, B.-H., and Shavit, N. Scalable Concurrent Counting. ACM Transactions on Computer Systems 13, 4 (1995), 343-364. [ pdf ]
Aspnes, J., Herlihy, M., and Shavit, N. Counting Networks. Journal of the ACM 41, 5 (1994), 1020-1048. [ pdf ]
Herlihy, M., and Rajsbaum, S. Set Consensus Using Arbitrary Objects (preliminary version). In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (1994), ACM Press, pp. 324-333. [ pdf ]
Herlihy, M. A Methodology for Implementing Highly Concurrent Data Objects. ACM Transactions on Programming Languages and Systems 15, 5 (Nov. 1993), 745-770. [ pdf ]
Chaudhuri, S., Herlihy, M. P., Lynch, N., and Tuttle, M. R. A Tight Lower Bound for k-set Agreement. In Proceedings of the ACM Symposium on Foundations of Computer Science (Oct. 1993), pp. 206-215. [ pdf ]
Dwork, C., and Herlihy, M. Bounded Round Numbers. In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing (1993), ACM Press, pp. 53-64. [ pdf ]
Herlihy, M., and Moss, J. Lock-Free Garbage Collection for Multiprocessors. IEEE Transactions on Parallel and Distributed Systems 3, 2 (Apr. 1992), 304-311. [ pdf ]
Dwork, C., Herlihy, M., Plotkin, S. A., and Waarts, O. Time-Lapse Snapshots. In Proceedings of the Israel Symposium on Theory of Computing Systems (1992), pp. 154-170.
Herlihy, M., Lynch, N., Merritt, M., and Weihl, W. On the Correctness of Orphan Management Algorithms. Journal of the Association for Computing Machinery (ACM) 39, 4 (1992), 881-930. [ pdf ]
Herlihy, M. Impossibility Results for Asynchronous PRAM. In Proceedings of the 2nd Annual Symposium on Parallel Algorithms and Architectures (July 1991), pp. 327-336. [ pdf ]
Herlihy, M., and Wing, J. Specifying Graceful Degradation. IEEE Transactions on Parallel and Distributed Systems 2, 1 (July 1991), 93-104. [ pdf ]
Herlihy, M., and Weihl, W. Hybrid Concurrency Control for Abstract Data Types. Journal of Computer and System Sciences, 41 (1991), 25-61.
Herlihy, M. Randomized Wait-free Concurrent Objects (extended abstract). In Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing (1991), ACM Press, pp. 11-21. [ pdf ]
Herlihy, M. Wait-free Synchronization. ACM Transactions on Programming Languages and Systems 13, 1 (1991), 124-149. [ pdf ]
Aspnes, J., and Herlihy, M. Fast Randomized Consensus Using Shared Memory. Journal of Algorithms 11, 3 (1990), 441-461. [ pdf ]
Aspnes, J., and Herlihy, M. Wait-free Data Structures in the Asynchronous PRAM Model. In Proceedings of the Second Annual ACM Symposium on Parallel Algorithms and Architectures (1990), ACM Press, pp. 340-349. [ pdf ]
Herlihy, M. Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types. ACM Transactions on Database Systems 15, 1 (1990), 96-124. [ pdf ]
Herlihy, M. Concurrency and Availability as Dual Properties of Replicated Atomic Data. Journal of the Association for Computing Machinery (ACM) 37, 2 (1990), 257-278. [ pdf ]
Herlihy, M. P., and Wing, J. M. Linearizability: a Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems 12, 3 (1990), 463-492. [ pdf ]
Herlihy, M., and Tygar, J. Implementing Distributed Capabilities Without a Trusted Kernel. In Proceedings of the International Working Conference on Dependable Computing for Critical Applications (Aug. 1989).
Herlihy, M., and McKendry, M. Timestamp-based Orphan Elimination. IEEE Transactions on Software Engineering 15, 7 (July 1989), 825-831. [ pdf ]
Herlihy, M., and Wing, J. Avalon: Language Support for Reliable Distributed Systems. In Proceedings of the 17th Symposium on Fault-Tolerant Computer Systems (July 1987).
Herlihy, M. Extending Multiversion Timestamping Protocols to Exploit Type Information. IEEE Transactions on Computers C-35, 4 (Apr. 1987), 443-449.
Herlihy, M. Concurrency Versus Availability: Atomicity Mechanisms for Replicated Data. ACM Transactions on Computer Systems 5, 3 (1987), 249-274.
Herlihy, M. Dynamic Quorum Adjustment for Partitioned Data. ACM Transactions on Database Systems 12, 2 (1987), 170-194. [ pdf ]
Herlihy, M., and Tygar, J. D. How to Make Replicated Data Secure. In CRYPTO (1987), pp. 379-391. [ pdf ]
Herlihy, M. A Quorum-Consensus Replication Method for Abstract Data Types. ACM Transactions on Computer Systems 4, 1 (1986), 32-53. [ pdf ]
Liskov, B., Herlihy, M., and Gilbert, L. Limitations of Synchronous Communication with Static Process Structure in Languages for Distributed Computing. In Proceedings of the 13th ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) - Special Interest Group for Programming Languages (SIGPLAN) Symposium on Principles of Programming Languages (1986), ACM Press, pp. 150-159.
Herlihy, M. P., and Liskov, B. A Value Transmission Method for Abstract Data Types. ACM Transactions on Programming Languages and Systems 4, 4 (1982), 527-551. [ pdf ]
| Page Owner: Webmaster | Last Modified: Mon Oct 23 14:57:09 2006 |