Leader Election and Renaming with Optimal Message Complexity

Speaker: Rati Gelashvili , MIT

Date: Wednesday, April 23, 2014

Time: 5:00 PM to 6:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Ilya Razenshteyn

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/?q=index

Speaker URL: None

Speaker Photo:
None

Reminders to: ryadegar@csail.mit.edu

Reminder Subject: TALK: Algorithms & Complexity Seminar: Rati Gelashvili

Abstract: Asynchronous message-passing system is a standard distributed model,where $n$ processors communicate over unreliable channels,controlled by a strong adaptive adversary. The asynchronous nature of the system and the fact that $t < n / 2$ processes may fail by crashing are the great obstacles for designing efficient algorithms.

\emph{Leader election (test-and-set)} and \emph{renaming} are two fundamental distributed tasks. We prove that both tasks can be solved using expected $O( n^2 )$ messages---the same asymptotic complexity as a single all-to-all broadcast---and that this message complexity is in fact optimal.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Rebecca Yadegar at Tuesday, April 22, 2014 at 3:23 PM.