Distributed Computing
Solving coordination problems in the presence of failures and delays
Project status: Active
Research Areas
People
| Maurice Herlihy |
Publications
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 ]
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 ]
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 ]
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 ]
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., Herlihy, M., and Wattenhofer, R. Routing without Flow Control. In Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, Hersonissos, Greece (Jul 2001), pp. 11-20. [ 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. 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., 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., Tirthapura, S., and Wattenhofer, R. Ordered Multicast and Distributed Swap. Operating Systems Review 35, 1 (2001), 85-95. [ 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 ]
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., 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 (Jun 2000), 114-132. [ 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 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 ]
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 ]
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 Rajsbaum, S. New Perspectives in Distributed Computing. In Mathematical Foundations of Computer Science (Sep 1999), pp. 170-186. [ pdf ]
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 ]
Soma Chaudhuri, M. H., and Tuttle, M. R. Wait-free Implementations in Message-passing Systems. Theoretical Computer Science 220 (Jun 1999), 211-245. [ 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 ]
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 (Sep 1998), pp. 175-185. [ 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 ]
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. A Methodology for Implementing Highly Concurrent Data Objects. ACM Transactions on Programming Languages and Systems 15, 5 (Nov 1993), 745-770. [ 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., and Moss, J. Lock-Free Garbage Collection for Multiprocessors. IEEE Transactions on Parallel and Distributed Systems 3, 2 (Apr 1992), 304-311. [ 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. Impossibility Results for Asynchronous PRAM. In Proceedings of the 2nd Annual Symposium on Parallel Algorithms and Architectures (Jul 1991), pp. 327-336. [ pdf ]
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., and Wing, J. Specifying Graceful Degradation. IEEE Transactions on Parallel and Distributed Systems 2, 1 (Jul 1991), 93-104. [ 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 (Jul 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 (Jul 1987).
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. Extending Multiversion Timestamping Protocols to Exploit Type Information. IEEE Transactions on Computers C-35, 4 (Apr 1987), 443-449.
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 |