License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2019.18
URN: urn:nbn:de:0030-drops-118049
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11804/
Go to the corresponding LIPIcs Volume Portal

Fatourou, Panagiota ; Kallimanis, Nikolaos D. ; Kanellou, Eleni

An Efficient Universal Construction for Large Objects

pdf-format:
LIPIcs-OPODIS-2019-18.pdf (0.6 MB)

Abstract

This paper presents L-UC, a universal construction that efficiently implements dynamic objects of large state in a wait-free manner. The step complexity of L-UC is O(n+kw), where n is the number of processes, k is the interval contention (i.e., the maximum number of active processes during the execution interval of an operation), and w is the worst-case time complexity to perform an operation on the sequential implementation of the simulated object. L-UC efficiently implements objects whose size can change dynamically. It improves upon previous universal constructions either by efficiently handling objects whose state is large and can change dynamically, or by achieving better step complexity.

BibTeX - Entry

@InProceedings{fatourou_et_al:LIPIcs:2020:11804,
  author =	{Panagiota Fatourou and Nikolaos D. Kallimanis and Eleni Kanellou},
  title =	{{An Efficient Universal Construction for Large Objects}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11804},
  URN =		{urn:nbn:de:0030-drops-118049},
  doi =		{10.4230/LIPIcs.OPODIS.2019.18},
  annote =	{Keywords: universal construction, concurrent object, shared memory, simulation, wait-freedom, large object}
}

Keywords: universal construction, concurrent object, shared memory, simulation, wait-freedom, large object
Collection: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Issue Date: 2020
Date of publication: 11.02.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI