7 Search Results for "Patt-Shamir, Boaz"


Document
Packet Forwarding with a Locally Bursty Adversary

Authors: Will Rosenbaum

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
We consider packet forwarding in the adversarial queueing theory (AQT) model introduced by Borodin et al. We introduce a refinement of the AQT (ρ, σ)-bounded adversary, which we call a locally bursty adversary (LBA) that parameterizes injection patterns jointly by edge utilization and packet origin. For constant (O(1)) parameters, the LBA model is strictly more permissive than the (ρ, σ) model. For example, there are injection patterns in the LBA model with constant parameters that can only be realized as (ρ, σ)-bounded injection patterns with ρ + σ = Ω(n) (where n is the network size). We show that the LBA model (unlike the (ρ, σ) model) is closed under packet bundling and discretization operations. Thus, the LBA model allows one to reduce the study of general (uniform) capacity networks and inhomogenous packet sizes to unit capacity networks with homogeneous packets. On the algorithmic side, we focus on information gathering networks - i.e., networks in which all packets share a common destination, and the union of packet routes forms a tree. We show that the Odd-Even Downhill (OED) forwarding protocol described independently by Dobrev et al. and Patt-Shamir and Rosenbaum achieves buffer space usage of O(log n) against all LBAs with constant parameters. OED is a local protocol, but we show that the upper bound is tight even when compared to centralized protocols. Our lower bound for the LBA model is in contrast to the (ρ, σ)-model, where centralized protocols can achieve worst-case buffer space usage O(1) for ρ, σ = O(1), while the O(log n) upper bound for OED is optimal only for local protocols.

Cite as

Will Rosenbaum. Packet Forwarding with a Locally Bursty Adversary. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 34:1-34:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{rosenbaum:LIPIcs.DISC.2022.34,
  author =	{Rosenbaum, Will},
  title =	{{Packet Forwarding with a Locally Bursty Adversary}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{34:1--34:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.34},
  URN =		{urn:nbn:de:0030-drops-172254},
  doi =		{10.4230/LIPIcs.DISC.2022.34},
  annote =	{Keywords: packet forwarding, packet scheduling, adversarial queueing theory, network calculus, odd-even downhill forwarding, locally bursty adversary, local algorithms}
}
Document
Track A: Algorithms, Complexity and Games
Competitive Vertex Recoloring

Authors: Yossi Azar, Chay Machluf, Boaz Patt-Shamir, and Noam Touitou

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of n weighted vertices and a k-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper k-coloring of the vertices. The cost of a recoloring is the sum of weights of vertices whose color changed. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm. We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an O(log n)-competitive deterministic algorithm and an Ω(log n) lower bound on the competitive ratio of randomized algorithms. For (Δ+1)-coloring, we present tight bounds of Θ(Δ) and Θ(logΔ) on the competitive ratios of deterministic and randomized algorithms, respectively (where Δ denotes the maximum degree). We also consider a dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are weighted and the cost of recoloring a vertex is its weight. All our lower bounds hold even in the unweighted case.

Cite as

Yossi Azar, Chay Machluf, Boaz Patt-Shamir, and Noam Touitou. Competitive Vertex Recoloring. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ICALP.2022.13,
  author =	{Azar, Yossi and Machluf, Chay and Patt-Shamir, Boaz and Touitou, Noam},
  title =	{{Competitive Vertex Recoloring}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.13},
  URN =		{urn:nbn:de:0030-drops-163542},
  doi =		{10.4230/LIPIcs.ICALP.2022.13},
  annote =	{Keywords: coloring with recourse, anti-affinity constraints}
}
Document
Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems

Authors: Shiri Antaki, Quanquan C. Liu, and Shay Solomon

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


