BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Leonid Barenboim

Leonid Barenboim contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
2topics
3close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

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