License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.34
URN: urn:nbn:de:0030-drops-191609
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19160/
Go to the corresponding LIPIcs Volume Portal

Tran, Anh ; Talmage, Edward

Improved and Partially-Tight Lower Bounds for Message-Passing Implementations of Multiplicity Queues

pdf-format:
LIPIcs-DISC-2023-34.pdf (0.6 MB)

Abstract

A multiplicity queue is a concurrently-defined data type which relaxes the conditions of a linearizable FIFO queue to allow concurrent Dequeue instances to return the same value. It would seem that this should allow faster message-passing implementations, as processes should not need to wait as long to learn about concurrent operations at remote processes and previous work has shown that multiplicity queues are computationally less complex than the unrelaxed version. Intriguingly, other work has shown that there is, in fact, not much speedup possible versus an unrelaxed queue implementation. Seeking to understand this difference between intuition and real behavior, we improve the existing lower bound for uniform algorithms. We also give an upper bound for a special case to show that our bound is tight at that point. To achieve our lower bounds, we use extended shifting arguments, which are rarely used. We use these techniques in series of inductive indistinguishability proofs, extending our proofs beyond the usual limitations of traditional shifting arguments. This proof structure is an interesting contribution independently of the main result, as new lower bound proof techniques may have many uses in future work.

BibTeX - Entry

@InProceedings{tran_et_al:LIPIcs.DISC.2023.34,
  author =	{Tran, Anh and Talmage, Edward},
  title =	{{Improved and Partially-Tight Lower Bounds for Message-Passing Implementations of Multiplicity Queues}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{34:1--34:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19160},
  URN =		{urn:nbn:de:0030-drops-191609},
  doi =		{10.4230/LIPIcs.DISC.2023.34},
  annote =	{Keywords: Distributed Data Structures, ADTs, Lower Bounds, Shifting Arguments, Multiplicity Queues}
}

Keywords: Distributed Data Structures, ADTs, Lower Bounds, Shifting Arguments, Multiplicity Queues
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023

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