English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the Backup Placement problem in networks in the $\mathcal{CONGEST}$ distributed setting. Given a network graph $G = (V,E)$, 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. The backup placement problem was introduced by Halldorsson, Kohler, Patt-Shamir, and Rawitz, who obtained an $O(\log n/ \log \log n)$ approximation with randomized polylogarithmic time. Their algorithm remained the state-of-the-art for general graphs, as well as specific graph topologies. In this paper we obtain significantly improved algorithms for various graph topologies. Specifically, we show that $O(1)$-approximation to optimal backup placement can be computed deterministically in $O(1)$ rounds in graphs that model wireless networks, certain social networks, claw-free graphs, and more generally, in any graph with neighborhood independence bounded by a constant. At the other end, we consider sparse graphs, such as trees, forests, planar graphs and graphs of constant arboricity, and obtain a constant approximation to optimal backup placement in $O(\log n)$ deterministic rounds. Clearly, our constant-time algorithms for graphs with constant neighborhood independence are asymptotically optimal. Moreover, we show that our algorithms for sparse graphs are not far from optimal as well, by proving several lower bounds. Specifically, optimal backup placement of unoriented trees requires $\Omega(\log n)$ time, and approximate backup placement with a polylogarithmic approximation factor requires $\Omega(\sqrt {\log n / \log \log n})$ time. Our results extend the knowledge regarding the question of "what can be computed locally?", and reveal surprising gaps between complexities of distributed symmetry breaking problems.

Fast Distributed Backup Placement in Sparse and Dense Networks