Search Results

Documents authored by Harlev, Noga

Document
DOI: 10.4230/LIPIcs.DISC.2024.22
On the Power of Graphical Reconfigurable Circuits

Authors: Yuval Emek, Yuval Gil, and Noga Harlev

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

Abstract
We introduce the graphical reconfigurable circuits (GRC) model as an abstraction for distributed graph algorithms whose communication scheme is based on local mechanisms that collectively construct long-range reconfigurable channels (this is an extension to general graphs of a distributed computational model recently introduced by Feldmann et al. (JCB 2022) for hexagonal grids). The crux of the GRC model lies in its modest assumptions: (1) the individual nodes are computationally weak, with state space bounded independently of any global graph parameter; and (2) the reconfigurable communication channels are highly restrictive, only carrying information-less signals (a.k.a. beeps). Despite these modest assumptions, we prove that GRC algorithms can solve many important distributed tasks efficiently, i.e., in polylogarithmic time. On the negative side, we establish various runtime lower bounds, proving that for other tasks, GRC algorithms (if they exist) are doomed to be slow.
Cite as

Yuval Emek, Yuval Gil, and Noga Harlev. On the Power of Graphical Reconfigurable Circuits. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2024.22,
  author =	{Emek, Yuval and Gil, Yuval and Harlev, Noga},
  title =	{{On the Power of Graphical Reconfigurable Circuits}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{22:1--22:16},
  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.22},
  URN =		{urn:nbn:de:0030-drops-212487},
  doi =		{10.4230/LIPIcs.DISC.2024.22},
  annote =	{Keywords: graphical reconfigurable circuits, bounded uniformity, beeping}
}
Document
DOI: 10.4230/LIPIcs.DNA.29.3
On the Runtime of Chemical Reaction Networks Beyond Idealized Conditions

Authors: Anne Condon, Yuval Emek, and Noga Harlev

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)

Abstract
This paper studies the (discrete) chemical reaction network (CRN) computational model that emerged in the last two decades as an abstraction for molecular programming. The correctness of CRN protocols is typically established under one of two possible schedulers that determine how the execution advances: (1) a stochastic scheduler that obeys the (continuous time) Markov process dictated by the standard model of stochastic chemical kinetics; or (2) an adversarial scheduler whose only commitment is to maintain a certain fairness condition. The latter scheduler is justified by the fact that the former one crucially assumes "idealized conditions" that more often than not, do not hold in real wet-lab experiments. However, when it comes to analyzing the runtime of CRN protocols, the existing literature focuses strictly on the stochastic scheduler, thus raising the research question that drives this work: Is there a meaningful way to quantify the runtime of CRNs without the idealized conditions assumption? The main conceptual contribution of the current paper is to answer this question in the affirmative, formulating a new runtime measure for CRN protocols that does not rely on idealized conditions. This runtime measure is based on an adapted (weaker) fairness condition as well as a novel scheme that enables partitioning the execution into short rounds and charging the runtime for each round individually (inspired by definitions for the runtime of asynchronous distributed algorithms). Following that, we turn to investigate various fundamental computational tasks and establish (often tight) bounds on the runtime of the corresponding CRN protocols operating under the adversarial scheduler. This includes an almost complete chart of the runtime complexity landscape of predicate decidability tasks.
Cite as

Anne Condon, Yuval Emek, and Noga Harlev. On the Runtime of Chemical Reaction Networks Beyond Idealized Conditions. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{condon_et_al:LIPIcs.DNA.29.3,
  author =	{Condon, Anne and Emek, Yuval and Harlev, Noga},
  title =	{{On the Runtime of Chemical Reaction Networks Beyond Idealized Conditions}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{3:1--3:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.3},
  URN =		{urn:nbn:de:0030-drops-187861},
  doi =		{10.4230/LIPIcs.DNA.29.3},
  annote =	{Keywords: chemical reaction networks, adversarial runtime, weak fairness, predicate decidability}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.27
Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach

Authors: Yuval Emek, Yuval Gil, and Noga Harlev

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Self-stabilization is an important concept in the realm of fault-tolerant distributed computing. In this paper, we propose a new approach that relies on the properties of linear programming duality to obtain self-stabilizing approximation algorithms for distributed graph optimization problems. The power of this new approach is demonstrated by the following results: - A self-stabilizing 2(1+ε)-approximation algorithm for minimum weight vertex cover that converges in O(logΔ /(εlog log Δ)) synchronous rounds. - A self-stabilizing Δ-approximation algorithm for maximum weight independent set that converges in O(Δ+log^* n) synchronous rounds. - A self-stabilizing ((2ρ+1)(1+ε))-approximation algorithm for minimum weight dominating set in ρ-arboricity graphs that converges in O((logΔ)/ε) synchronous rounds. In all of the above, Δ denotes the maximum degree. Our technique improves upon previous results in terms of time complexity while incurring only an additive O(log n) overhead to the message size. In addition, to the best of our knowledge, we provide the first self-stabilizing algorithms for the weighted versions of minimum vertex cover and maximum independent set.
Cite as

Yuval Emek, Yuval Gil, and Noga Harlev. Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.OPODIS.2022.27,
  author =	{Emek, Yuval and Gil, Yuval and Harlev, Noga},
  title =	{{Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.27},
  URN =		{urn:nbn:de:0030-drops-176474},
  doi =		{10.4230/LIPIcs.OPODIS.2022.27},
  annote =	{Keywords: self-stabilization, approximation algorithms, primal-dual}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.32
Towards Distributed Two-Stage Stochastic Optimization

Authors: Yuval Emek, Noga Harlev, and Taisuke Izumi

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
The weighted vertex cover problem is concerned with selecting a subset of the vertices that covers a target set of edges with the objective of minimizing the total cost of the selected vertices. We consider a variant of this classic combinatorial optimization problem where the target edge set is not fully known; rather, it is characterized by a probability distribution. Adhering to the model of two-stage stochastic optimization, the execution is divided into two stages so that in the first stage, the decision maker selects some of the vertices based on the probabilistic forecast of the target edge set. Then, in the second stage, the edges in the target set are revealed and in order to cover them, the decision maker can augment the vertex subset selected in the first stage with additional vertices. However, in the second stage, the vertex cost increases by some inflation factor, so the second stage selection becomes more expensive. The current paper studies the two-stage stochastic vertex cover problem in the realm of distributed graph algorithms, where the decision making process (in both stages) is distributed among the vertices of the graph. By combining the stochastic optimization toolbox with recent advances in distributed algorithms for weighted vertex cover, we develop an algorithm that runs in time O(log (Δ) / ε), sends O(m) messages in total, and guarantees to approximate the optimal solution within a (3 + ε)-ratio, where m is the number of edges in the graph, Δ is its maximum degree, and 0 < ε < 1 is a performance parameter.
Cite as

Yuval Emek, Noga Harlev, and Taisuke Izumi. Towards Distributed Two-Stage Stochastic Optimization. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.OPODIS.2019.32,
  author =	{Emek, Yuval and Harlev, Noga and Izumi, Taisuke},
  title =	{{Towards Distributed Two-Stage Stochastic Optimization}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.32},
  URN =		{urn:nbn:de:0030-drops-118187},
  doi =		{10.4230/LIPIcs.OPODIS.2019.32},
  annote =	{Keywords: weighted vertex cover, distributed graph algorithms, two-stage stochastic optimization, primal-dual}
}
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 About DROPS Imprint Privacy Contact