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.2015.13
URN: urn:nbn:de:0030-drops-66044
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6604/
Go to the corresponding LIPIcs Volume Portal

Saraph, Vikram ; Herlihy, Maurice

The Relative Power of Composite Loop Agreement Tasks

pdf-format:
LIPIcs-OPODIS-2015-13.pdf (0.6 MB)

Abstract

Loop agreement is a family of distributed tasks that includes set agreement and simplex agreement, and was used to prove the undecidability of wait-free solvability of distributed tasks by read/write memory. Herlihy and Rajsbaum defined the algebraic signature of a loop agreement task, which consists of a group and a distinguished element. They used the algebraic signature to characterize the relative power of loop agreement tasks. In particular, they showed that one task implements another exactly when there is a homomorphism between their respective signatures sending one loop to the other. In this paper, we extend the previous result by defining the composition of multiple loop agreement tasks to create a new one with the same combined power. We generalize the original algebraic characterization for relative power to compositions of tasks. In this way, we can think of loop agreement tasks in terms of their basic building blocks. We also investigate a category-theoretic perspective of loop agreement by defining a category of loops, showing that the algebraic signature is a functor, and proving that our definition of task composition is the "correct" one, in a categorical sense.

BibTeX - Entry

@InProceedings{saraph_et_al:LIPIcs:2016:6604,
  author =	{Vikram Saraph and Maurice Herlihy},
  title =	{{The Relative Power of Composite Loop Agreement Tasks}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Emmanuelle Anceaume and Christian Cachin and Maria Potop-Butucaru},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6604},
  URN =		{urn:nbn:de:0030-drops-66044},
  doi =		{10.4230/LIPIcs.OPODIS.2015.13},
  annote =	{Keywords: Distributed computing, loop agreement, task composition, topology}
}

Keywords: Distributed computing, loop agreement, task composition, topology
Collection: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Issue Date: 2016
Date of publication: 13.10.2016

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