UCLA Logic Colloquium, Dec 2

UCLA LOGIC COLLOQUIUM
Friday, December 2, 2005
4:00 p.m.
Mathematical Sciences 6627
UCLA

ELI GAFNI

Computer Science, UCLA

"DISTRIBUTED SYMMETRY-BREAKING:
RENAMING IS WEAKER THAN SET AGREEMENT!"

We resolve a problem in distributed computing, open since the discovery
of the connection between distributed computing and topology, back in
1993. Then, the problems of renaming and set agreement were proved to
be impossible to solve wait-free in a read-write shared-memory model.
However, the proofs were very different, and the relation between the
problems was left unclear. Moreover, the renaming impossibility proof
relied on non-trivial algebraic topology techniques.

Our main result is that renaming is strictly weaker than set agreement.
To prove this impossibility, we design a new model of computation, that
we believe is interesting by itself. It is the first model we know of
where an easy analysis of the topology of a protocol that invokes other
protocols can be performed, and hence for a general setting to study
reductions. To study reductions between renaming and set agreement, we
identify and study a symmetry breaking class of tasks, where processes
decide on binary output values. We show that set agreement and renaming
are just variations of symmetry breaking. Also, we formulate a new
version of the celebrated index lemma, that yields the first elementary
proof of the renaming impossibility proof. Finally, by exhibiting
a symmetry breaking task that is a symmetric manifold and solves
renaming, we pinpoint the difference between set-agreement and renaming.
While the former is impossible to solve using tasks that are manifolds,
the latter cannot be solved by a task that is an orientable manifold.
Unfortunately read-write memory is an orientable manifold.

Joint work with Sergio Rajsbaum, UNAM.

-------------------------------------------------------------

http://www.logic.ucla.edu

.