Abstract
The field of dynamic graph algorithms aims at achieving a thorough understanding of real-world networks whose topology evolves with time. Traditionally, the focus has been on the classic sequential, centralized setting where the main quality measure of an algorithm is its update time, i.e. the time needed to restore the solution after each update. While real-life networks are very often distributed across multiple machines, the fundamental question of finding efficient dynamic, distributed graph algorithms received little attention to date. The goal in this setting is to optimize both the round and message complexities incurred per update step, ideally achieving a message complexity that matches the centralized update time in O(1) (perhaps amortized) rounds. Toward initiating a systematic study of dynamic, distributed algorithms, we study some of the most central symmetry-breaking problems: maximal independent set (MIS), maximal matching/(approx-) maximum cardinality matching (MM/MCM), and (Δ + 1)-vertex coloring. This paper focuses on dynamic, distributed algorithms that are deterministic, and in particular - robust against an adaptive adversary. Most of our focus is on our MIS algorithm, which achieves O (m^{2/3}log² n) amortized messages in O(log² n) amortized rounds in the Congest model. Notably, the amortized message complexity of our algorithm matches the amortized update time of the best-known deterministic centralized MIS algorithm by Gupta and Khan [SOSA'21] up to a polylog n factor. The previous best deterministic distributed MIS algorithm, by Assadi et al. [STOC'18], uses O(m^{3/4}) amortized messages in O(1) amortized rounds, i.e., we achieve a polynomial improvement in the message complexity by a polylog n increase to the round complexity; moreover, the algorithm of Assadi et al. makes an implicit assumption that the network is connected at all times, which seems excessively strong when it comes to dynamic networks. Using techniques similar to the ones we developed for our MIS algorithm, we also provide deterministic algorithms for MM, approximate MCM and (Δ + 1)-vertex coloring whose message complexities match or nearly match the update times of the best centralized algorithms, while having either constant or polylog(n) round complexities.

Cite as

Shiri Antaki, Quanquan C. Liu, and Shay Solomon. Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{antaki_et_al:LIPIcs.ITCS.2022.7,
  author =	{Antaki, Shiri and Liu, Quanquan C. and Solomon, Shay},
  title =	{{Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{7:1--7: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.7},
  URN =		{urn:nbn:de:0030-drops-156039},
  doi =		{10.4230/LIPIcs.ITCS.2022.7},
  annote =	{Keywords: dynamic graph algorithms, distributed algorithms, symmetry breaking problems, maximal independent set, matching, coloring}
}
Document
On the Probe Complexity of Local Computation Algorithms

Authors: Uriel Feige, Boaz Patt-Shamir, and Shai Vardi

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
In the Local Computation Algorithms (LCA) model, the algorithm is asked to compute a part of the output by reading as little as possible from the input. For example, an LCA for coloring a graph is given a vertex name (as a "query"), and it should output the color assigned to that vertex after inquiring about some part of the graph topology using "probes"; all outputs must be consistent with the same coloring. LCAs are useful when the input is huge, and the output as a whole is not needed simultaneously. Most previous work on LCAs was limited to bounded-degree graphs, which seems inevitable because probes are of the form "what vertex is at the other end of edge i of vertex v?". In this work we study LCAs for unbounded-degree graphs. In particular, such LCAs are expected to probe the graph a number of times that is significantly smaller than the maximum, average, or even minimum degree. We show that there are problems that have very efficient LCAs on any graph - specifically, we show that there is an LCA for the weak coloring problem (where a coloring is legal if every vertex has a neighbor with a different color) that uses log^* n+O(1) probes to reply to any query. As another way of dealing with large degrees, we propose a more powerful type of probe which we call a strong probe: given a vertex name, it returns a list of its neighbors. Lower bounds for strong probes are stronger than ones in the edge probe model (which we call weak probes). Our main result in this model is that roughly Omega(sqrt{n}) strong probes are required to compute a maximal matching. Our findings include interesting separations between closely related problems. For weak probes, we show that while weak 3-coloring can be done with probe complexity log^* n+O(1), weak 2-coloring has probe complexity Omega(log n/log log n). For strong probes, our negative result for maximal matching is complemented by an LCA for (1-epsilon)-approximate maximum matching on regular graphs that uses O(1) strong probes, for any constant epsilon>0.

Cite as

Uriel Feige, Boaz Patt-Shamir, and Shai Vardi. On the Probe Complexity of Local Computation Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{feige_et_al:LIPIcs.ICALP.2018.50,
  author =	{Feige, Uriel and Patt-Shamir, Boaz and Vardi, Shai},
  title =	{{On the Probe Complexity of Local Computation Algorithms}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{50:1--50:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.50},
  URN =		{urn:nbn:de:0030-drops-90543},
  doi =		{10.4230/LIPIcs.ICALP.2018.50},
  annote =	{Keywords: Local computation algorithms, sublinear algorithms}
}
Document
Online Scheduling with Interval Conflicts

Authors: Magnus M. Halldorsson, Boaz Patt-Shamir, and Dror Rawitz

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)


Abstract
In the problem of Scheduling with Interval Conflicts, there is a ground set of items indexed by integers, and the input is a collection of conflicts, each containing all the items whose index lies within some interval on the real line. Conflicts arrive in an online fashion. A scheduling algorithm must select, from each conflict, at most one survivor item, and the goal is to maximize the number (or weight) of items that survive all the conflicts they are involved in. We present a centralized deterministic online algorithm whose competitive ratio is O(log sigma), where sigma is the size of the largest conflict. For the distributed setting, we present another deterministic algorithm whose competitive ratio is 2 log sigma, in the special contiguous case, in which the item indices constitute a contiguous interval of integers. Our upper bounds are complemented by two lower bounds: one that shows that even in the contiguous case, all deterministic algorithms (centralized or distributed) have competitive ratio Omega(log sigma), and that in the non-contiguous case, no deterministic oblivious algorithm (i.e., a distributed algorithm that does not use communication) can have a bounded competitive ratio.

Cite as

Magnus M. Halldorsson, Boaz Patt-Shamir, and Dror Rawitz. Online Scheduling with Interval Conflicts. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 472-483, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.STACS.2011.472,
  author =	{Halldorsson, Magnus M. and Patt-Shamir, Boaz and Rawitz, Dror},
  title =	{{Online Scheduling with Interval Conflicts}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{472--483},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.472},
  URN =		{urn:nbn:de:0030-drops-30363},
  doi =		{10.4230/LIPIcs.STACS.2011.472},
  annote =	{Keywords: online scheduling, online set packing, interval conflicts, competitive analysis, compound tasks, distributed algorithms}
}
Document
Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental

Authors: Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)


