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

A drawback of the classic approach for complexity analysis of distributedgraph problems is that it mostly informs about the complexity of notoriousclasses of ``worst case'' graphs. Algorithms that are used to prove a tight(existential) bound are essentially optimized to perform well on such worstcase graphs. However, such graphs are often either unlikely or actively avoidedin practice, where benign graph instances usually admit much faster solutions.  To circumnavigate these drawbacks, the concept of universal complexityanalysis in the distributed setting was suggested by [Kutten and Peleg,PODC'95] and actively pursued by [Haeupler et al., STOC'21]. Here, the aim isto gauge the complexity of a distributed graph problem depending on the givengraph instance. The challenge is to identify and understand the graph propertythat allows to accurately quantify the complexity of a distributed problem on agiven graph.  In the present work, we consider distributed shortest paths problems in theHYBRID model of distributed computing, where nodes have simultaneous access totwo different modes of communication: one is restricted by locality and theother is restricted by congestion. We identify the graph parameter ofneighborhood quality and show that it accurately describes a universal boundfor the complexity of certain class of shortest paths problems in the HYBRIDmodel.

Towards Universally Optimal Shortest Paths Algorithms in the Hybrid Model