Title: To use ID or not to use ID, is that a question? (slides in PDF)
Pierre Fraigniaud (University Paris Diderot, France)
http://www.liafa.jussieu.fr/~pierref/
Abstract: Identities (IDs) play an important role in distributed computing, e.g., to break symmetry. However, there are contexts in which ID may potentially play no role. This is typically the case when one is not interested in constructing a valid instance (e.g., constructing a proper coloring of a graph), but one is interested in deciding whether a given instance is valid or not, i.e., satisfies some specific properties (e.g., deciding whether a given coloring is a proper coloring). We investigate the question of whether the presence of IDs helps for decision tasks, in the framework of local computation. (Note that there are various contexts in which distributed systems may perform in absence of IDs, e.g., in biological systems like ant colonies and bacteria). It turns out that, in the LOCAL model, IDs may not help for decision tasks. We provide some evidences of this belief, derived from the study of solving decision tasks using randomization or a form of non-determinism.
This is a joint work with Amos Korman and Magnus Halldorsson.