Abstract
In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (``buying price''), and cost proportional to the duration of the usage (``rental rate''). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best option at any point in time. Multislope Ski Rental is a natural generalization of the classical Ski Rental problem (where the only options are pure rent and pure buy), which is one of the fundamental problems of online computation. The Multislope Ski Rental problem is an abstraction of many problems where online decisions cannot be modeled by just two options, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for Multislope Ski Rental. Our results include the best possible online randomized strategy for any additive instance, where the cost of switching from one option to another is the difference in their buying prices; and an algorithm that produces an $e$-competitive randomized strategy for any (non-additive) instance.

Cite as

Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 503-514, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{lotker_et_al:LIPIcs.STACS.2008.1331,
  author =	{Lotker, Zvi and Patt-Shamir, Boaz and Rawitz, Dror},
  title =	{{Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{503--514},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1331},
  URN =		{urn:nbn:de:0030-drops-13313},
  doi =		{10.4230/LIPIcs.STACS.2008.1331},
  annote =	{Keywords: Competitive analysis, ski rental, randomized algorithms}
}
Document
High Entropy Random Selection Protocols

Authors: Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)


Abstract
We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n - O(1) and has 4log^* n rounds, improving over the protocol of Goldwasser et al. that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n^2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits of communication and yields entropy n- O(log n) and min-entropy n/2 - O(log n). Our protocol achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al., however achieves much higher min-entropy: n/2 - O(log n) versus O(log n). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n -o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.

Cite as

Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir. High Entropy Random Selection Protocols. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{vereshchagin_et_al:DagSemProc.07411.5,
  author =	{Vereshchagin, Nikolai K. and Buhrman, Harry and Cristandl, Matthias and Koucky, Michal and Lotker, Zvi and Patt-Shamir, Boaz},
  title =	{{High Entropy Random Selection Protocols}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.5},
  URN =		{urn:nbn:de:0030-drops-13091},
  doi =		{10.4230/DagSemProc.07411.5},
  annote =	{Keywords: Shannon entropy, Random string ds}
}
  • Refine by Author
  • 5 Patt-Shamir, Boaz
  • 2 Lotker, Zvi
  • 2 Rawitz, Dror
  • 1 Antaki, Shiri
  • 1 Azar, Yossi
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Dynamic graph algorithms
  • 1 Computer systems organization → Cloud computing
  • 1 Networks → Packet scheduling
  • 1 Theory of computation → Distributed computing models
  • Show More...

  • Refine by Keyword
  • 2 distributed algorithms
  • 1 Competitive analysis
  • 1 Local computation algorithms
  • 1 Random string ds
  • 1 Shannon entropy
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 3 2022
  • 2 2008
  • 1 2011
  • 1 2018

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