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

Ami Paz

Ami Paz 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 AlgorithmsNetworking and Internet ArchitectureSocial and Information Networks

Catalog footprint

What is connected

8works
4topics
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)

preprint2022arXiv

Sinkless Orientation Made Simple

The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is $Ω(\log n)$ in the deterministic LOCAL model and $O(\log \log n)$ in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Time Complexity of Consensus in Dynamic Networks Under Oblivious Message Adversaries

Consensus is a most fundamental task in distributed computing. This paper studies the consensus problem for a set of processes connected by a dynamic directed network, in which computation and communication is lock-step synchronous but controlled by an oblivious message adversary. In this basic model, determining consensus solvability and designing consensus algorithms in the case where it is possible, has been shown to be surprisingly difficult. We present an explicit decision procedure to determine if consensus is possible under a given adversary. This in turn enables us, for the first time, to study the time complexity of consensus in this model. In particular, we derive time complexity upper bounds for consensus solvability both for a centralized decision procedure as well as for solving distributed consensus. We complement these results with time complexity lower bounds. Intriguingly, we find that reaching consensus under an oblivious message adversary can take exponentially longer than broadcasting the input value of some process to all other processes.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Input-Dynamic Distributed Algorithms for Communication Networks

Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic CONGEST model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of $α$ edge label changes arrive, -- how much time as a function of $α$ we need to update an existing solution, and -- how much information the nodes have to keep in local memory between batches in order to update the solution quickly. Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Redundancy in Distributed Proofs

Distributed proofs are mechanisms enabling the nodes of a network to collectivity and efficiently check the correctness of Boolean predicates on the structure of the network, or on data-structures distributed over the nodes (e.g., spanning trees or routing tables). We consider mechanisms consisting of two components: a \emph{prover} assigning a \emph{certificate} to each node, and a distributed algorithm called \emph{verifier} that is in charge of verifying the distributed proof formed by the collection of all certificates. In this paper, we show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs for establishing perfect tradeoffs between the \emph{size of the certificate} stored at every node, and the \emph{number of rounds} of the verification protocol. If we allow every node to communicate to distance at most $t$, one might expect that the certificate sizes can be reduced by a multiplicative factor of at least~$t$. In trees, cycles and grids, we show that such tradeoffs can be established for \emph{all} network predicates, i.e., it is always possible to linearly decrease the certificate size. In arbitrary graphs, we show that any part of the certificates common to all nodes can be evenly redistributed among these nodes, achieving even a better tradeoff: this common part of the certificate can be reduced by the size of a smallest ball of radius $t$ in the network. In addition to these general results, we establish several upper and lower bounds on the certificate sizes used for distributed proofs for spanning trees, minimum-weight spanning trees, diameter, additive and multiplicative spanners, and more, improving and generalizing previous results from the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simple and Fast Distributed Computation of Betweenness Centrality

Betweenness centrality is a graph parameter that has been successfully applied to network analysis. In the context of computer networks, it was considered for various objectives, ranging from routing to service placement. However, as observed by Maccari et al. [INFOCOM 2018], research on betweenness centrality for improving protocols was hampered by the lack of a usable, fully distributed algorithm for computing this parameter. We resolve this issue by designing an efficient algorithm for computing betweenness centrality, which can be implemented by minimal modifications to any distance-vector routing protocol based on Bellman-Ford. The convergence time of our implementation is shown to be proportional to the diameter of the network

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Sparsest Additive Spanner via Multiple Weighted BFS Trees

Spanners are fundamental graph structures that sparsify graphs at the cost of small stretch. In particular, in recent years, many sequential algorithms constructing additive all-pairs spanners were designed, providing very sparse small-stretch subgraphs. Remarkably, it was then shown that the known (+6)-spanner constructions are essentially the sparsest possible, that is, a larger additive stretch cannot guarantee a sparser spanner, which brought the stretch-sparsity trade-off to its limit. Distributed constructions of spanners are also abundant. However, for additive spanners, while there were algorithms constructing (+2) and (+4)-all-pairs spanners, the sparsest case of (+6)-spanners remained elusive. We remedy this by designing a new sequential algorithm for constructing a (+6)-spanner with the essentially-optimal sparsity of roughly O(n^{4/3}) edges. We then show a distributed implementation of our algorithm, answering an open problem in [Censor-Hillel et al., DISC 2016]. A main ingredient in our distributed algorithm is an efficient construction of multiple weighted BFS trees. A weighted BFS tree is a BFS tree in a weighted graph, that consists of the lightest among all shortest paths from the root to each node. We present a distributed algorithm in the CONGEST model, that constructs multiple weighted BFS trees in |S|+D-1 rounds, where S is the set of sources and D is the diameter of the network graph.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distributed Construction of Purely Additive Spanners

This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need to simultaneously make decisions at far apart locations, the algorithms use additional mechanisms compared to their sequential counterparts. We complement our algorithms with a lower bound on the number of rounds required for computing pairwise spanners. The standard reductions from set-disjointness and equality seem unsuitable for this task because no specific edge needs to be removed from the graph. Instead, to obtain our lower bound, we define a new communication complexity problem that reduces to computing a sparse spanner, and prove a lower bound on its communication complexity using information theory. This technique significantly extends the current toolbox used for obtaining lower bounds for the CONGEST model, and we believe it may find additional applications.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computing Exact Distances in the Congested Clique

This paper gives simple distributed algorithms for the fundamental problem of computing graph distances in the Congested Clique model. One of the main components of our algorithms is fast matrix multiplication, for which we show an $O(n^{1/3})$-round algorithm when the multiplication needs to be performed over a semi-ring, and an $O(n^{0.157})$-round algorithm when the computation can be performed over a field. We propose to denote by $κ$ the exponent of matrix multiplication in this model, which gives $κ< 0.157$. We show how to compute all-pairs-shortest-paths (APSP) in $O(n^{1/3}\log{n})$ rounds in weighted graphs of $n$ nodes, implying also the computation of the graph diameter $D$. In unweighted graphs, APSP can be computed in $O(\min\{n^{1/3}\log{D},n^κ D\})$ rounds, and the diameter can be computed in $O(n^κ\log{D})$ rounds. Furthermore, we show how to compute the girth of a graph in $O(n^{1/3})$ rounds, and provide triangle detection and 4-cycle detection algorithms that complete in $O(n^κ)$ rounds. All our algorithms are deterministic. Our triangle detection and 4-cycle detection algorithms improve upon the previously best known algorithms in this model, and refute a conjecture that $\tilde Ω(n^{1/3})$ rounds are required for detecting triangles by any deterministic oblivious algorithm. Our distance computation algorithms are exact, and improve upon the previously best known $\tilde O(n^{1/2})$ algorithm of Nanongkai [STOC 2014] for computing a $(2+o(1))$-approximation of APSP. Finally, we give lower bounds that match the above for natural families of algorithms. For the Congested Clique Broadcast model, we derive unconditioned lower bounds for matrix multiplication and APSP. The matrix multiplication algorithms and lower bounds are adapted from parallel computations, which is a connection of independent interest.

0 citations0 reviewsNo code linkedOpen access