research
∙
08/07/2023
Strong Byzantine Agreement with Adaptive Word Complexity
The strong Byzantine agreement (SBA) problem is defined among n processe...
share
research
∙
06/01/2023
Every Bit Counts in Consensus
Consensus enables n processes to agree on a common valid L-bit value, de...
research
∙
02/15/2023
Robust and Listening-Efficient Contention Resolution
This paper shows how to achieve contention resolution on a shared commun...
research
∙
01/12/2023
On the Validity of Consensus
The Byzantine consensus problem involves n processes, out of which t < n...
research
∙
08/19/2022
Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony! [Extended Version]
The Dolev-Reischuk bound says that any deterministic Byzantine consensus...
research
∙
08/11/2022
Smoothed Analysis of Information Spreading in Dynamic Networks
The best known solutions for k-message broadcast in dynamic networks of ...
research
∙
07/24/2022
Contention Resolution for Coded Radio Networks
Randomized backoff protocols, such as exponential backoff, are a powerfu...
research
∙
01/30/2022
OverChain: Building a robust overlay with a blockchain
Blockchains use peer-to-peer networks for disseminating information amon...
research
∙
05/27/2021
On the Complexity of Load Balancing in Dynamic Networks
In the load balancing problem, each node in a network is assigned a load...
research
∙
05/26/2021
Contention Resolution with Predictions
In this paper, we consider contention resolution algorithms that are aug...
research
∙
02/17/2020
How fast can you update your MST? (Dynamic algorithms for cluster computing)
Imagine a large graph that is being processed by a cluster of computers,...
research
∙
08/07/2019
Parallel Finger Search Structures
In this paper we present two versions of a parallel finger structure FS ...
research
∙
04/28/2019
Periodic Bandits and Wireless Network Selection
Bandit-style algorithms have been studied extensively in stochastic and ...
research
∙
02/24/2019
Latency, Capacity, and Distributed MST
Consider the problem of building a minimum-weight spanning tree for a gi...
research
∙
01/23/2019
Cooperation Speeds Surfing: Use Co-Bandit!
In this paper, we explore the benefit of cooperation in adversarial band...
research
∙
01/02/2019
Leader Election in Well-Connected Graphs
In this paper, we look at the problem of randomized leader election in s...
research
∙
09/26/2018
On Bioelectric Algorithms: A Novel Application of Theoretical Computer Science to Core Problems in Developmental Biology
Cellular bioelectricity describes the biological phenomenon in which cel...
research
∙
05/15/2018
Parallel Working-Set Search Structures
In this paper we present two versions of a parallel working-set map on p...
research
∙
03/06/2018
On Simple Back-Off in Complicated Radio Networks
In this paper, we study local and global broadcast in the dual graph mod...
research
∙
02/16/2018
A Reallocation Algorithm for Online Split Packing of Circles
The Split Packing algorithm is an offline algorithm that packs a set of ...
research
∙
12/08/2017