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 propose distributed algorithms for two well-established problems thatoperate efficiently under extremely harsh conditions. Our algorithms achievestate-of-the-art performance in a simple and novel way.  Our algorithm for maximal independent set selection operates on a network ofidentical anonymous processors. The processor at each node has no priorinformation about the network. At each time step, each node can only broadcasta single bit to all its neighbours, or remain silent. Each node can detectwhether one or more neighbours have broadcast, but cannot tell how many of itsneighbours have broadcast, or which ones. We build on recent work of Afek etal. which was inspired by studying the development of a network of cells in thefruit fly~\cite{Afek2011a}. However we incorporate for the first time anotherimportant feature of the biological system: varying the probability value usedat each node based on local feedback from neighbouring nodes. Given any$n$-node network, our algorithm achieves the optimal expected time complexityof $O(\log n)$ rounds and the optimal expected message complexity of $O(1)$single-bit messages broadcast by each node.We also show that the previousapproach, without feedback, cannot achieve better than $\Omega(\log^2 n)$expected time complexity, whatever global scheme is used to choose theprobabilities.  Our algorithm for distributed greedy colouring works under similar harshconditions: each identical node has no prior information about the network, canonly broadcast a single message to all neighbours at each time steprepresenting a desired colour, and can only detect whether at least oneneighbour has broadcast each colour value. We show that our algorithm has anexpected time complexity of $O(\Delta+\log n)$, where $\Delta$ is the maximumdegree of the network, and expected message complexity of $O(1)$ messagesbroadcast by each node.

Feedback from Nature: Simple Randomised Distributed Algorithms for Maximal Independent Set Selection and Greedy Colouring