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.
I was designing and implementing an algorithmically complex,
high-performance system for running neural networks on CPUs.

I am now a research scientist at Novi, working on a blockchain system
(consensus, other distributed algorithmic aspects, performance).

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.


A list of some of my favorite papers.


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.



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