DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2017.15

Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms

Authors: Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract

We consider synchronous distributed systems in which processors communicate by shared read- write variables. Processors are anonymous and do not know their number n. The goal is to assign individual names by all the processors to themselves. We develop algorithms that accomplish this for each of the four cases determined by the following independent properties of the model: concurrently attempting to write distinct values into the same shared memory register either is allowed or not, and the number of shared variables either is a constant or it is unbounded. For each such a case, we give a Monte Carlo algorithm that runs in the optimum expected time and uses the expected number of O(n log n) random bits. All our algorithms produce correct output upon termination with probabilities that are 1−n^{−Ω(1)}, which is best possible when terminating almost surely and using O(n log n) random bits.

Cite as

Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo. Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chlebus_et_al:LIPIcs.OPODIS.2017.15,
  author =	{Chlebus, Bogdan S. and De Marco, Gianluca and Talo, Muhammed},
  title =	{{Anonymous  Processors with Synchronous Shared Memory:  Monte Carlo Algorithms}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.15},
  URN =		{urn:nbn:de:0030-drops-86502},
  doi =		{10.4230/LIPIcs.OPODIS.2017.15},
  annote =	{Keywords: anonymous processors, synchrony, shared memory, read-write registers, naming, Monte Carlo algorithms}
}

Search Results

Documents authored by Talo, Muhammed

Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms

Abstract

Cite as

Thanks for your feedback!

Could not send message