Search Results

Documents authored by Oshman, Rotem

Document
DOI: 10.4230/LIPIcs.DISC.2024.1
Fully Local Succinct Distributed Arguments

Authors: Eden Aldema Tshuva and Rotem Oshman

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

Abstract
Distributed certification is a proof system for detecting illegal network states or improper execution of distributed algorithms. A certification scheme consists of a proving algorithm, which assigns a certificate to each node, and a verification algorithm where nodes use these certificates to decide whether to accept or reject. The system must ensure that all nodes accept if and only if the network is in a legal state, adhering to the principles of completeness and soundness. The main goal is to design a scheme where the verification process is local and the certificates are succinct, while using as efficient as possible proving algorithm. In cryptographic proof systems, the soundness requirement is often relaxed to computational soundness, where soundness is guaranteed only against computationally bounded adversaries. Computationally sound proof systems are called arguments. Recently, Aldema Tshuva, Boyle, Cohen, Moran, and Oshman (TCC 2023) showed that succinct distributed arguments can be used to enable any polynomially bounded distributed algorithm to certify its execution with polylogarithmic-length certificates. However, their approach required a global communication phase, adding O(D) communication rounds in networks of diameter D, which limits its applicability to local algorithms. In this work, we give the first construction of a fully local succinct distributed argument system, where the prover and the verifier are both local. We show that a distributed algorithm that runs in R rounds, has polynomial local computation, and messages of B bits each can be compiled into a self-certifying algorithm that runs in R + polylog(n) rounds and sends messages of size B + polylog(n), with certificates of length polylog(n). This construction has several applications, including self-certification for local algorithms, ongoing certification of long-lived algorithms, and efficient local mending of the certificates when the network changes.
Cite as

Eden Aldema Tshuva and Rotem Oshman. Fully Local Succinct Distributed Arguments. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aldematshuva_et_al:LIPIcs.DISC.2024.1,
  author =	{Aldema Tshuva, Eden and Oshman, Rotem},
  title =	{{Fully Local Succinct Distributed Arguments}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{1:1--1:24},
  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.1},
  URN =		{urn:nbn:de:0030-drops-212662},
  doi =		{10.4230/LIPIcs.DISC.2024.1},
  annote =	{Keywords: distributed certification, proof labeling schemes, SNARG}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.27
On Polynomial Time Local Decision

Authors: Eden Aldema Tshuva and Rotem Oshman

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
The field of distributed local decision studies the power of local network algorithms, where each network can see only its own local neighborhood, and must act based on this restricted information. Traditionally, the nodes of the network are assumed to have unbounded local computation power, and this makes the model incomparable with centralized notions of efficiency, namely, the classes 𝖯 and NP. In this work we seek to bridge this gap by studying local algorithms where the nodes are required to be computationally efficient: we introduce the classes PLD and NPLD of polynomial-time local decision and non-deterministic polynomial-time local decision, respectively, and compare them to the centralized complexity classes 𝖯 and NP, and to the distributed classes LD and NLD, which correspond to local deterministic and non-deterministic decision, respectively. We show that for deterministic algorithms, requiring both computational and distributed efficiency is likely to be more restrictive than either requirement alone: if the nodes do not know the network size, then PLD ⊊ LD ∩ 𝖯 holds unconditionally; if the network size is known to all nodes, then the same separation holds under a widely believed complexity assumption (UP ∩ coUP ≠ 𝖯). However, when nondeterminism is introduced, this distinction vanishes, and NPLD = NLD ∩ NP. To complete the picture, we extend the classes PLD and NPLD into a hierarchy akin to the centralized polynomial hierarchy, and we characterize its connections to the centralized polynomial hierarchy and to the distributed local decision hierarchy of Balliu, D'Angelo, Fraigniaud, and Olivetti.
Cite as

Eden Aldema Tshuva and Rotem Oshman. On Polynomial Time Local Decision. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aldematshuva_et_al:LIPIcs.OPODIS.2023.27,
  author =	{Aldema Tshuva, Eden and Oshman, Rotem},
  title =	{{On Polynomial Time Local Decision}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.27},
  URN =		{urn:nbn:de:0030-drops-195179},
  doi =		{10.4230/LIPIcs.OPODIS.2023.27},
  annote =	{Keywords: Local Decision, Polynomial-Time, LD, NLD}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.DISC.2023
