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

The notion of an anonymous shared memory (recently introduced in PODC 2017)considers that processes use different names for the same memory location.Hence, there is permanent disagreement on the location names among processes.In this context, the PODC paper presented -among other results- a symmetricdeadlock-free mutual exclusion (mutex) algorithm for two processes and anecessary condition on the size $m$ of the anonymous memory for the existenceof a symmetric deadlock-free mutex algorithm in an $n$-process system. Thiscondition states that $m$ must be greater than $1$ and belong to the set$M(n)=\{m:\forall~\ell:1<\ell\leq n:~\gcd(\ell,m)=1\}$ (symmetric means that,while each process has its own identity, process identities can only becompared with equality).  The present paper answers several open problems related to symmetricdeadlock-free mutual exclusion in an $n$-process system ($n\geq 2$) where theprocesses communicate through $m$ registers. It first presents two algorithms.The first considers that the registers are anonymous read/write atomicregisters and works for any $m$ greater than $1$ and belonging to the set$M(n)$. It thus shows that this condition on $m$ is both necessary andsufficient. The second algorithm considers anonymous read/modify/write atomicregisters. It assumes that $m\in M(n)$. These algorithms differ in their designprinciples and their costs (measured as the number of registers which mustcontain the identity of a process to allow it to enter the critical section).The paper also shows that the condition $m\in M(n)$ is necessary fordeadlock-free mutex on top of anonymous read/modify/write atomic registers. Itfollows that, when $m>1$, $m\in M(n)$ is a tight characterization of the sizeof the anonymous shared memory needed to solve deadlock-free mutex, be theanonymous registers read/write or read/modify/write.

Optimal Memory-Anonymous Symmetric Deadlock-Free Mutual Exclusion