Rati Gelashvili

@ gelash csail.mit.edu

I did my Ph.D. in the Multicore Algorithms Group at MIT,
and had the pleasure to be supervised by Prof. Nir Shavit.
Afterwards, I was a Postdoctoral Fellow at the University of Toronto,
this time having the pleasure to work with Prof. Faith Ellen.

My research is in distributed computing, centered on
the complexity of synchronization.
I have worked on the complexity of concurrent algorithms
in different asynchronous distributed models:
time and space complexity of algorithms in shared-memory systems,
time and message complexity in the message passing models, and
time and state complexity of population protocols.
My full research statement can be found here.

During high school, I competed at international math and informatics olympiads.
I did my undergrad at ETH Zurich and have interned at Google, Facebook, Akamai,
Microsoft Reseach, Dropbox and D.E.Shaw.

I like coding when I do math and I like math when I code :-).


Detour


A list of some of my favorite papers.

Time-tested

FLP: A must-read for anyone interested in asynchrony. Foundational.
Burns-Lynch: This paper introduced covering arguments. Very clever and elegant.
Tight Step Bound for Consensus by Attyia and Censor-Hillel: Beautiful techniques, some originating in this
tour de force by Aspnes that bounds the number of randomized coin flips.
Gödel prize-winning papers showing k-set agreement impossibility: Establishing a connection between combinatorial
topology and distributed computing. I recommend checking Maurice Herlihy's website for sources to learn more.

More recent

Doty-Soloveichik linear time lower bound for constant-state population protocols: Hands down the favorite paper
that came out during my PhD. Check it out for yourself.
Tight space bound for consensus by Zhu. The proof fits in 3 pages and solves a problem that was open for 20+ years.
Space-optimal Test-and-Set: All of the above were lower bounds, so here is what a real upper bound looks like.

Publications


Theses

Bachelor Thesis: Attacks on re-keying and renegotiation in Key Exchange Protocols. 2012, Supervisor: Cas Cremers. [full text]

Master Thesis: Leader election and renaming with optimal message complexity. 2014, Advisor: Nir Shavit. [dspace]

Doctoral Thesis: On the complexity of synchronization. 2017, Advisor: Nir Shavit. [dspace]


Shared Memory

Why Extension-Based Proofs Fail.
D. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu. Unpublished manuscript. [draft]

Space Lower Bounds for the ABA Detection Problem.
F. Ellen, R. Gelashvili, P.Woelfel, L. Zhu. Unpublished manuscript.

Revisionist Simulations: A New Approach to Proving Space Lower Bounds.
F. Ellen, R. Gelashvili, L. Zhu. PODC 2018, London, UK, 2018. [arxiv]

Towards Reduced Instruction Sets for Synchronization.
R. Gelashvili, I. Keidar, A. Spiegelman, R. Wattenhofer. DISC 2017 Brief Announcement, Vienna, Austria, 2017. [arxiv]

A Complexity-Based Hierarchy for Multiprocessor Synchronization.
F. Ellen, R. Gelashvili, N. Shavit, L. Zhu. PODC 2016, Chicago, USA, 2016. [arxiv]

Optimal Space Complexity of Consensus for Anonymous Processes.
R. Gelashvili. DISC 2015, Tokyo, Japan, 2015. [arxiv] Best Paper Award
Journal: Distributed Computing, Special Issue, Vol 31, Issue 4, pp. 317-326, 2018.

On the Importance of Registers for Computability.
R. Gelashvili, M. Ghaffari, J. Li, N. Shavit. OPODIS 2014, Cortina d'Ampezzo, Italy, 2014. [arxiv]

Dynamic Task Allocation in Asynchronous Shared Memory.
D. Alistarh, J. Aspnes, M. A. Bender, R. Gelashvili, S. Gilbert. SODA 2014, Portland, Oregon, 2014. [full text]


Population Protocols

Space-Optimal Majority in Population Protocols.
D. Alistarh, J. Aspnes, R. Gelashvili. SODA 2018, New Orleans, USA, 2018. [arxiv]

Time-Space Trade-offs in Population Protocols.
D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, R. L. Rivest. SODA 2017, Barcelona, Spain, 2017. [arxiv]

Fast and Exact Majority in Population Protocols.
D. Alistarh, R. Gelashvili, M. Vojnovic. PODC 2015, Donostia-San Sebastian, Spain, 2015. [full text]

Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States.
D. Alistarh, R. Gelashvili. ICALP 2015, Kyoto, Japan, 2015. [arxiv]


Message Passing

How to Elect a Leader Faster than a Tournament.
D. Alistarh, R. Gelashvili, A. Vladu. PODC 2015, Donostia-San Sebastian, Spain, 2015. [arxiv]


Other Work

Restricted Isometry Property for General p-Norms.
Z. Allen-Zhu, R. Gelashvili, I. Razenshteyn. SoCG 2015, Eindhoven, Netherlands, 2015.
Journal: IEEE Transactions on Information Theory, Vol. 62, Issue 10, pp. 5839-5854, 2016. [arxiv]

Sparse Sign-Consistent Johnson-Lindenstrauss Matrices: Compression with Neuroscience-Based Constraints.
Z. Allen-Zhu, R. Gelashvili, S. Micali, N. Shavit.
Journal: Proceedings of the national academy of sciences (PNAS), vol 111, no. 47, 2014. [link]

Mining Railway Delay Dependencies in Large-Scale Real-World Delay Data.
H. Flier, R. Gelashvili, T. Graffagnino, M. Nunkesser. Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems. Lecture Notes in Computer Science, Vol. 5868, pp. 354-368, Springer, 2009.