Thesis Defense: Rati Gelashvili "On the Complexity of Synchronization"

Speaker: Rati Gelashvili

Date: Thursday, May 18, 2017

Time: 2:00 PM to 3:00 PM

Refreshments: 1:45 PM

Public: Yes

Location: 32-D463

Event Type:

Room Description:

Host: Nir Shavit, MIT

Contact: Joanne Talbot Hanley, 617-253-4602, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Thesis Defense: Rati Gelashvili "On the Complexity of Randomized Synchronization"

The field of distributed algorithms revolves around efficiently solving synchronization tasks, such as leader election (test-and-set), consensus and majority. This thesis makes contributions towards a better understanding of the complexity of central tasks in different standard distributed models.
The thesis defense will focus on the following results:
In the population protocols model, we develop a new leaderless phase clock technique. This enables us to solve majority efficiently, in time O(log^2 n), using O(log n) states per node, for n nodes. We complement this by a tight Omega(log n) lower bound on the number of states, conditional on basic monotonicity and output assumptions, satisfied by all known protocols.
In asynchronous shared memory, we solve n-process wait-free consensus by combining synchronization instructions that would be considered "weak" according to Herlihy's consensus hierarchy. This collapses the hierarchy when instructions can be applied to the same memory location, as is the case in all existing multicore processors. We suggest an alternative hierarchy and provide a practical universal construction using only "weak" instructions, raising a fundamental question about minimal set of synchronization instructions that the architectures have to support.
Determining the number of registers required for solving k-set agreement is a problem that highlights important gaps in our understanding and state-of-the-art methods. No general lower bound better than 2 is known. We introduce new ideas and techniques, inspired by the connections between distributed computability and combinatorial topology. For a given protocol P, we design a simulation in which, either the simulating processes solve an impossible task, or they simulate an "embedded adversarial" execution of P that uses many registers, proving strong lower bounds.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Joanne Talbot Hanley at Thursday, May 04, 2017 at 3:00 PM.