|
|
Title:Renaming is Weaker than Set Agreement |
Name: Maurice Herlihy Brown University |
|
| Time:October 13th (Monday) 16:00-16:45 | |
| Location: Lecture Hall, FIT Building, Tsinghua University | |
| Host Unit: ITCS, Tsinghua University |
|
|
Title:Renaming is Weaker than Set Agreement |
Name: Maurice Herlihy Brown University |
|
| Time:October 13th (Monday) 16:00-16:45 | |
| Location: Lecture Hall, FIT Building, Tsinghua University | |
| Host Unit: ITCS, Tsinghua University |
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.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.
