简介: |
Abstract:
We consider the relative power of two important synchronization problems: set agreement and renaming. We show that renaming is strictly weaker than set agreement in a round-by-round model of computation.
We introduce new techniques including previously unknown connections between properties of manifolds and computation, as well as novel "symmetry-breaking" constructions.
Biography: Maurice Herlihy received an A.B. in Mathematics from Harvard University, and a Ph.D. in Computer Science from M.I.T. He has served on the faculty of Carnegie Mellon University, on the staff of DEC Cambridge Research Lab, and is currently a Professor in the Computer Science Department at Brown University. His 1991 paper "Wait-Free Synchronization" won the 2003 Dijkstra Prize in Distributed Computing, and he shared the 2004 Goedel Prize for his 1999 paper "The Topological Structure of Asynchronous Computation." He is a Fellow of the ACM. |
