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

In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study ofdistributed computation in the presence of mobile adversaries which candynamically appear throughout the network. Over the years, this setting hasbeen studied mostly under the assumption that the communication graph isfully-connected. Resilient CONGEST algorithms for general graphs, on the otherhand, are currently known only for the classical static setting, i.e., wherethe set of corrupted edges (or nodes) is fixed throughout the entirecomputation.  We fill this gap by providing round-efficient simulations that translategiven CONGEST algorithms into equivalent algorithms that are resilient against$f$-mobile edge adversaries. Our main results are:  -Perfect-Security with Mobile Eavesdroppers: A translation of any $r$-round$f$-static-secure algorithm into an equivalent $\Theta(f)$-mobile-securealgorithm with $\Theta(r)$ rounds. We also show that the $f$-static-securealgorithms of [Hitron, Parter and Yogev, DISC 2022 & ITCS 2023] can be modifiedinto $f$-mobile-secure algorithms with the same number of rounds.  -Resilience with Mobile Byzantine Adversaries: An $f$-mobile-byzantinesimulation which is based on a decomposition of the graph into low-diameteredge-disjoint spanning trees. This provides us with near-optimal CONGESTcompilers for expander graphs. It also leads to near-optimal compilers in thecongested-clique model against $\Theta(n)$-mobile adversaries. For general$(2f+1)$ edge-connected graphs with $f$-mobile adversary, we almost match thebounds known for the $f$-static setting, when provided a trusted pre-processingphase.  Our results are based on a collection of tools from interactive coding[Gelles, Found. Trends Theor. Comput. Sci. 2017], linear sketches andlow-congestion graph decomposition. The introduced toolkit might have furtherapplications for resilient computation.

Distributed CONGEST Algorithms against Mobile Adversaries