Search Results

Documents authored by Paz, Ami

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.42
Brief Announcement: Solvability of Three-Process General Tasks

Authors: Hagit Attiya, Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
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 solvability of colorless tasks in terms of ℐ, 𝒪 and Δ. Essentially, a colorless task is wait-free solvable if and only if there is a continuous map from the geometric realization of ℐ to that of 𝒪 that respects Δ. This paper makes headway towards providing an analogous characterization for general tasks, which are not necessarily colorless, by concentrating on the case of three-process inputless tasks. Our key contribution is identifying local articulation points as an obstacle for the solvability of general tasks, and defining a topological deformation on the output complex of a task T, which eliminates these points by splitting them, to obtain a new task T', with an adjusted relation Δ' between the input complex ℐ and an output complex 𝒪' without articulation points. We obtain a new characterization of wait-free solvability of three-process general tasks: T is wait-free solvable if and only if there is a continuous map from the geometric realization of ℐ to that of 𝒪' that respects Δ'.
Cite as

Hagit Attiya, Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum. Brief Announcement: Solvability of Three-Process General Tasks. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 42:1-42:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2024.42,
  author =	{Attiya, Hagit and Fraigniaud, Pierre and Paz, Ami and Rajsbaum, Sergio},
  title =	{{Brief Announcement: Solvability of Three-Process General Tasks}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{42:1--42:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.42},
  URN =		{urn:nbn:de:0030-drops-212700},
  doi =		{10.4230/LIPIcs.DISC.2024.42},
  annote =	{Keywords: Wait-free computing, lower bounds, topology}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.47
Brief Announcement: Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structures

Authors: Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
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. Surprisingly, almost all of this work assumes that messages are passed in a complete network, i.e., each process has a direct link to every other process. Set agreement, a relaxed variant of consensus, has also been heavily studied in different settings, yet research on it has also been limited to complete networks. We address this situation by considering consensus and set agreement in general networks, i.e., that can have an arbitrary graph G as their communication graph. We focus on fault-prone networks, where up to t nodes may crash and irrevocably stop communicating, and present upper and lower bounds for such networks. We establish the following collection of results: - The consensus algorithm by [Castañeda et al., 2023] is optimal for all graphs, and not only for symmetric graphs. - This algorithm can be extended to a generic algorithm for k-set agreement, for every k ≥ 1. For k = 1, our generic algorithm coincides with the existing one for consensus. - All these algorithms can be extended to the case where the number t of failures exceeds the connectivity κ of the graph, while the existing consensus algorithm assumed that t < κ.
Cite as

Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz. Brief Announcement: Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structures. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 47:1-47:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2024.47,
  author =	{Fraigniaud, Pierre and Nguyen, Minh Hang and Paz, Ami},
  title =	{{Brief Announcement: Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structures}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{47:1--47:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.47},
  URN =		{urn:nbn:de:0030-drops-212755},
  doi =		{10.4230/LIPIcs.DISC.2024.47},
  annote =	{Keywords: Consensus, set-agreement, fault tolerance, crash failures}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.4
One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks

Authors: Hagit Attiya, Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
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 essence of the seminal round-reduction proof establishing a lower bound on the number of rounds for 3-coloring a cycle (Linial, 1992), and going by backward induction. Second, we consider FLP-style proofs, aiming at capturing the essence of the seminal consensus impossibility proof (Fischer, Lynch, and Paterson, 1985) and using forward induction. We show that despite their very different natures, these two forms of proof are tightly connected. In particular, we show that for every colorless task Π, if there is a round-reduction proof establishing the impossibility of solving Π using wait-free colorless algorithms, then there is an FLP-style proof establishing the same impossibility. For 1-dimensional colorless tasks (for an arbitrarily number n ≥ 2 of processes), we prove that the two proof techniques have exactly the same power, and more importantly, both are complete: if a 1-dimensional colorless task is not wait-free solvable by n ≥ 2 processes, then the impossibility can be proved by both proof techniques. Moreover, a round-reduction proof can be automatically derived, and an FLP-style proof can be automatically generated from it. Finally, we illustrate the use of these two techniques by establishing the impossibility of solving any colorless covering task of arbitrary dimension by wait-free algorithms.
Cite as

Hagit Attiya, Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum. One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2023.4,
  author =	{Attiya, Hagit and Fraigniaud, Pierre and Paz, Ami and Rajsbaum, Sergio},
  title =	{{One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.4},
  URN =		{urn:nbn:de:0030-drops-191304},
  doi =		{10.4230/LIPIcs.DISC.2023.4},
  annote =	{Keywords: Wait-free computing, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.100
The Time Complexity of Consensus Under Oblivious Message Adversaries

Authors: Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
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 𝐃 arbitrarily. In this fundamental model, determining consensus solvability and designing efficient consensus algorithms is surprisingly difficult. Enabled by a decision procedure that is derived from a well-established previous consensus solvability characterization for a given set 𝐃, we study, for the first time, the time complexity of solving consensus in this model: We provide both upper and lower bounds for this time complexity, and also relate it to the number of iterations required by the decision procedure. Among other results, we find that reaching consensus under an oblivious message adversary can take exponentially longer than both deciding consensus solvability and broadcasting the input value of some unknown process to all other processes.
Cite as

Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid. The Time Complexity of Consensus Under Oblivious Message Adversaries. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 100:1-100:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{winkler_et_al:LIPIcs.ITCS.2023.100,
  author =	{Winkler, Kyrill and Paz, Ami and Rincon Galeana, Hugo and Schmid, Stefan and Schmid, Ulrich},
  title =	{{The Time Complexity of Consensus Under Oblivious Message Adversaries}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{100:1--100:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.100},
  URN =		{urn:nbn:de:0030-drops-176030},
  doi =		{10.4230/LIPIcs.ITCS.2023.100},
  annote =	{Keywords: dynamic networks, oblivious message adversaries, consensus, time complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.65
Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs

Authors: Monika Henzinger, Ami Paz, and A. R. Sricharan

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
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 general dynamic graphs, yet graph families that arise in practice often exhibit structural properties that the existing lower bound constructions do not possess. We study three specific graph families that are ubiquitous, namely constant-degree graphs, power-law graphs, and expander graphs, and give the first conditional lower bounds for them. Our results show that even when restricting our attention to one of these graph classes, any algorithm for fundamental graph problems such as distance computation or approximation or maximum matching, cannot simultaneously achieve a sub-polynomial update time and query time. For example, we show that the same lower bounds as for general graphs hold for maximum matching and (s,t)-distance in constant-degree graphs, power-law graphs or expanders. Namely, in an m-edge graph, there exists no dynamic algorithms with both O(m^{1/2 - ε}) update time and O(m^{1 -ε}) query time, for any small ε > 0. Note that for (s,t)-distance the trivial dynamic algorithm achieves an almost matching upper bound of constant update time and O(m) query time. We prove similar bounds for the other graph families and for other fundamental problems such as densest subgraph detection and perfect matching.
Cite as

Monika Henzinger, Ami Paz, and A. R. Sricharan. Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 65:1-65:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ESA.2022.65,
  author =	{Henzinger, Monika and Paz, Ami and Sricharan, A. R.},
  title =	{{Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{65:1--65:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.65},
  URN =		{urn:nbn:de:0030-drops-170035},
  doi =		{10.4230/LIPIcs.ESA.2022.65},
  annote =	{Keywords: Dynamic graph algorithms, Expander graphs, Power-law graphs}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.23
Playing Guess Who with Your Kids

Authors: Ami Paz and Liat Peterfreund

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
Guess who is a two-player search game in which each player chooses a character from a deck of 24 cards, and has to infer the other player’s character by asking yes-no questions. A simple binary search strategy allows the starting player find the opponent’s character by asking 5 questions only, when the opponent is honest. Real-life observations show that in more realistic scenarios, the game is played against adversaries that do not strictly follow the rules, e.g., kids. Such players might decide to answer all questions at once, answer only part of the questions as they do not know the answers to all, and even lie occasionally. We devise strategies for such scenarios using techniques from error-correcting and erasure codes. This connects to a recent line of work on search problems on graphs and trees with unreliable auxiliary information, and could be of independent interest.
Cite as

Ami Paz and Liat Peterfreund. Playing Guess Who with Your Kids. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 23:1-23:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{paz_et_al:LIPIcs.FUN.2022.23,
  author =	{Paz, Ami and Peterfreund, Liat},
  title =	{{Playing Guess Who with Your Kids}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{23:1--23:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.23},
  URN =		{urn:nbn:de:0030-drops-159935},
  doi =		{10.4230/LIPIcs.FUN.2022.23},
  annote =	{Keywords: Guess Who?, Binary Search, Error Correcting Codes, Erasure Codes}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.58
Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model

Authors: Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
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 also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n).
Cite as

Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 58:1-58:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{korhonen_et_al:LIPIcs.DISC.2021.58,
  author =	{Korhonen, Janne H. and Paz, Ami and Rybicki, Joel and Schmid, Stefan and Suomela, Jukka},
  title =	{{Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{58:1--58:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.58},
  URN =		{urn:nbn:de:0030-drops-148609},
  doi =		{10.4230/LIPIcs.DISC.2021.58},
  annote =	{Keywords: Supported LOCAL model, sinkless orientation, round elimination}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.28
Distributed Quantum Proofs for Replicated Data

Authors: Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
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 equality locally, i.e., by having each node consult only nodes in its vicinity. On the other hand, it remains possible to assign certificates to the nodes, so that verifying the consistency of the replicas can be achieved locally. However, we show that, as the replicated data is large, classical certification mechanisms, including distributed Merlin-Arthur protocols, cannot guarantee good completeness and soundness simultaneously, unless they use very large certificates. The main result of this paper is a distributed quantum Merlin-Arthur protocol enabling the nodes to collectively check the consistency of the replicas, based on small certificates, and in a single round of message exchange between neighbors, with short messages. In particular, the certificate-size is logarithmic in the size of the data set, which gives an exponential advantage over classical certification mechanisms. We propose yet another usage of a fundamental quantum primitive, called the SWAP test, in order to show our main result.
Cite as

Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz. Distributed Quantum Proofs for Replicated Data. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.ITCS.2021.28,
  author =	{Fraigniaud, Pierre and Le Gall, Fran\c{c}ois and Nishimura, Harumichi and Paz, Ami},
  title =	{{Distributed Quantum Proofs for Replicated Data}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.28},
  URN =		{urn:nbn:de:0030-drops-135679},
  doi =		{10.4230/LIPIcs.ITCS.2021.28},
  annote =	{Keywords: Quantum Computing, Distributed Network Computing, Algorithmic Aspects of Networks}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.28
Fast Deterministic Algorithms for Highly-Dynamic Networks

Authors: Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
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 its combination of (1) having an O(1) amortized time complexity, (2) using only O(log{n})-bit messages, (3) not posing any restrictions on the dynamic behavior of the environment, (4) being deterministic, (5) having strong guarantees for intermediate solutions, and (6) being applicable for a wide family of tasks. The tasks for which we deduce such an algorithm are maximal matching, (degree+1)-coloring, 2-approximation for minimum weight vertex cover, and maximal independent set (which is the most subtle case). For some of these tasks, node insertions can also be among the allowed topology changes, and for some of them also abrupt node deletions.
Cite as

Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman. Fast Deterministic Algorithms for Highly-Dynamic Networks. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2020.28,
  author =	{Censor-Hillel, Keren and Dafni, Neta and Kolobov, Victor I. and Paz, Ami and Schwartzman, Gregory},
  title =	{{Fast Deterministic Algorithms for Highly-Dynamic Networks}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.28},
  URN =		{urn:nbn:de:0030-drops-135138},
  doi =		{10.4230/LIPIcs.OPODIS.2020.28},
  annote =	{Keywords: dynamic distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.19
Improved Hardness of Approximation of Diameter in the CONGEST Model

Authors: Ofer Grossman, Seri Khoury, and Ami Paz

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We study the problem of approximating the diameter D of an unweighted and undirected n-node graph in the congest model. Through a connection to extremal combinatorics, we show that a (6/11 + ε)-approximation requires Ω(n^{1/6}/log n) rounds, a (4/7 + ε)-approximation requires Ω(n^{1/4}/log n) rounds, and a (3/5 + ε)-approximation requires Ω(n^{1/3}/log n) rounds. These lower bounds are robust in the sense that they hold even against algorithms that are allowed to return an additional small additive error. Prior to our work, only lower bounds for (2/3 + ε)-approximation were known [Frischknecht et al. SODA 2012, Abboud et al. DISC 2016]. Furthermore, we prove that distinguishing graphs of diameter 3 from graphs of diameter 5 requires Ω(n/log n) rounds. This stands in sharp contrast to previous work: while there is an algorithm that returns an estimate ⌊ 2/3D ⌋ ≤ D̃ ≤ D in Õ(√n+D) rounds [Holzer et al. DISC 2014], our lower bound implies that any algorithm for returning an estimate 2/3D ≤ D̃ ≤ D requires ̃Ω(n) rounds.
Cite as

Ofer Grossman, Seri Khoury, and Ami Paz. Improved Hardness of Approximation of Diameter in the CONGEST Model. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{grossman_et_al:LIPIcs.DISC.2020.19,
  author =	{Grossman, Ofer and Khoury, Seri and Paz, Ami},
  title =	{{Improved Hardness of Approximation of Diameter in the CONGEST Model}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.19},
  URN =		{urn:nbn:de:0030-drops-130972},
  doi =		{10.4230/LIPIcs.DISC.2020.19},
  annote =	{Keywords: Distributed graph algorithms, Approximation algorithms, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.36
Models of Smoothing in Dynamic Networks

Authors: Uri Meir, Ami Paz, and Gregory Schwartzman

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Smoothed analysis is a framework suggested for mediating gaps between worst-case and average-case complexities. In a recent work, Dinitz et al. [Distributed Computing, 2018] suggested to use smoothed analysis in order to study dynamic networks. Their aim was to explain the gaps between real-world networks that function well despite being dynamic, and the strong theoretical lower bounds for arbitrary networks. To this end, they introduced a basic model of smoothing in dynamic networks, where an adversary picks a sequence of graphs, representing the topology of the network over time, and then each of these graphs is slightly perturbed in a random manner. The model suggested above is based on a per-round noise, and our aim in this work is to extend it to models of noise more suited for multiple rounds. This is motivated by long-lived networks, where the amount and location of noise may vary over time. To this end, we present several different models of noise. First, we extend the previous model to cases where the amount of noise is very small. Then, we move to more refined models, where the amount of noise can change between different rounds, e.g., as a function of the number of changes the network undergoes. We also study a model where the noise is not arbitrarily spread among the network, but focuses in each round in the areas where changes have occurred. Finally, we study the power of an adaptive adversary, who can choose its actions in accordance with the changes that have occurred so far. We use the flooding problem as a running case-study, presenting very different behaviors under the different models of noise, and analyze the flooding time in different models.
Cite as

Uri Meir, Ami Paz, and Gregory Schwartzman. Models of Smoothing in Dynamic Networks. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.DISC.2020.36,
  author =	{Meir, Uri and Paz, Ami and Schwartzman, Gregory},
  title =	{{Models of Smoothing in Dynamic Networks}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.36},
  URN =		{urn:nbn:de:0030-drops-131145},
  doi =		{10.4230/LIPIcs.DISC.2020.36},
  annote =	{Keywords: Distributed dynamic graph algorithms, Smoothed analysis, Flooding}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.43
Brief Announcement: Distributed Quantum Proofs for Replicated Data

Authors: Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
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 equality locally, i.e., by having each node consult only nodes in its vicinity. On the other hand, it remains possible to assign certificates to the nodes, so that verifying the consistency of the replicas can be achieved locally. However, we show that, as the replicated data is large, classical certification mechanisms, including distributed Merlin-Arthur protocols, cannot guarantee good completeness and soundness simultaneously, unless they use very large certificates. The main result of this paper is a distributed quantum Merlin-Arthur protocol enabling the nodes to collectively check the consistency of the replicas, based on small certificates, and in a single round of message exchange between neighbors, with short messages. In particular, the certificate-size is logarithmic in the size of the data set, which gives an exponential advantage over classical certification mechanisms.
Cite as

Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz. Brief Announcement: Distributed Quantum Proofs for Replicated Data. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2020.43,
  author =	{Fraigniaud, Pierre and Le Gall, Fran\c{c}ois and Nishimura, Harumichi and Paz, Ami},
  title =	{{Brief Announcement: Distributed Quantum Proofs for Replicated Data}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{43:1--43:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.43},
  URN =		{urn:nbn:de:0030-drops-131217},
  doi =		{10.4230/LIPIcs.DISC.2020.43},
  annote =	{Keywords: Quantum Computing, Distributed Network Computing, Algorithmic Aspects of Networks}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.128
The Topology of Local Computing in Networks

Authors: Pierre Fraigniaud and Ami Paz

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Modeling distributed computing in a way enabling the use of formal methods is a challenge that has been approached from different angles, among which two techniques emerged at the turn of the century: protocol complexes, and directed algebraic topology. In both cases, the considered computational model generally assumes communication via shared objects (typically a shared memory consisting of a collection of read-write registers), or message-passing enabling direct communication between any pair of processes. Our paper is concerned with network computing, where the processes are located at the nodes of a network, and communicate by exchanging messages along the edges of that network (only neighboring processes can communicate directly). Applying the topological approach for verification in network computing is a considerable challenge, mainly because the presence of identifiers assigned to the nodes yields protocol complexes whose size grows exponentially with the size of the underlying network. However, many of the problems studied in this context are of local nature, and their definitions do not depend on the identifiers or on the size of the network. We leverage this independence in order to meet the above challenge, and present local protocol complexes, whose sizes do not depend on the size of the network. As an application of the design of "compacted" protocol complexes, we reformulate the celebrated lower bound of Ω(log^*n) rounds for 3-coloring the n-node ring, in the algebraic topology framework.
Cite as

Pierre Fraigniaud and Ami Paz. The Topology of Local Computing in Networks. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 128:1-128:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.ICALP.2020.128,
  author =	{Fraigniaud, Pierre and Paz, Ami},
  title =	{{The Topology of Local Computing in Networks}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{128:1--128:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.128},
  URN =		{urn:nbn:de:0030-drops-125358},
  doi =		{10.4230/LIPIcs.ICALP.2020.128},
  annote =	{Keywords: Distributed computing, distributed graph algorithms, combinatorial topology}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.13
Trade-Offs in Distributed Interactive Proofs

Authors: Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
The study of interactive proofs in the context of distributed network computing is a novel topic, recently introduced by Kol, Oshman, and Saxena [PODC 2018]. In the spirit of sequential interactive proofs theory, we study the power of distributed interactive proofs. This is achieved via a series of results establishing trade-offs between various parameters impacting the power of interactive proofs, including the number of interactions, the certificate size, the communication complexity, and the form of randomness used. Our results also connect distributed interactive proofs with the established field of distributed verification. In general, our results contribute to providing structure to the landscape of distributed interactive proofs.
Cite as

Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz. Trade-Offs in Distributed Interactive Proofs. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{crescenzi_et_al:LIPIcs.DISC.2019.13,
  author =	{Crescenzi, Pierluigi and Fraigniaud, Pierre and Paz, Ami},
  title =	{{Trade-Offs in Distributed Interactive Proofs}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.13},
  URN =		{urn:nbn:de:0030-drops-113202},
  doi =		{10.4230/LIPIcs.DISC.2019.13},
  annote =	{Keywords: Distributed interactive proofs, Distributed verification}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.7
The Sparsest Additive Spanner via Multiple Weighted BFS Trees

Authors: Keren Censor-Hillel, Ami Paz, and Noam Ravid

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
Spanners are fundamental graph structures that sparsify graphs at the cost of small stretch. In particular, in recent years, many sequential algorithms constructing additive all-pairs spanners were designed, providing very sparse small-stretch subgraphs. Remarkably, it was then shown that the known (+6)-spanner constructions are essentially the sparsest possible, that is, larger additive stretch cannot guarantee a sparser spanner, which brought the stretch-sparsity trade-off to its limit. Distributed constructions of spanners are also abundant. However, for additive spanners, while there were algorithms constructing (+2) and (+4)-all-pairs spanners, the sparsest case of (+6)-spanners remained elusive. We remedy this by designing a new sequential algorithm for constructing a (+6)-spanner with the essentially-optimal sparsity of O~(n^{4/3}) edges. We then show a distributed implementation of our algorithm, answering an open problem in [Keren Censor{-}Hillel et al., 2016]. A main ingredient in our distributed algorithm is an efficient construction of multiple weighted BFS trees. A weighted BFS tree is a BFS tree in a weighted graph, that consists of the lightest among all shortest paths from the root to each node. We present a distributed algorithm in the CONGEST model, that constructs multiple weighted BFS trees in |S|+D-1 rounds, where S is the set of sources and D is the diameter of the network graph.
Cite as

Keren Censor-Hillel, Ami Paz, and Noam Ravid. The Sparsest Additive Spanner via Multiple Weighted BFS Trees. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2018.7,
  author =	{Censor-Hillel, Keren and Paz, Ami and Ravid, Noam},
  title =	{{The Sparsest Additive Spanner via Multiple Weighted BFS Trees}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.7},
  URN =		{urn:nbn:de:0030-drops-100676},
  doi =		{10.4230/LIPIcs.OPODIS.2018.7},
  annote =	{Keywords: Distributed graph algorithms, congest model, weighted BFS trees, additive spanners}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.24
Redundancy in Distributed Proofs

Authors: Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Distributed proofs are mechanisms enabling the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g. having a specific diameter), or on data structures distributed over the nodes (e.g. a spanning tree). We consider well known mechanisms consisting of two components: a prover that assigns a certificate to each node, and a distributed algorithm called verifier that is in charge of verifying the distributed proof formed by the collection of all certificates. We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs to establish perfect tradeoffs between the size of the certificate stored at every node, and the number of rounds of the verification protocol.
Cite as

Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry. Redundancy in Distributed Proofs. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{feuilloley_et_al:LIPIcs.DISC.2018.24,
  author =	{Feuilloley, Laurent and Fraigniaud, Pierre and Hirvonen, Juho and Paz, Ami and Perry, Mor},
  title =	{{Redundancy in Distributed Proofs}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.24},
  URN =		{urn:nbn:de:0030-drops-98139},
  doi =		{10.4230/LIPIcs.DISC.2018.24},
  annote =	{Keywords: Distributed verification, Distributed graph algorithms, Proof-labeling schemes, Space-time tradeoffs, Non-determinism}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.10
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model

Authors: Keren Censor-Hillel, Seri Khoury, and Ami Paz

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires a near-quadratic number of rounds in the CONGEST model, as well as any algorithm for computing the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds. Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple linear lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a sub-linear complexity. We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.
Cite as

Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2017.10,
  author =	{Censor-Hillel, Keren and Khoury, Seri and Paz, Ami},
  title =	{{Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.10},
  URN =		{urn:nbn:de:0030-drops-79969},
  doi =		{10.4230/LIPIcs.DISC.2017.10},
  annote =	{Keywords: CONGEST, Lower Bounds, Minimum Vertex Cover, Chromatic Number, Weighted APSP}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact