NDLI: Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Castan͂eda, Armando Imbs, Damien Rajsbaum, Sergio Raynal, Michel
Copyright Year	2016
Abstract	Processes in a concurrent system need to coordinate using an underlying shared memory or a message-passing system in order to solve agreement tasks such as, for example, consensus or set agreement. However, coordination is often needed to break the symmetry of processes that are initially in the same state---for example, to get exclusive access to a shared resource, to get distinct names, or to elect a leader. This paper introduces and studies the family of generalized symmetry breaking (GSB) tasks, which includes election, renaming, and many other symmetry breaking tasks, and studies how nondeterminism properties of objects solving tasks affects the computability power of GSB tasks. The aim is to develop the understanding of symmetry breaking tasks and their relation with agreement tasks and to study nondeterminism properties of objects solving tasks and how these properties affect the computability power of symmetry breaking tasks. Among various results characterizing the family of GSB tasks, it is shown that perfect renaming, i.e., $(n,n)$-renaming, is universal for all GSB tasks. The paper also shows that there is a large family of GSB tasks, which includes perfect renaming, that is strictly more powerful than $(n,n-1)$-set agreement. Some of these tasks are equivalent to perfect renaming, while others lie strictly between perfect renaming and $(n,n+1)$-renaming. Results comparing renaming and set agreement are proved, and the results in this paper complement known results. This paper sheds new light on the relations linking set agreement and symmetry breaking. The proofs are based on combinatorial topology techniques and new ideas about different notions of nondeterminism that can be associated with shared objects.
Sponsorship	Dirección General Asuntos del Personal Académico, Universidad Nacional Autónoma de México
Starting Page	379
Ending Page	414
Page Count	36
File Format	PDF
ISSN	00975397
DOI	10.1137/130936828
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2 (Special Section on the Forty-Fifth Annual ACM Symposium on the Theory of Computing (STOC 2013))
Volume Number	45
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2016-04-12
Access Restriction	Subscribed
Subject Keyword	renaming asynchronous read/write model agreement symmetry breaking set agreement crash failure wait-freedom concurrent object coordination Modes of computation distributed computability Analysis of algorithms and problem complexity decision task problem hierarchy Combinatorics nondeterminism
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

no Generalized Symmetry Breaking Tasks

Agreement via Symmetry Breaking: On the Structure of Weak Subconsensus Tasks

Brief announcement: there are plenty of tasks weaker than perfect renaming and stronger than set agreement

The universe of symmetry breaking tasks

The Renaming Problem in Shared Memory Systems: an Introduction

The Renaming Problem in Shared Memory Systems: an Introduction

A Theory-Oriented Introduction to Wait-Free Synchronization Based on the Adaptive Renaming Problem

Computing in the Presence of Concurrent Solo Executions

Distributed Universal Constructions: a Guided Tour

Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects

Similar Documents

no Generalized Symmetry Breaking Tasks

Agreement via Symmetry Breaking: On the Structure of Weak Subconsensus Tasks

Brief announcement: there are plenty of tasks weaker than perfect renaming and stronger than set agreement

The universe of symmetry breaking tasks

The Renaming Problem in Shared Memory Systems: an Introduction

The Renaming Problem in Shared Memory Systems: an Introduction

A Theory-Oriented Introduction to Wait-Free Synchronization Based on the Adaptive Renaming Problem

Computing in the Presence of Concurrent Solo Executions

Distributed Universal Constructions: a Guided Tour

Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects