BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Leonid Barenboim

Leonid Barenboim appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms

Catalog footprint

What is connected

8works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2021arXiv

Secured Distributed Algorithms Without Hardness Assumptions

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. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributed K-Backup Placement and Applications to Virtual Memory in Real-World Wireless Networks

The Backup Placement problem in networks in the $\mathcal{CONGEST}$ distributed setting considers a network graph $G = (V,E)$, in which the goal of each vertex $v \in V$ is selecting a neighbor, such that the maximum number of vertices in $V$ that select the same vertex is minimized [Halldorsson et al., 2015]. Previous backup placement algorithms suffer from obliviousness to main factors of real-world heterogeneous wireless network. Specifically, there is no consideration of the nodes memory and storage capacities, and no reference to a case in which nodes have different energy capacity, and thus can leave (or join) the network at any time. These parameters are strongly correlated in wireless networks, as the load on different parts of the network can differ greatly, thus requiring more communication, energy, memory and storage. In order to fit the real-world attributes of wireless networks, this work addresses a generalized version of the original problem, namely $K$-Backup Placement, in which each vertex selects $K$ neighbors, for a positive parameter $K$. Our $K$-Backup Placement algorithm terminates within just one round. In addition we suggest two complementary algorithms which employ $K$-Backup-Placement to obtain efficient virtual memory schemes for wireless networks. The first algorithm divides the memory of each node to many small parts. Each vertex is assigned the memories of a large subset of its neighbors. Thus more memory capacity for more vertices is gained, but with much fragmentation. The second algorithm requires greater round-complexity, but produces larger virtual memory for each vertex without any fragmentation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity

We consider coloring problems in the distributed message-passing setting. The previously-known deterministic algorithms for edge-coloring employed at least (2Delta - 1) colors, even though any graph admits an edge-coloring with Delta + 1 colors [V64]. Moreover, the previously-known deterministic algorithms that employed at most O(Delta) colors required superlogarithmic time [B15,BE10,BE11,FHK15]. In the current paper we devise deterministic edge-coloring algorithms that employ only Delta + o(Delta) colors, for a very wide family of graphs. Specifically, as long as the arboricity is a = O(Delta^{1 - ε}), for a constant epsilon > 0, our algorithm computes such a coloring within {polylogarithmic} deterministic time. We also devise significantly improved deterministic edge-coloring algorithms for {general graphs} for a very wide range of parameters. Specifically, for any value $χ$ in the range [4Delta, 2^{o(log Delta)} \cdot Delta], our χ-edge-coloring algorithm has smaller running time than the best previously-known χ-edge-coloring algorithms. Our algorithms are actually much more general, since edge-coloring is equivalent to {vertex-coloring of line graphs.} Our method is applicable to vertex-coloring of the family of graphs with {bounded diversity} that contains line graphs, line graphs of hypergraphs, and many other graphs. Our results are obtained using a novel technique that connects vertices or edges in a certain way that reduces clique size. The resulting structures, which we call {connectors}, can be colored more efficiently than the original graph. Moreover, the color classes constitute simpler subgraphs that can be colored even more efficiently using appropriate connectors. Hence, we recurse until we obtain sufficiently simple structures that are colored directly. We introduce several types of connectors that are useful for various scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Locality of Distributed Symmetry Breaking

Symmetry breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this paper we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes - An MIS algorithm running in $O(\log^2Δ+ 2^{O(\sqrt{\log\log n})})$ time, where $Δ$ is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when $\log n \ll Δ\ll 2^{\sqrt{\log n}}$, and comes close to the $Ω(\log Δ)$ lower bound of Kuhn, Moscibroda, and Wattenhofer. - A maximal matching algorithm running in $O(\logΔ+ \log^4\log n)$ time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on $Δ$ is provably optimal. - A method for reducing symmetry breaking problems in low arboricity/degeneracy graphs to low degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an $O(\sqrt{\log n})$-time maximal matching algorithm for graphs with arboricity up to $2^{\sqrt{\log n}}$ and an $O(\log^{2/3} n)$-time MIS algorithm for graphs with arboricity up to $2^{(\log n)^{1/3}}$. Each of our algorithms is based on a simple, but powerful technique for reducing a randomized symmetry breaking task to a corresponding deterministic one on a poly$(\log n)$-size graph.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Locality of Some NP-Complete Problems

We consider the distributed message-passing {LOCAL} model. In this model a communication network is represented by a graph where vertices host processors, and communication is performed over the edges. Computation proceeds in synchronous rounds. The running time of an algorithm is the number of rounds from the beginning until all vertices terminate. Local computation is free. An algorithm is called {local} if it terminates within a constant number of rounds. The question of what problems can be computed locally was raised by Naor and Stockmayer \cite{NS93} in their seminal paper in STOC'93. Since then the quest for problems with local algorithms, and for problems that cannot be computed locally, has become a central research direction in the field of distributed algorithms \cite{KMW04,KMW10,LOW08,PR01}. We devise the first local algorithm for an {NP-complete} problem. Specifically, our randomized algorithm computes, with high probability, an O(n^{1/2 + epsilon} \cdot chi)-coloring within O(1) rounds, where epsilon > 0 is an arbitrarily small constant, and chi is the chromatic number of the input graph. (This problem was shown to be NP-complete in \cite{Z07}.) On our way to this result we devise a constant-time algorithm for computing (O(1), O(n^{1/2 + epsilon}))-network-decompositions. Network-decompositions were introduced by Awerbuch et al. \cite{AGLP89}, and are very useful for solving various distributed problems. The best previously-known algorithm for network-decomposition has a polylogarithmic running time (but is applicable for a wider range of parameters) \cite{LS93}. We also devise a Delta^{1 + epsilon}-coloring algorithm for graphs with sufficiently large maximum degree Delta that runs within O(1) rounds. It improves the best previously-known result for this family of graphs, which is O(\log-star n) \cite{SW10}.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Deterministic and Energy-Optimal Wireless Synchronization

We consider the problem of clock synchronization in a wireless setting where processors must power-down their radios in order to save energy. Energy efficiency is a central goal in wireless networks, especially if energy resources are severely limited. In the current setting, the problem is to synchronize clocks of $m$ processors that wake up in arbitrary time points, such that the maximum difference between wake up times is bounded by a positive integer $n$, where time intervals are appropriately discretized. Currently, the best-known results for synchronization for single-hop networks of $m$ processors is a randomized algorithm due to \cite{BKO09} of O(\sqrt {n /m} \cdot poly-log(n)) awake times per processor and a lower bound of Omega(\sqrt{n/m}) of the number of awake times needed per processor \cite{BKO09}. The main open question left in their work is to close the poly-log gap between the upper and the lower bound and to de-randomize their probabilistic construction and eliminate error probability. This is exactly what we do in this paper. That is, we show a {deterministic} algorithm with radio use of Theta(\sqrt {n /m}) that never fails. We stress that our upper bound exactly matches the lower bound proven in \cite{BKO09}, up to a small multiplicative constant. Therefore, our algorithm is {optimal} in terms of energy efficiency and completely resolves a long sequence of works in this area. In order to achieve these results we devise a novel {adaptive} technique that determines the times when devices power their radios on and off. In addition, we prove several lower bounds on the energy efficiency of algorithms for {multi-hop networks}. Specifically, we show that any algorithm for multi-hop networks must have radio use of Omega(\sqrt n) per processor.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Deterministic Distributed Vertex Coloring in Polylogarithmic Time

Consider an n-vertex graph G = (V,E) of maximum degree Delta, and suppose that each vertex v \in V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, i.e., it proceeds in discrete rounds. In the distributed vertex coloring problem the objective is to color G with Delta + 1, or slightly more than Delta + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time.) Efficient randomized algorithms for this problem are known for more than twenty years \cite{L86, ABI86}. Specifically, these algorithms produce a (Delta + 1)-coloring within O(log n) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O(Delta^2) colors. This algorithm was devised in a seminal FOCS'87 paper by Linial \cite{L87}. Its running time is O(log^* n). In the same paper Linial asked whether one can color with significantly less than Delta^2 colors in deterministic polylogarithmic time. By now this question of Linial became one of the most central long-standing open questions in this area. In this paper we answer this question in the affirmative, and devise a deterministic algorithm that employs Δ^{1 +o(1)} colors, and runs in polylogarithmic time. Specifically, the running time of our algorithm is O(f(Delta) log Delta log n), for an arbitrarily slow-growing function f(Delta) = ω(1). We can also produce O(Delta^{1 + η})-coloring in O(log Delta log n)-time, for an arbitrarily small constant η> 0, and O(Delta)-coloring in O(Delta^ε log n) time, for an arbitrarily small constant ε> 0.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence

We study the {edge-coloring} problem in the message-passing model of distributed computing. This is one of the most fundamental and well-studied problems in this area. Currently, the best-known deterministic algorithms for (2Delta -1)-edge-coloring requires O(Delta) + log-star n time \cite{PR01}, where Delta is the maximum degree of the input graph. Also, recent results of \cite{BE10} for vertex-coloring imply that one can get an O(Delta)-edge-coloring in O(Delta^{epsilon} \cdot \log n) time, and an O(Delta^{1 + epsilon})-edge-coloring in O(log Delta log n) time, for an arbitrarily small constant epsilon > 0. In this paper we devise a drastically faster deterministic edge-coloring algorithm. Specifically, our algorithm computes an O(Delta)-edge-coloring in O(Delta^{epsilon}) + log-star n time, and an O(Delta^{1 + epsilon})-edge-coloring in O(log Delta) + log-star n time. This result improves the previous state-of-the-art {exponentially} in a wide range of Delta, specifically, for 2^{Omega(\log-star n)} \leq Delta \leq polylog(n). In addition, for small values of Delta our deterministic algorithm outperforms all the existing {randomized} algorithms for this problem. On our way to these results we study the {vertex-coloring} problem on the family of graphs with bounded {neighborhood independence}. This is a large family, which strictly includes line graphs of r-hypergraphs for any r = O(1), and graphs of bounded growth. We devise a very fast deterministic algorithm for vertex-coloring graphs with bounded neighborhood independence. This algorithm directly gives rise to our edge-coloring algorithms, which apply to {general} graphs. Our main technical contribution is a subroutine that computes an O(Delta/p)-defective p-vertex coloring of graphs with bounded neighborhood independence in O(p^2) + \log-star n time, for a parameter p, 1 \leq p \leq Delta.

0 citations0 reviewsNo code linkedOpen access