Author name cluster

Goran Zuzic

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

STOC Conference 2024 Conference Paper

Polylog-Competitive Deterministic Local Routing and Scheduling

Bernhard Haeupler
Shyamal Patel
Antti Roeyskoe
Cliff Stein 0001
Goran Zuzic

This paper addresses point-to-point packet routing in undirected networks, which is the most important communication primitive in most networks. The main result proves the existence of routing tables that deterministically guarantee a polylog-competitive completion-time: In any undirected network, it is possible to give each node simple stateless deterministic local forwarding rules, such that, any adversarially chosen set of packets are delivered as fast as possible, up to polylog factors. All previous routing strategies crucially required randomization for both route selection and packet scheduling. The core technical contribution of this paper is a new local packet scheduling result of independent interest. This scheduling strategy integrates well with recent sparse semi-oblivious path selection strategies. Such strategies deterministically select not one but several candidate paths for each packet and require a global coordinator to know all packets to adaptively select a single good path from those candidates for each packet. Of course, global knowledge of all packets is exactly what local routing tables cannot have. Another challenge is that, even if a single path is selected for each packet, no strategy for scheduling packets along low-congestion paths that is both local and deterministic is known. Our novel scheduling strategy utilizes the fact that every semi-oblivious routing strategy uses only a small (polynomial) subset of candidate routes. It overcomes the issue of global coordination by furthermore being provably robust to adversarial noise. This avoids the issue of having to choose a single path per packet by treating congestion caused by ineffective candidate paths as noise. Beyond more efficient routing tables, our results can be seen as making progress on fundamental questions regarding the importance and power of randomization in network communications and distributed computing. For example, our results imply the first deterministic universally-optimal algorithms in the distributed supported-CONGEST model for many important global distributed tasks, including computing minimum spanning trees, approximate shortest paths, and part-wise aggregates.

Details

STOC Conference 2023 Conference Paper

Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances

Václav Rozhon
Bernhard Haeupler
Anders Martinsson
Christoph Grunau
Goran Zuzic

This paper introduces stronger notions for approximate single-source shortest-path distances and gives simple reductions to compute them from weaker standard notions of approximate distances. Strongly-approximate distances isolate, capture, and address the well-known barriers for using approximate distances algorithmically and their reductions directly address these barriers in a clean and modular manner. The reductions are model-independent and require only log O (1) n black-box approximate distance computations. They apply equally to parallel, distributed, and semi-streaming settings. Strongly (1+ε)-approximate distances are equivalent to exact distances in a (1+ε)-perturbed graph and approximately satisfy the subtractive triangle inequality. In directed graphs, this is sufficient to reduce even exact distance computation to arbitrary (1+ε)-approximate ones.

Details

STOC Conference 2022 Conference Paper

Undirected (1+ ε )-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms

Václav Rozhon
Christoph Grunau
Bernhard Haeupler
Goran Zuzic
Jason Li 0006

This paper presents near-optimal deterministic parallel and distributed algorithms for computing (1+ eps )-approximate single-source shortest paths in any undirected weighted graph. On a high level, we deterministically reduce this and other shortest-path problems to Õ(1) Minor-Aggregations. A Minor-Aggregation computes an aggregate (e.g., max or sum) of node-values for every connected component of some subgraph. Our reduction immediately implies: Optimal deterministic parallel (PRAM) algorithms with Õ(1) depth and near-linear work. Universally-optimal deterministic distributed (CONGEST) algorithms, whenever deterministic Minor-Aggregate algorithms exist. For example, an optimal Õ( hopDiameter G )-round deterministic CONGEST algorithm for excluded-minor networks. Several novel tools developed for the above results are interesting in their own right: A local iterative approach for reducing shortest path computations “up to distance D ” to computing low-diameter decompositions “up to distance D /2”. Compared to the recursive vertex-reduction approach of [Li20], our approach is simpler, suitable for distributed algorithms, and eliminates many derandomization barriers. A simple graph-based Õ(1)-competitive ℓ 1 -oblivious routing based on low-diameter decompositions that can be evaluated in near-linear work. The previous such routing [ZGY+20] was n o (1) -competitive and required n o (1) more work. A deterministic algorithm to round any fractional single-source transshipment flow into an integral tree solution. The first distributed algorithms for computing Eulerian orientations.

Details

SODA Conference 2022 Conference Paper

Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based ℓ 1 -Oblivious Routing

Goran Zuzic
Gramoz Goranci
Mingquan Ye
Bernhard Haeupler
Xiaorui Sun

We provide universally-optimal distributed graph algorithms for (1+ ∊ )-approximate shortest path problems including shortest-path-tree and transshipment. The universal optimality of our algorithms guarantees that, on any n -node network G, our algorithm completes in T · n o (1) rounds whenever a T -round algorithm exists for G. This includes D · n o (1) -round algorithms for any planar or excluded-minor network. Our algorithms never require more than rounds, resulting in the first sub-linear-round distributed algorithm for transshipment. The key technical contribution leading to these results is the first efficient n o (1) -competitive linear ℓ 1 -oblivious routing operator that does not require the use of ℓ 1 -embeddings. Our construction is simple, solely based on low-diameter decompositions, and—in contrast to all known constructions—directly produces an oblivious flow instead of just an approximation of the optimal flow cost. This also has the benefit of simplifying the interaction with Sherman's multiplicative weight framework [SODA'17] in the distributed setting and its subsequent rounding procedures.

Details

STOC Conference 2021 Conference Paper

Hop-constrained oblivious routing

Mohsen Ghaffari 0001
Bernhard Haeupler
Goran Zuzic

We prove the existence of an oblivious routing scheme that is poly (log n )-competitive in terms of ( congestion + dilation ), thus resolving a well-known question in oblivious routing.

Details

STOC Conference 2021 Conference Paper

Tree embeddings for hop-constrained network design

Bernhard Haeupler
D. Ellis Hershkowitz
Goran Zuzic

Network design problems aim to compute low-cost structures such as routes, trees and subgraphs. Often, it is natural and desirable to require that these structures have small hop length or hop diameter. Unfortunately, optimization problems with hop constraints are much harder and less well understood than their hop-unconstrained counterparts. A significant algorithmic barrier in this setting is the fact that hop-constrained distances in graphs are very far from being a metric. We show that, nonetheless, hop-constrained distances can be approximated by distributions over ``partial tree metrics.'' We build this result into a powerful and versatile algorithmic tool which, similarly to classic probabilistic tree embeddings, reduces hop-constrained problems in general graphs to hop-unconstrained problems on trees. We then use this tool to give the first poly-logarithmic bicriteria approximations for the hop-constrained variants of many classic network design problems. These include Steiner forest, group Steiner tree, group Steiner forest, buy-at-bulk network design as well as online and oblivious versions of many of these problems.

Details

STOC Conference 2021 Conference Paper

Universally-optimal distributed algorithms for known topologies

Bernhard Haeupler
David Wajc
Goran Zuzic

Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two questions:

Details

FOCS Conference 2020 Conference Paper

Network Coding Gaps for Completion Times of Multiple Unicasts

Bernhard Haeupler
David Wajc
Goran Zuzic

We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible. The network coding gap specifies how much coding packets together in a network can help compared to the more natural approach of routing. While makespan minimization using routing has been intensely studied for the multiple unicasts problem, no bounds on network coding gaps for this problem are known. We develop new techniques which allow us to upper bound the network coding gap for the makespan of k unicasts, proving this gap is at most polylogarithmic in k. Complementing this result, we show there exist instances of k unicasts for which this coding gap is polylogarithmic in k. Our results also hold for average completion time, and more generally any lp norm of completion times.

Details