Rati Gelashvili

@ gelash cs.toronto.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.

For the following two years, I worked at NeuralMagic as a
Senior Algorithms Lead (and an Engineering Team Lead).
I was designing and implementing an algorithmically complex,
high-performance system for running neural networks on CPUs.

I continued as a Research Scientist at Novi, focusing on theoretical
foundations of blockchain systems and practical scalability of Diem.

Background
My core expertise (and my PhD topic) 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 post-graduation 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.

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. 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]
ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award 2018