Publications by Dan Alistarh | EPFL Graph Search

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual ...

One of the key trends in computing over the past two decades has been increased distribution, both at the processor level, where multi-core architectures are now the norm, and at the system level, where many key services are currently distributed overmulti ...

As the size and complexity of models and datasets grow, so does the need for communication-efficient variants of stochastic gradient descent that can be deployed to perform parallel model training. One popular communication-compression method for data-para ...

This paper studies non-cryptographic authenticated broad- cast in radio networks subject to malicious failures. We in- troduce two protocols that address this problem. The first, NeighborWatchRB, makes use of a novel strategy in which honest devices monito ...

Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal ...

We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of

n

processes with step complexity $ ...

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Omega(k) process steps for deterministic renaming into ...

Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key buildi ...

Modern deep neural networks exhibit heterogeneity across numerous layers of various types such as residuals, multi-head attention, etc., due to varying structures (dimensions, activation functions, etc.), distinct representation characteristics, which impa ...

A randomized implementation is given of a test-and-set register with O(log log it) individual step complexity and O(n) total step complexity against an oblivious adversary. The implementation is linearizable and multi-shot, and shows an exponential complex ...

Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficien ...

Renaming is a fundamental problem in distributed computing, in which a set of n processes need to pick unique names from a namespace of limited size. In this paper, we present the first early-deciding upper bounds for synchronous renaming, in which the run ...

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write ...

This paper addresses the following question: what is the minimum-sized synchronous window needed to solve consensus in an otherwise asynchronous system? In answer to this question, we present the first optimally-resilient algorithm ASAP that solves consens ...

Dan Alistarh

Chat with Graph Search

Tight Bounds for Asynchronous Renaming

Randomized versus Deterministic Implementations of Concurrent Data Structures

NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization

Securing Every Bit: Authenticated Broadcast in Radio Networks

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

The Complexity of Renaming

How to Allocate Tasks Asynchronously

Layer-wise Quantization for Quantized Optimistic Dual Averaging

Sub-Logarithmic Test-and-Set Against a Weak Adversary

Generating Fast Indulgent Algorithms

Generating Fast Indulgent Algorithms

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

Early Deciding Synchronous Renaming in O( logf ) Rounds or Less

Fast Randomized Test-and-Set and Renaming

How to solve consensus in the smallest window of synchrony