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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Population protocols are a distributed computing model appropriate fordescribing massive numbers of agents with limited computational power. Apopulation protocol "has an initial leader" if every valid initialconfiguration contains a single agent in a special "leader" state that helps tocoordinate the computation. Although the class of predicates and functionscomputable with probability 1 is the same whether or not there is an initialleader (semilinear functions and predicates), it is not known whether a leaderis necessary for fast computation. Efficient population protocols are generallydefined as those computing in polylogarithmic in $n$ (parallel) time. Weconsider leaderless population protocols, regarding the computation finishedwhen a configuration is reached from which a different output is no longerreachable.  In this setting we show that a wide class of functions and predicatescomputable by population protocols are not efficiently computable (they requireat least linear time to stabilize on a correct answer), nor are some linearfunctions even efficiently approximable. For example, the widely studiedparity, majority, and equality predicates cannot be computed in sublinear time.Moreover, it requires at least linear time for a population protocol even toapproximate any linear function with a coefficient outside of $\mathbb{N}$: forsufficiently small $\gamma > 0$, the output of a sublinear time protocol canstabilize outside the interval $f(m) (1 \pm \gamma)$ on infinitely many inputs$m$. We also show that it requires linear time to exactly compute a wide rangeof semilinear functions (e.g., $f(m)=m$ if $m$ is even and $2m$ if $m$ is odd).  Finally, we show that with a sufficiently large value of $\gamma$, apopulation protocol can approximate any linear $f$ with nonnegative rationalcoefficients, within approximation factor $\gamma$, in $O(\log n)$ time.

Hardness of computing and approximating predicates and functions with leaderless population protocols