Ami Paz
YOU?
Author Swipe
View article: Solvability Characterization for General Three-Process Tasks
Solvability Characterization for General Three-Process Tasks Open
International audience
View article: Semi-Streaming Algorithms for Graph Property Certification
Semi-Streaming Algorithms for Graph Property Certification Open
We introduce the {\em certification} of solutions to graph problems when access to the input is restricted. This topic has received a lot of attention in the distributed computing setting, and we introduce it here in the context of \emph{s…
View article: Smoothed Analysis of Dynamic Graph Algorithms
Smoothed Analysis of Dynamic Graph Algorithms Open
Recent years have seen significant progress in the study of dynamic graph algorithms, and most notably, the introduction of strong lower bound techniques for them (e.g., Henzinger, Krinninger, Nanongkai and Saranurak, STOC 2015; Larsen and…
View article: Distributed Non-Interactive Zero-Knowledge Proofs
Distributed Non-Interactive Zero-Knowledge Proofs Open
Distributed certification is a set of mechanisms that allows an all-knowing prover to convince the units of a communication network that the network's state has some desired property, such as being 3-colorable or triangle-free. Classical m…
View article: Lower Bounds for k-Set Agreement in Fault-Prone Networks
Lower Bounds for k-Set Agreement in Fault-Prone Networks Open
We develop a new lower bound for k-set agreement in synchronous message-passing systems connected by an arbitrary directed communication network, where up to t processes may crash. Our result thus generalizes the ⌊t/k⌋ + 1 lower bound for …
View article: A Simple Lower Bound for Set Agreement in Dynamic Networks
A Simple Lower Bound for Set Agreement in Dynamic Networks Open
International audience
View article: $k$-Center Clustering in Distributed Models
$k$-Center Clustering in Distributed Models Open
The $k$-center problem is a central optimization problem with numerous applications for machine learning, data mining, and communication networks. Despite extensive study in various scenarios, it surprisingly has not been thoroughly explor…
View article: The Time Complexity of Consensus Under Oblivious Message Adversaries
The Time Complexity of Consensus Under Oblivious Message Adversaries Open
We study the problem of solving consensus in synchronous directed dynamic networks, in which communication is controlled by an oblivious message adversary that picks the communication graph to be used in a round from a fixed set of graphs …
View article: Brief Announcement: Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structures
Brief Announcement: Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structures Open
Consensus is arguably the most studied problem in distributed computing as a whole, and particularly in distributed message-passing settings. Research on consensus has considered various failure types, memory constraints, and much more. Su…
View article: Brief Announcement: Solvability of Three-Process General Tasks
Brief Announcement: Solvability of Three-Process General Tasks Open
The topological view on distributed computing represents a task T as a relation Δ between the complex ℐ of its inputs and the complex 𝒪 of its outputs. A cornerstone result in the field is an elegant computability characterization of the s…
View article: One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks
One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks Open
The paper compares two generic techniques for deriving lower bounds and impossibility results in distributed computing. First, we prove a speedup theorem (a-la Brandt, 2019), for wait-free colorless algorithms, aiming at capturing the esse…
View article: Topological Characterization of Consensus Solvability in Directed Dynamic Networks
Topological Characterization of Consensus Solvability in Directed Dynamic Networks Open
Consensus is one of the most fundamental problems in distributed computing. This paper studies the consensus problem in a synchronous dynamic directed network, in which communication is controlled by an oblivious message adversary. The que…
View article: Sinkless Orientation Made Simple
Sinkless Orientation Made Simple Open
International audience
View article: The augmentation-speed tradeoff for consistent network updates
The augmentation-speed tradeoff for consistent network updates Open
Emerging software-defined networking technologies enable more adaptive communication infrastructures, allowing for quick reactions to changes in networking requirements by exploiting the workload's temporal structure. However, operating ne…
View article: A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement
A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement Open
We study two fundamental problems of distributed computing, consensus and approximate agreement, through a novel approach for proving lower bounds and impossibility results, that we call the asynchronous speedup theorem. For a given $n$-pr…
View article: Time Complexity of Consensus in Dynamic Networks Under Oblivious Message Adversaries
Time Complexity of Consensus in Dynamic Networks Under Oblivious Message Adversaries Open
Consensus is a most fundamental task in distributed computing. This paper studies the consensus problem for a set of processes connected by a dynamic directed network, in which computation and communication is lock-step synchronous but con…
View article: Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs
Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs Open
A dynamic graph algorithm is a data structure that answers queries about a property of the current graph while supporting graph modifications such as edge insertions and deletions. Prior work has shown strong conditional lower bounds for g…
View article: Smaller Cuts, Higher Lower Bounds
Smaller Cuts, Higher Lower Bounds Open
This article proves strong lower bounds for distributed computing in the congest model, by presenting the bit-gadget : a new technique for constructing graphs with small cuts. The contribution of bit-gadgets is twofold. First, developing c…
View article: Sinkless Orientation Made Simple
Sinkless Orientation Made Simple Open
The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sink…
View article: Sinkless orientation is hard also in the supported LOCAL model.
Sinkless orientation is hard also in the supported LOCAL model. Open
We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires $\Omega(\log n)$ rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollar…
View article: On the Complexity of Weight-Dynamic Network Algorithms
On the Complexity of Weight-Dynamic Network Algorithms Open
While operating communication networks adaptively may improve utilization and performance, frequent adjustments also introduce an algorithmic challenge: the re-optimization of traffic engineering solutions is time-consuming and may limit t…
View article: On the Complexity of Load Balancing in Dynamic Networks
On the Complexity of Load Balancing in Dynamic Networks Open
In the load balancing problem, each node in a network is assigned a load, and the goal is to equally distribute the loads among the nodes, by preforming local load exchanges. While load balancing was extensively studied in static networks,…
View article: Distributed Quantum Proofs for Replicated Data
Distributed Quantum Proofs for Replicated Data Open
This paper tackles the issue of checking that all copies of a large data set replicated at several nodes of a network are identical. The fact that the replicas may be located at distant nodes prevents the system from verifying their equali…
View article: Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model
Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model Open
We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this a…
View article: Fast Deterministic Algorithms for Highly-Dynamic Networks
Fast Deterministic Algorithms for Highly-Dynamic Networks Open
This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which arbitrarily many edge changes may occur in each round. Our algorithm significantly improves upon prior work in it…