Anonymity in distributed read/write systems: An introductory survey

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

5 Citations (Scopus)

Abstract

This paper is an algorithmic introduction to anonymity in asynchronous systems where processes communicate by reading and writing atomic read/write registers. Two types of anonymity are investigated: process-anonymity and memory-anonymity. Process-anonymity is when the processes cannot be distinguished the ones from the others (among other features, they do not have identifiers). Memory-anonymity is when the same memory locations can have different names at different processes (e.g., the location name A used by process p i and the location name B used by another process p j can correspond to the very same memory location X, and similarly for the names B at p i and A at p j which correspond to the same memory location Y ≠ X). The paper shows how algorithms can cope with the uncertainty created by these two types of anonymity. To this end, taking examples from the literature, it presents anonymity-tolerant implementations of several concurrent objects, such as snapshot, consensus, and lock, each implementation satisfying a well-defined progress condition (obstruction-freedom, non-blocking, or wait-freedom). This paper must be considered as a short example-driven introductory tutorial on anonymous asynchronous read/write systems.

Original languageEnglish
Title of host publicationNetworked Systems - 6th International Conference, NETYS 2018, Revised Selected Papers
EditorsAndreas Podelski, François Taïani
PublisherSpringer-Verlag
Pages122-140
Number of pages19
ISBN (Print)9783030055288
DOIs
Publication statusPublished - 1 Jan 2019
Event6th International Conference on Networked Systems, NETYS 2018 - Essaouira, Morocco
Duration: 9 May 201811 May 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11028 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Conference on Networked Systems, NETYS 2018
Country/TerritoryMorocco
CityEssaouira
Period9/05/1811/05/18

Keywords

  • Agreement problem
  • Anonymity
  • Anonymous processes
  • Anonymous shared memory
  • Consensus
  • Impossibility
  • Linearization point
  • Lower bound
  • Mutual exclusindon
  • Non-blocking
  • Obstruction-freedom
  • Progress condition
  • Snapshot
  • Wait-freedom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this