2 Search Results for "Barenboim, Leonid"

Document
DOI: 10.4230/LIPIcs.DISC.2021.10
Deterministic Logarithmic Completeness in the Distributed Sleeping Model

Authors: Leonid Barenboim and Tzalik Maimon

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

Abstract
In this paper we provide a deterministic scheme for solving any decidable problem in the distributed sleeping model. The sleeping model [Valerie King et al., 2011; Soumyottam Chatterjee et al., 2020] is a generalization of the standard message-passing model, with an additional capability of network nodes to enter a sleeping state occasionally. As long as a vertex is in the awake state, it is similar to the standard message-passing setting. However, when a vertex is asleep it cannot receive or send messages in the network nor can it perform internal computations. On the other hand, sleeping rounds do not count towards awake complexity. Awake complexity is the main complexity measurement in this setting, which is the number of awake rounds a vertex spends during an execution. In this paper we devise algorithms with worst-case guarantees on the awake complexity. We devise a deterministic scheme with awake complexity of O(log n) for solving any decidable problem in this model by constructing a structure we call Distributed Layered Tree. This structure turns out to be very powerful in the sleeping model, since it allows one to collect the entire graph information within a constant number of awake rounds. Moreover, we prove that our general technique cannot be improved in this model, by showing that the construction of distributed layered trees itself requires Ω(log n) awake rounds. This is obtained by a reduction from message-complexity lower bounds, which is of independent interest. Furthermore, our scheme also works in the CONGEST setting where we are limited to messages of size at most O(log n) bits. This result is shown for a certain class of problems, which contains problems of great interest in the research of the distributed setting. Examples for problems we can solve under this limitation are leader election, computing exact number of edges and average degree. Another result we obtain in this work is a deterministic scheme for solving any problem from a class of problems, denoted O-LOCAL, in O(log Δ + log^*n) awake rounds. This class contains various well-studied problems, such as MIS and (Δ+1)-vertex-coloring. Our main structure in this case is a tree as well, but is sharply different from a distributed layered tree. In particular, it is constructed in the local memory of each processor, rather than distributively. Nevertheless, it provides an efficient synchronization scheme for problems of the O-LOCAL class.
Cite as

Leonid Barenboim and Tzalik Maimon. Deterministic Logarithmic Completeness in the Distributed Sleeping Model. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{barenboim_et_al:LIPIcs.DISC.2021.10,
  author =	{Barenboim, Leonid and Maimon, Tzalik},
  title =	{{Deterministic Logarithmic Completeness in the Distributed Sleeping Model}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{10:1--10: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.10},
  URN =		{urn:nbn:de:0030-drops-148123},
  doi =		{10.4230/LIPIcs.DISC.2021.10},
  annote =	{Keywords: Distributed Computing, Sleeping Model, Complexity Class}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.32
Secured Distributed Algorithms Without Hardness Assumptions

Authors: Leonid Barenboim and Harel Levin

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

Abstract
We study algorithms in the distributed message-passing model that produce secured output, for an input graph G. Specifically, each vertex computes its part in the output, the entire output is correct, but each vertex cannot discover the output of other vertices, with a certain probability. This is motivated by high-performance processors that are embedded nowadays in a large variety of devices. Furthermore, sensor networks were established to monitor physical areas for scientific research, smart-cities control, and other purposes. In such situations, it no longer makes sense, and in many cases it is not feasible, to leave the whole processing task to a single computer or even a group of central computers. As the extensive research in the distributed algorithms field yielded efficient decentralized algorithms for many classic problems, the discussion about the security of distributed algorithms was somewhat neglected. Nevertheless, many protocols and algorithms were devised in the research area of secure multi-party computation problem (MPC or SMC). However, the notions and terminology of these protocols are quite different than in classic distributed algorithms. As a consequence, the focus in those protocols was to work for every function f at the expense of increasing the round complexity, or the necessity of several computational assumptions. In this work, we present a novel approach, which rather than turning existing algorithms into secure ones, identifies and develops those algorithms that are inherently secure (which means they do not require any further constructions). This approach yields efficient secure algorithms for various locality problems, such as coloring, network decomposition, forest decomposition, and a variety of additional labeling problems. Remarkably, our approach does not require any hardness assumption, but only a private randomness generator in each vertex. This is in contrast to previously known techniques in this setting that are based on public-key encryption schemes.
Cite as

Leonid Barenboim and Harel Levin. Secured Distributed Algorithms Without Hardness Assumptions. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{barenboim_et_al:LIPIcs.OPODIS.2020.32,
  author =	{Barenboim, Leonid and Levin, Harel},
  title =	{{Secured Distributed Algorithms Without Hardness Assumptions}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{32:1--32: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.32},
  URN =		{urn:nbn:de:0030-drops-135171},
  doi =		{10.4230/LIPIcs.OPODIS.2020.32},
  annote =	{Keywords: distributed algorithms, privacy preserving, graph coloring, generic algorithms, multi-party computation}
}
  • Refine by Author
  • 2 Barenboim, Leonid
  • 1 Levin, Harel
  • 1 Maimon, Tzalik

  • Refine by Classification
  • 2 Theory of computation → Distributed algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph coloring
  • 1 Security and privacy → Privacy-preserving protocols

  • Refine by Keyword
  • 1 Complexity Class
  • 1 Distributed Computing
  • 1 Sleeping Model
  • 1 distributed algorithms
  • 1 generic algorithms
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2021

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