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 infrastructure-less highly dynamic networks, computing and performing evenbasic tasks (such as routing and broadcasting) is a very challenging activitydue to the fact that connectivity does not necessarily hold, and the networkmay actually be disconnected at every time instant. Clearly the task ofdesigning protocols for these networks is less difficult if the environmentallows waiting (i.e., it provides the nodes with store-carry-forward-likemechanisms such as local buffering) than if waiting is not feasible. Noquantitative corroborations of this fact exist (e.g., no answer to thequestion: how much easier?). In this paper, we consider these qualitativequestions about dynamic networks, modeled as time-varying (or evolving) graphs,where edges exist only at some times.  We examine the difficulty of the environment in terms of the expressivity ofthe corresponding time-varying graph; that is in terms of the languagegenerated by the feasible journeys in the graph. We prove that the set oflanguages $L_{nowait}$ when no waiting is allowed contains all computablelanguages. On the other end, using algebraic properties of quasi-orders, weprove that $L_{wait}$ is just the family of regular languages. In other words,we prove that, when waiting is no longer forbidden, the power of the acceptingautomaton (difficulty of the environment) drops drastically from being aspowerful as a Turing machine, to becoming that of a Finite-State machine. This(perhaps surprisingly large) gap is a measure of the computational power ofwaiting.  We also study bounded waiting; that is when waiting is allowed at a node onlyfor at most $d$ time units. We prove the negative result that $L_{wait[d]} =L_{nowait}$; that is, the expressivity decreases only if the waiting is finitebut unpredictable (i.e., under the control of the protocol designer and not ofthe environment).

Expressivity of Time-Varying Graphs and the Power of Waiting in Dynamic Networks