LIPIcs, Volume 281, DISC 2023, Complete Volume

Authors: Rotem Oshman

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

Abstract
LIPIcs, Volume 281, DISC 2023, Complete Volume
Cite as

37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 1-836, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{oshman:LIPIcs.DISC.2023,
  title =	{{LIPIcs, Volume 281, DISC 2023, Complete Volume}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{1--836},
  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},
  URN =		{urn:nbn:de:0030-drops-191258},
  doi =		{10.4230/LIPIcs.DISC.2023},
  annote =	{Keywords: LIPIcs, Volume 281, DISC 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.DISC.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Rotem Oshman

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{oshman:LIPIcs.DISC.2023.0,
  author =	{Oshman, Rotem},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{0:i--0:xx},
  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.0},
  URN =		{urn:nbn:de:0030-drops-191265},
  doi =		{10.4230/LIPIcs.DISC.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.95
The Communication Complexity of Set Intersection Under Product Distributions

Authors: Rotem Oshman and Tal Roth

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We consider a multiparty setting where k parties have private inputs X_1,…,X_k ⊆ [n] and wish to compute the intersection ⋂_{𝓁 =1}^k X_𝓁 of their sets, using as little communication as possible. This task generalizes the well-known problem of set disjointness, where the parties are required only to determine whether the intersection is empty or not. In the worst-case, it is known that the communication complexity of finding the intersection is the same as that of solving set disjointness, regardless of the size of the intersection: the cost of both problems is Ω(n log k + k) bits in the shared blackboard model, and Ω (nk) bits in the coordinator model. In this work we consider a realistic setting where the parties' inputs are independent of one another, that is, the input is drawn from a product distribution. We show that this makes finding the intersection significantly easier than in the worst-case: only Θ̃((n^{1-1/k} (H(S) + 1)^{1/k}) + k) bits of communication are required, where {H}(S) is the Shannon entropy of the intersection S. We also show that the parties do not need to know the exact underlying input distribution; if we are given in advance O(n^{1/k}) samples from the underlying distribution μ, we can learn enough about μ to allow us to compute the intersection of an input drawn from μ using expected communication Θ̃((n^{1-1/k}𝔼[|S|]^{1/k}) + k), where |S| is the size of the intersection.
Cite as

Rotem Oshman and Tal Roth. The Communication Complexity of Set Intersection Under Product Distributions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{oshman_et_al:LIPIcs.ICALP.2023.95,
  author =	{Oshman, Rotem and Roth, Tal},
  title =	{{The Communication Complexity of Set Intersection Under Product Distributions}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{95:1--95:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.95},
  URN =		{urn:nbn:de:0030-drops-181472},
  doi =		{10.4230/LIPIcs.ICALP.2023.95},
  annote =	{Keywords: Communication complexity, intersection, set disjointness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.86
Resilience of 3-Majority Dynamics to Non-Uniform Schedulers

Authors: Uri Meir, Rotem Oshman, Ofer Shayevitz, and Yuval Volkov

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

Abstract
In recent years there has been great interest in networks of passive, computationally-weak nodes, whose interactions are controlled by the outside environment; examples include population protocols, chemical reactions networks (CRNs), DNA computing, and more. Such networks are usually studied under one of two extreme regimes: the schedule of interactions is either assumed to be adversarial, or it is assumed to be chosen uniformly at random. In this paper we study an intermediate regime, where the interaction at each step is chosen from some not-necessarily-uniform distribution: we introduce the definition of a (p,ε)-scheduler, where the distribution that the scheduler chooses at every round can be arbitrary, but it must have 𝓁_p-distance at most ε from the uniform distribution. We ask how far from uniform we can get before the dynamics of the model break down. For simplicity, we focus on the 3-majority dynamics, a type of chemical reaction network where the nodes of the network interact in triplets. Each node initially has an opinion of either 𝖷 or 𝖸, and when a triplet of nodes interact, all three nodes change their opinion to the majority of their three opinions. It is known that under a uniformly random scheduler, if we have an initial gap of Ω(√{n log n}) in favor of one value, then w.h.p. all nodes converge to the majority value within O(n log n) steps. For the 3-majority dynamics, we prove that among all non-uniform schedulers with a given 𝓁_1- or 𝓁_∞-distance to the uniform scheduler, the worst case is a scheduler that creates a partition in the network, disconnecting some nodes from the rest: under any (p,ε)-close scheduler, if the scheduler’s distance from uniform only suffices to disconnect a set of size at most S nodes and we start from a configuration with a gap of Ω(S+√{n log n}) in favor of one value, then we are guaranteed that all but O(S) nodes will convert to the majority value. We also show that creating a partition is not necessary to cause the system to converge to the wrong value, or to fail to converge at all. We believe that our work can serve as a first step towards understanding the resilience of chemical reaction networks and population protocols under non-uniform schedulers.
Cite as

Uri Meir, Rotem Oshman, Ofer Shayevitz, and Yuval Volkov. Resilience of 3-Majority Dynamics to Non-Uniform Schedulers. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 86:1-86:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.ITCS.2023.86,
  author =	{Meir, Uri and Oshman, Rotem and Shayevitz, Ofer and Volkov, Yuval},
  title =	{{Resilience of 3-Majority Dynamics to Non-Uniform Schedulers}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{86:1--86:19},
  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.86},
  URN =		{urn:nbn:de:0030-drops-175895},
  doi =		{10.4230/LIPIcs.ITCS.2023.86},
  annote =	{Keywords: chemical reaction networks, population protocols, randomized scheduler}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.21
Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators

Authors: Orr Fischer, Rotem Oshman, and Dana Shamir

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
In distributed verification, our goal is to verify that the network configuration satisfies some desired property, using pre-computed information stored at each network node. This is formally modeled as a proof labeling scheme (PLS): a prover assigns to each node a certificate, and then the nodes exchange their certificates with their neighbors and decide whether to accept or reject the configuration. Subsequent work has shown that in some specific cases, allowing more rounds of communication - so that nodes can communicate further across the network - can yield shorter certificates, trading off the space required to store the certificate against the time required for verification. Such tradeoffs were previously known for trees, cycles, and grids, or for proof labeling schemes where all nodes receive the same certificate. In this work we show that in large classes of graphs, every one-round PLS can be transformed into a multi-round PLS with shorter certificates. We give two constructions: given a 1-round PLS with certificates of 𝓁 bits, in graphs families with balanced edge separators of size s(n), we construct a t-round PLS with certificates of size Õ(𝓁 ⋅ s(n) / t), and in graph families with an excluded minor and maximum degree Δ, we construct a t-round PLS with certificates of size Õ(𝓁 ⋅ Δ / √t). Our constructions are explicit, and we use erasure codes to exploit the larger neighborhood viewed by each node in a t-round PLS.
Cite as

Orr Fischer, Rotem Oshman, and Dana Shamir. Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.OPODIS.2021.21,
  author =	{Fischer, Orr and Oshman, Rotem and Shamir, Dana},
  title =	{{Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.21},
  URN =		{urn:nbn:de:0030-drops-157969},
  doi =		{10.4230/LIPIcs.OPODIS.2021.21},
  annote =	{Keywords: proof-labeling schemes, space-time tradeoffs, families with excluded minor}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.35
Quantum Distributed Algorithms for Detection of Cliques

Authors: Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The possibilities offered by quantum computing have drawn attention in the distributed computing community recently, with several breakthrough results showing quantum distributed algorithms that run faster than the fastest known classical counterparts, and even separations between the two models. A prime example is the result by Izumi, Le Gall, and Magniez [STACS 2020], who showed that triangle detection by quantum distributed algorithms is easier than triangle listing, while an analogous result is not known in the classical case. In this paper we present a framework for fast quantum distributed clique detection. This improves upon the state-of-the-art for the triangle case, and is also more general, applying to larger clique sizes. Our main technical contribution is a new approach for detecting cliques by encapsulating this as a search task for nodes that can be added to smaller cliques. To extract the best complexities out of our approach, we develop a framework for nested distributed quantum searches, which employ checking procedures that are quantum themselves. Moreover, we show a circuit-complexity barrier on proving a lower bound of the form Ω(n^{3/5+ε}) for K_p-detection for any p ≥ 4, even in the classical (non-quantum) distributed CONGEST setting.
Cite as

Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Quantum Distributed Algorithms for Detection of Cliques. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 35:1-35:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ITCS.2022.35,
  author =	{Censor-Hillel, Keren and Fischer, Orr and Le Gall, Fran\c{c}ois and Leitersdorf, Dean and Oshman, Rotem},
  title =	{{Quantum Distributed Algorithms for Detection of Cliques}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{35:1--35:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.35},
  URN =		{urn:nbn:de:0030-drops-156319},
  doi =		{10.4230/LIPIcs.ITCS.2022.35},
  annote =	{Keywords: distributed graph algorithms, quantum algorithms, cycles, cliques, Congested Clique, CONGEST}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.37
Truthful Information Dissemination in General Asynchronous Networks

Authors: Lior Solodkin and Rotem Oshman

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

Abstract
We give a protocol for information dissemination in asynchronous networks of rational players, where each player may have its own desires and preferences as to the outcome of the protocol, and players may deviate from the protocol if doing so achieves their goals. We show that under minimalistic assumptions, it is possible to solve the information dissemination problem in a truthful manner, such that no participant has an incentive to deviate from the protocol we design. Our protocol works in any asynchronous network, provided the network graph is at least 2-connected. We complement the protocol with two impossibility results, showing that 2-connectivity is necessary, and also that our protocol achieves optimal bit complexity. As an application, we show that truthful information dissemination can be used to implement a certain class of communication equilibria, which are equilibria that are typically reached by interacting with a trusted third party. Recent work has shown that communication equilibria can be implemented in synchronous networks, or in asynchronous, complete networks; we show that in some useful cases, our protocol yields a lightweight mechanism for implementing communication equilibria in any 2-connected asynchronous network.
Cite as

Lior Solodkin and Rotem Oshman. Truthful Information Dissemination in General Asynchronous Networks. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{solodkin_et_al:LIPIcs.DISC.2021.37,
  author =	{Solodkin, Lior and Oshman, Rotem},
  title =	{{Truthful Information Dissemination in General Asynchronous Networks}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{37:1--37:19},
  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.37},
  URN =		{urn:nbn:de:0030-drops-148398},
  doi =		{10.4230/LIPIcs.DISC.2021.37},
  annote =	{Keywords: game theory, asynchronous networks, information dissemination}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2020
LIPIcs, Volume 184, OPODIS 2020, Complete Volume

Authors: Quentin Bramas, Rotem Oshman, and Paolo Romano

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

Abstract
LIPIcs, Volume 184, OPODIS 2020, Complete Volume
Cite as

24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 1-514, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{bramas_et_al:LIPIcs.OPODIS.2020,
  title =	{{LIPIcs, Volume 184, OPODIS 2020, Complete Volume}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{1--514},
  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},
  URN =		{urn:nbn:de:0030-drops-134842},
  doi =		{10.4230/LIPIcs.OPODIS.2020},
  annote =	{Keywords: LIPIcs, Volume 184, OPODIS 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Quentin Bramas, Rotem Oshman, and Paolo Romano

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.OPODIS.2020.0,
  author =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{0:i--0:xvi},
  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.0},
  URN =		{urn:nbn:de:0030-drops-134854},
  doi =		{10.4230/LIPIcs.OPODIS.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.33
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs

Authors: Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman

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

Abstract
In this paper we give fast distributed graph algorithms for detecting and listing small subgraphs, and for computing or approximating the girth. Our algorithms improve upon the state of the art by polynomial factors, and for girth, we obtain a constant-time algorithm for additive +1 approximation in Congested Clique, and the first parametrized algorithm for exact computation in Congest. In the Congested Clique model, we first develop a technique for learning small neighborhoods, and apply it to obtain an O(1)-round algorithm that computes the girth with only an additive +1 error. Next, we introduce a new technique (the partition tree technique) allowing for efficiently listing all copies of any subgraph, which is deterministic and improves upon the state-of the-art for non-dense graphs. We give two concrete applications of the partition tree technique: First we show that for constant k, it is possible to solve C_{2k}-detection in O(1) rounds in the Congested Clique, improving on prior work, which used fast matrix multiplication and thus had polynomial round complexity. Second, we show that in triangle-free graphs, the girth can be exactly computed in time polynomially faster than the best known bounds for general graphs. We remark that no analogous result is currently known for sequential algorithms. In the Congest model, we describe a new approach for finding cycles, and instantiate it in two ways: first, we show a fast parametrized algorithm for girth with round complexity Õ(min{g⋅ n^{1-1/Θ(g)},n}) for any girth g; and second, we show how to find small even-length cycles C_{2k} for k = 3,4,5 in O(n^{1-1/k}) rounds. This is a polynomial improvement upon the previous running times; for example, our C₆-detection algorithm runs in O(n^{2/3}) rounds, compared to O(n^{3/4}) in prior work. Finally, using our improved C₆-freeness algorithm, and the barrier on proving lower bounds on triangle-freeness of Eden et al., we show that improving the current ̃Ω(√n) lower bound for C₆-freeness of Korhonen et al. by any polynomial factor would imply strong circuit complexity lower bounds.
Cite as

Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2020.33,
  author =	{Censor-Hillel, Keren and Fischer, Orr and Gonen, Tzlil and Le Gall, Fran\c{c}ois and Leitersdorf, Dean and Oshman, Rotem},
  title =	{{Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{33:1--33:17},
  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.33},
  URN =		{urn:nbn:de:0030-drops-131115},
  doi =		{10.4230/LIPIcs.DISC.2020.33},
  annote =	{Keywords: distributed graph algorithms, cycles, girth, Congested Clique, CONGEST}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.8
On the Computational Power of Radio Channels

Authors: Mark Braverman, Gillat Kol, Rotem Oshman, and Avishay Tal

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

Abstract
Radio networks can be a challenging platform for which to develop distributed algorithms, because the network nodes must contend for a shared channel. In some cases, though, the shared medium is an advantage rather than a disadvantage: for example, many radio network algorithms cleverly use the shared channel to approximate the degree of a node, or estimate the contention. In this paper we ask how far the inherent power of a shared radio channel goes, and whether it can efficiently compute "classicaly hard" functions such as Majority, Approximate Sum, and Parity. Using techniques from circuit complexity, we show that in many cases, the answer is "no". We show that simple radio channels, such as the beeping model or the channel with collision-detection, can be approximated by a low-degree polynomial, which makes them subject to known lower bounds on functions such as Parity and Majority; we obtain round lower bounds of the form Omega(n^{delta}) on these functions, for delta in (0,1). Next, we use the technique of random restrictions, used to prove AC^0 lower bounds, to prove a tight lower bound of Omega(1/epsilon^2) on computing a (1 +/- epsilon)-approximation to the sum of the nodes' inputs. Our techniques are general, and apply to many types of radio channels studied in the literature.
Cite as

Mark Braverman, Gillat Kol, Rotem Oshman, and Avishay Tal. On the Computational Power of Radio Channels. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.DISC.2019.8,
  author =	{Braverman, Mark and Kol, Gillat and Oshman, Rotem and Tal, Avishay},
  title =	{{On the Computational Power of Radio Channels}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{8:1--8: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.8},
  URN =		{urn:nbn:de:0030-drops-113152},
  doi =		{10.4230/LIPIcs.DISC.2019.8},
  annote =	{Keywords: radio channel, lower bounds, approximate majority}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.15
Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles

Authors: Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman

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

Abstract
In this paper we give sublinear-time distributed algorithms in the CONGEST model for subgraph detection for two classes of graphs: cliques and even-length cycles. We show for the first time that all copies of 4-cliques and 5-cliques in the network graph can be listed in sublinear time, O(n^{5/6+o(1)}) rounds and O(n^{21/22+o(1)}) rounds, respectively. Prior to our work, it was not known whether it was possible to even check if the network contains a 4-clique or a 5-clique in sublinear time. For even-length cycles, C_{2k}, we give an improved sublinear-time algorithm, which exploits a new connection to extremal combinatorics. For example, for 6-cycles we improve the running time from O~(n^{5/6}) to O~(n^{3/4}) rounds. We also show two obstacles on proving lower bounds for C_{2k}-freeness: First, we use the new connection to extremal combinatorics to show that the current lower bound of Omega~(sqrt{n}) rounds for 6-cycle freeness cannot be improved using partition-based reductions from 2-party communication complexity, the technique by which all known lower bounds on subgraph detection have been proven to date. Second, we show that there is some fixed constant delta in (0,1/2) such that for any k, a Omega(n^{1/2+delta}) lower bound on C_{2k}-freeness implies new lower bounds in circuit complexity. For general subgraphs, it was shown in [Orr Fischer et al., 2018] that for any fixed k, there exists a subgraph H of size k such that H-freeness requires Omega~(n^{2-Theta(1/k)}) rounds. It was left as an open problem whether this is tight, or whether some constant-sized subgraph requires truly quadratic time to detect. We show that in fact, for any subgraph H of constant size k, the H-freeness problem can be solved in O(n^{2 - Theta(1/k)}) rounds, nearly matching the lower bound of [Orr Fischer et al., 2018].
Cite as

Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.DISC.2019.15,
  author =	{Eden, Talya and Fiat, Nimrod and Fischer, Orr and Kuhn, Fabian and Oshman, Rotem},
  title =	{{Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{15:1--15:16},
  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.15},
  URN =		{urn:nbn:de:0030-drops-113224},
  doi =		{10.4230/LIPIcs.DISC.2019.15},
  annote =	{Keywords: Distributed Computing, Subgraph Freeness, CONGEST}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.16
A Distributed Algorithm for Directed Minimum-Weight Spanning Tree

Authors: Orr Fischer and Rotem Oshman

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

Abstract
In the directed minimum spanning tree problem (DMST, also called minimum weight arborescence), the network is given a root node r, and needs to construct a minimum-weight directed spanning tree, rooted at r and oriented outwards. In this paper we present the first sub-quadratic DMST algorithms in the distributed CONGEST network model, where the messages exchanged between the network nodes are bounded in size. We consider three versions: a model where the communication links are bidirectional but can have different weights in the two directions; a model where communication is unidirectional; and the Congested Clique model, where all nodes can communicate directly with each other. Our algorithm is based on a variant of Lovász' DMST algorithm for the PRAM model, and uses a distributed single-source shortest-path (SSSP) algorithm for directed graphs as a black box. In the bidirectional CONGEST model, our algorithm has roughly the same running time as the SSSP algorithm; using the state-of-the-art SSSP algorithm, we obtain a running time of O~(min(sqrt{nD},sqrt{n}D^{1/4} + n^{3/5} +D)) rounds for the bidirectional communication case. For the unidirectional communication model we give an O~(n) algorithm, and show that it is nearly optimal. And finally, for the Congested Clique, our algorithm again matches the best known SSSP algorithm: it runs in O~(n^{1/3}) rounds. On the negative side, we adapt an observation of Chechik in the sequential setting to show that in all three models, the DMST problem is at least as hard as the (s,t)-shortest path problem. Thus, in terms of round complexity, distributed DMST lies between single-source shortest path and (s,t)-shortest path.
Cite as

Orr Fischer and Rotem Oshman. A Distributed Algorithm for Directed Minimum-Weight Spanning Tree. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.DISC.2019.16,
  author =	{Fischer, Orr and Oshman, Rotem},
  title =	{{A Distributed Algorithm for Directed Minimum-Weight Spanning Tree}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{16:1--16:16},
  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.16},
  URN =		{urn:nbn:de:0030-drops-113236},
  doi =		{10.4230/LIPIcs.DISC.2019.16},
  annote =	{Keywords: Distributed Computing, Directed Minimum Spanning Tree, Minimum Arborescence, CONGEST}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.40
On the Communication Complexity of Key-Agreement Protocols

Authors: Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, and Amir Yehudayoff

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Key-agreement protocols whose security is proven in the random oracle model are an important alternative to protocols based on public-key cryptography. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but the parties are limited in the number of queries they can make to the oracle. The random oracle serves as an abstraction for black-box access to a symmetric cryptographic primitive, such as a collision resistant hash. Unfortunately, as shown by Impagliazzo and Rudich [STOC '89] and Barak and Mahmoody [Crypto '09], such protocols can only guarantee limited secrecy: the key of any l-query protocol can be revealed by an O(l^2)-query adversary. This quadratic gap between the query complexity of the honest parties and the eavesdropper matches the gap obtained by the Merkle's Puzzles protocol of Merkle [CACM '78]. In this work we tackle a new aspect of key-agreement protocols in the random oracle model: their communication complexity. In Merkle's Puzzles, to obtain secrecy against an eavesdropper that makes roughly l^2 queries, the honest parties need to exchange Omega(l) bits. We show that for protocols with certain natural properties, ones that Merkle's Puzzle has, such high communication is unavoidable. Specifically, this is the case if the honest parties' queries are uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Our proof for the first setting uses a novel reduction from the set-disjointness problem in two-party communication complexity. For the second setting we prove the lower bound directly, using information-theoretic arguments. Understanding the communication complexity of protocols whose security is proven (in the random-oracle model) is an important question in the study of practical protocols. Our results and proof techniques are a first step in this direction.
Cite as

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, and Amir Yehudayoff. On the Communication Complexity of Key-Agreement Protocols. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{haitner_et_al:LIPIcs.ITCS.2019.40,
  author =	{Haitner, Iftach and Mazor, Noam and Oshman, Rotem and Reingold, Omer and Yehudayoff, Amir},
  title =	{{On the Communication Complexity of Key-Agreement Protocols}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.40},
  URN =		{urn:nbn:de:0030-drops-101335},
  doi =		{10.4230/LIPIcs.ITCS.2019.40},
  annote =	{Keywords: key agreement, random oracle, communication complexity, Merkle's puzzles}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.6
Distributed Approximate Maximum Matching in the CONGEST Model

Authors: Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman

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

Abstract
We study distributed algorithms for the maximum matching problem in the CONGEST model, where each message must be bounded in size. We give new deterministic upper bounds, and a new lower bound on the problem. We begin by giving a distributed algorithm that computes an exact maximum (unweighted) matching in bipartite graphs, in O(n log n) rounds. Next, we give a distributed algorithm that approximates the fractional weighted maximum matching problem in general graphs. In a graph with maximum degree at most Delta, the algorithm computes a (1-epsilon)-approximation for the problem in time O(log(Delta W)/epsilon^2), where W is a bound on the ratio between the largest and the smallest edge weight. Next, we show a slightly improved and generalized version of the deterministic rounding algorithm of Fischer [DISC '17]. Given a fractional weighted maximum matching solution of value f for a given graph G, we show that in time O((log^2(Delta)+log^*n)/epsilon), the fractional solution can be turned into an integer solution of value at least (1-epsilon)f for bipartite graphs and (1-epsilon) * (g-1)/g * f for general graphs, where g is the length of the shortest odd cycle of G. Together with the above fractional maximum matching algorithm, this implies a deterministic algorithm that computes a (1-epsilon)* (g-1)/g-approximation for the weighted maximum matching problem in time O(log(Delta W)/epsilon^2 + (log^2(Delta)+log^* n)/epsilon). On the lower-bound front, we show that even for unweighted fractional maximum matching in bipartite graphs, computing an (1 - O(1/sqrt{n}))-approximate solution requires at least Omega~(D+sqrt{n}) rounds in CONGEST. This lower bound requires the introduction of a new 2-party communication problem, for which we prove a tight lower bound.
Cite as

Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. Distributed Approximate Maximum Matching in the CONGEST Model. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.DISC.2018.6,
  author =	{Ahmadi, Mohamad and Kuhn, Fabian and Oshman, Rotem},
  title =	{{Distributed Approximate Maximum Matching in the CONGEST Model}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{6:1--6:17},
  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.6},
  URN =		{urn:nbn:de:0030-drops-97950},
  doi =		{10.4230/LIPIcs.DISC.2018.6},
  annote =	{Keywords: distributed graph algorithms, maximum matching, deterministic rounding, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.6
Lower Bounds for Subgraph Detection in the CONGEST Model

Authors: Tzlil Gonen and Rotem Oshman

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
In the subgraph-freeness problem, we are given a constant-sized graph H, and wish to de- termine whether the network graph contains H as a subgraph or not. Until now, the only lower bounds on subgraph-freeness known for the CONGEST model were for cycles of length greater than 3; here we extend and generalize the cycle lower bound, and obtain polynomial lower bounds for subgraph-freeness in the CONGEST model for two classes of subgraphs. The first class contains any graph obtained by starting from a 2-connected graph H for which we already know a lower bound, and replacing the vertices of H by arbitrary connected graphs. We show that the lower bound on H carries over to the new graph. The second class is constructed by starting from a cycle Ck of length k ≥ 4, and constructing a graph H ̃ from Ck by replacing each edge {i, (i + 1) mod k} of the cycle with a connected graph Hi, subject to some constraints on the graphs H_{0}, . . . , H_{k−1}. In this case we obtain a polynomial lower bound for the new graph H ̃, depending on the size of the shortest cycle in H ̃ passing through the vertices of the original k-cycle.
Cite as

Tzlil Gonen and Rotem Oshman. Lower Bounds for Subgraph Detection in the CONGEST Model. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gonen_et_al:LIPIcs.OPODIS.2017.6,
  author =	{Gonen, Tzlil and Oshman, Rotem},
  title =	{{Lower Bounds for Subgraph Detection in the CONGEST Model}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.6},
  URN =		{urn:nbn:de:0030-drops-86445},
  doi =		{10.4230/LIPIcs.OPODIS.2017.6},
  annote =	{Keywords: subgraph freeness, CONGEST, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.15
Three Notes on Distributed Property Testing

Authors: Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca

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

Abstract
In this paper we present distributed property-testing algorithms for graph properties in the CONGEST model, with emphasis on testing subgraph-freeness. Testing a graph property P means distinguishing graphs G = (V,E) having property P from graphs that are epsilon-far from having it, meaning that epsilon|E| edges must be added or removed from G to obtain a graph satisfying P. We present a series of results, including: - Testing H-freeness in O(1/epsilon) rounds, for any constant-sized graph H containing an edge (u,v) such that any cycle in H contain either u or v (or both). This includes all connected graphs over five vertices except K_5. For triangles, we can do even better when epsilon is not too small. - A deterministic CONGEST protocol determining whether a graph contains a given tree as a subgraph in constant time. - For cliques K_s with s >= 5, we show that K_s-freeness can be tested in O(m^(1/2-1/(s-2)) epsilon^(-1/2-1/(s-2))) rounds, where m is the number of edges in the network graph. - We describe a general procedure for converting epsilon-testers with f(D) rounds, where D denotes the diameter of the graph, to work in O((log n)/epsilon)+f((log n)/epsilon) rounds, where n is the number of processors of the network. We then apply this procedure to obtain an epsilon-tester for testing whether a graph is bipartite and testing whether a graph is cycle-free. Moreover, for cycle-freeness, we obtain a corrector of the graph that locally corrects the graph so that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph in many places in the case that the graph is far from having the property. These protocols extend and improve previous results of [Censor-Hillel et al. 2016] and [Fraigniaud et al. 2016].
Cite as

Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three Notes on Distributed Property Testing. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 15:1-15:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{even_et_al:LIPIcs.DISC.2017.15,
  author =	{Even, Guy and Fischer, Orr and Fraigniaud, Pierre and Gonen, Tzlil and Levi, Reut and Medina, Moti and Montealegre, Pedro and Olivetti, Dennis and Oshman, Rotem and Rapaport, Ivan and Todinca, Ioan},
  title =	{{Three Notes on Distributed Property Testing}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{15:1--15:30},
  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.15},
  URN =		{urn:nbn:de:0030-drops-79847},
  doi =		{10.4230/LIPIcs.DISC.2017.15},
  annote =	{Keywords: Property testing, Property correcting, Distributed algorithms, CONGEST model}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.31
Interactive Compression for Multi-Party Protocol

Authors: Gillat Kol, Rotem Oshman, and Dafna Sadeh

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

Abstract
The field of compression studies the question of how many bits of communication are necessary to convey a given piece of data. For one-way communication between a sender and a receiver, the seminal work of Shannon and Huffman showed that the communication required is characterized by the entropy of the data; in recent years, there has been a great amount of interest in extending this line of research to interactive communication, where instead of a sender and a receiver we have two parties communication back-and-forth. In this paper we initiate the study of interactive compression for distributed multi-player protocols. We consider the classical shared blackboard model, where players take turns speaking, and each player's message is immediately seen by all the other players. We show that in the shared blackboard model with k players, one can compress protocols down to ~O(Ik), where I is the information content of the protocol and k is the number of players. We complement this result with an almost matching lower bound of ~Omega(Ik), which shows that a nearly-linear dependence on the number of players cannot be avoided.
Cite as

Gillat Kol, Rotem Oshman, and Dafna Sadeh. Interactive Compression for Multi-Party Protocol. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kol_et_al:LIPIcs.DISC.2017.31,
  author =	{Kol, Gillat and Oshman, Rotem and Sadeh, Dafna},
  title =	{{Interactive Compression for Multi-Party Protocol}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{31:1--31:15},
  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.31},
  URN =		{urn:nbn:de:0030-drops-80111},
  doi =		{10.4230/LIPIcs.DISC.2017.31},
  annote =	{Keywords: interactive compression, multi-party communication}
}
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