Leader-based de-anonymization of an anonymous read/write memory

Abstract A new notion of anonymity was recently introduced at PODC 2017, namely, anonymity on the names of the registers that define the shared memory. As an example, a shared register named A by a process p and a shared register named B by another process q may correspond to the very same shared register X, while the same name C may correspond to different shared registers for p and q. Considering an asynchronous n-process anonymous shared memory system, this paper is concerned with the de-anonymization of the memory, i.e., at the end of the execution of a de-anonymization algorithm, the processes must agree on the same name for each shared register, and different shared registers must have different names. To this end, the paper first addresses leader election in an anonymous memory system. Let n be the number of processes and m the size of the anonymous memory (total number of anonymous registers). It is first shown that there is no election algorithm when the number of anonymous registers is a multiple of n. Then, assuming m = α n + β , where α is a positive integer, three election algorithms are presented, which consider the cases β = 1 , β = n − 1 , and β ∈ M ( n ) , where the set M ( n ) characterizes the values for which mutual exclusion can be solved despite memory anonymity. Once election is solved, a general (and simple) de-anonymization algorithm is presented, which takes as a subroutine any memory anonymous leader election algorithm. Hence, any instance of this algorithm works for the values of m required by the selected underlying election algorithm. As the underlying election algorithms, the de-anonymization algorithm is symmetric in the sense that process identities can only be compared for equality.