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/

Zendy Plus

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

Zendy Tools

Zendy Open

The problem of dispersion of mobile robots on a graph asks that $n$ robotsinitially placed arbitrarily on the nodes of an $n$-node anonymous graph,autonomously move to reach a final configuration where exactly each node has atmost one robot on it. This problem is of significant interest due to itsrelationship to other fundamental robot coordination problems, such asexploration, scattering, load balancing, relocation of self-driving electriccars to recharge stations, etc. The robots have unique IDs, typically in therange $[1,poly(n)]$ and limited memory, whereas the graph is anonymous, i.e.,the nodes do not have identifiers. The objective is to simultaneously minimizetwo performance metrics: (i) time to achieve dispersion and (ii) memoryrequirement at each robot. This problem has been relatively well-studied whenrobots are non-faulty.  In this paper, we introduce the notion of Byzantine faults to this problem,i.e., we formalize the problem of dispersion in the presence of up to $f$Byzantine robots. We then study the problem on a ring while simultaneouslyoptimizing the time complexity of algorithms and the memory requirement perrobot. Specifically, we design deterministic algorithms that attempt to matchthe time lower bound ($\Omega(n)$ rounds) and memory lower bound ($\Omega(\logn)$ bits per robot).  Our main result is a deterministic algorithm that is both time and memoryoptimal, i.e., $O(n)$ rounds and $O(\log n)$ bits of memory required per robot,subject to certain constraints. We subsequently provide results that requireless assumptions but are either only time or memory optimal but not both. Wealso provide a primitive, utilized often, that takes robots initially gatheredat a node of the ring and disperses them in a time and memory optimal mannerwithout additional assumptions required.

Efficient Dispersion on an Anonymous Ring in the Presence of Weak Byzantine Robots