23 citations · 49 across the 14 of their papers we have counts for
20 papers
Deferred Objects to Enhance Smart Contract Programming with Optimistic Parallel Execution
George Mitenkov, Igor Kabiljo, Zekun Li +6
One of the main bottlenecks of blockchains is smart contract execution. To increase throughput, modern blockchains try to execute transactions in parallel. Unfortunately, however,…
Shoal: Improving DAG-BFT Latency And Robustness
Alexander Spiegelman, Balaji Arun, Rati Gelashvili +1
The Narwhal system is a state-of-the-art Byzantine fault-tolerant scalable architecture that involves constructing a directed acyclic graph (DAG) of messages among a set of validat…
Block-STM: Scaling Blockchain Execution by Turning Ordering Curse to a Performance Blessing
Rati Gelashvili, Alexander Spiegelman, Zhuolun Xiang +5
Block-STM is a parallel execution engine for smart contracts, built around the principles of Software Transactional Memory. Transactions are grouped in blocks, and every execution…
Be Aware of Your Leaders
Shir Cohen, Rati Gelashvili, Lefteris Kokoris Kogias +4
Advances in blockchains have influenced the State-Machine-Replication (SMR) world and many state-of-the-art blockchain-SMR solutions are based on two pillars: Chaining and Leader-r…
Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention
Dan Alistarh, Rati Gelashvili, Giorgi Nadiradze
This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registe…
Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback
Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino +2
Existing committee-based Byzantine state machine replication (SMR) protocols, typically deployed in production blockchains, face a clear trade-off: (1) they either achieve linear c…
Be Prepared When Network Goes Bad: An Asynchronous View-Change Protocol
Rati Gelashvili, Lefteris Kokoris-Kogias, Alexander Spiegelman +1
The popularity of permissioned blockchain systems demands BFT SMR protocols that are efficient under good network conditions (synchrony) and robust under bad network conditions (as…
Fast Graphical Population Protocols
Dan Alistarh, Rati Gelashvili, Joel Rybicki
Let be a graph on nodes. In the stochastic population protocol model, a collection of indistinguishable, resource-limited nodes collectively solve tasks via pairwise in…
L3 Fusion: Fast Transformed Convolutions on CPUs
Rati Gelashvili, Nir Shavit, Aleksandar Zlateski
Fast convolutions via transforms, either Winograd or FFT, had emerged as a preferred way of performing the computation of convolutional layers, as it greatly reduces the number of…
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, Faith Ellen +2
We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using pro…
Revisionist Simulations: A New Approach to Proving Space Lower Bounds
Faith Ellen, Rati Gelashvili, Leqi Zhu
Determining the space complexity of -obstruction-free -set agreement for is an open problem. In -obstruction-free protocols, processes are required to return in…
Towards Reduced Instruction Sets for Synchronization
Rati Gelashvili, Idit Keidar, Alexander Spiegelman +1
Contrary to common belief, a recent work by Ellen, Gelashvili, Shavit, and Zhu has shown that computability does not require multicore architectures to support "strong" synchroniza…
Space-Optimal Majority in Population Protocols
Dan Alistarh, James Aspnes, Rati Gelashvili
Population protocols are a model of distributed computing, in which agents with limited local state interact randomly, and cooperate to collectively compute global predicates.…
A Complexity-Based Hierarchy for Multiprocessor Synchronization
Faith Ellen, Rati Gelashvili, Nir Shavit +1
For many years, Herlihy's elegant computability based Consensus Hierarchy has been our best explanation of the relative power of various types of multiprocessor synchronization obj…
Time-Space Trade-offs in Population Protocols
Dan Alistarh, James Aspnes, David Eisenstat +2
Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational t…
Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States
Dan Alistarh, Rati Gelashvili
Population protocols are networks of finite-state agents, interacting randomly, and updating their states using simple rules. Despite their extreme simplicity, these systems have b…
Johnson-Lindenstrauss Compression with Neuroscience-Based Constraints
Zeyuan Allen-Zhu, Rati Gelashvili, Silvio Micali +1
Johnson-Lindenstrauss (JL) matrices implemented by sparse random synaptic connections are thought to be a prime candidate for how convergent pathways in the brain compress informat…
How to Elect a Leader Faster than a Tournament
Dan Alistarh, Rati Gelashvili, Adrian Vladu
The problem of electing a leader from among contenders is one of the fundamental questions in distributed computing. In its simplest formulation, the task is as follows: given…
On the Importance of Registers for Computability
Rati Gelashvili, Mohsen Ghaffari, Jerry Li +1
All consensus hierarchies in the literature assume that we have, in addition to copies of a given object, an unbounded number of registers. But why do we really need these register…
Restricted Isometry Property for General p-Norms
Zeyuan Allen-Zhu, Rati Gelashvili, Ilya Razenshteyn
The Restricted Isometry Property (RIP) is a fundamental property of a matrix which enables sparse recovery. Informally, an matrix satisfies RIP of order for the $\…