Dartmouth logo Dartmouth College Computer Science
Technical Report series
CS home
TR home
TR search TR listserv
By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Compositional Reasoning is not possible in Determining the Solvability of Consensus
Prasad Jayanti
Dartmouth PCS-TR96-277

Abstract:

Consensus, which requires processes with different input values to eventually agree on one of these values, is a fundamental problem in fault-tolerant computing. We study this problem in the context of asynchronous shared-memory systems. In our model, shared-memory consists of a sequence of cells and supports a specific set of operations. Prior research on consensus focussed on its solvability in shared-memories supporting specific operations. In this paper, we investigate the following general question:

Let OP1 and OP2 be any two sets of operations such that each set includes read and write operations. Suppose there is no consensus protocol for N processes in a shared-memory that supports only operations in OP1 and in a shared-memory that supports only operations in OP2. Does it follow that there is no consensus protocol for N processes in a shared-memory that supports all operations in OP1 and all operations in OP_2?

This question is in the same spirit as the robustness question, but there are significant differences, both conceptually and in the models of shared-memory for which the two questions are studied. For deterministic types, the robustness question has been known to have a positive answer, In contrast, we prove that the answer to the question posed above is negative even if operations are deterministic.


PDF PDF (508KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Prasad Jayanti, "Compositional Reasoning is not possible in Determining the Solvability of Consensus." Dartmouth Computer Science Technical Report PCS-TR96-277, January 1996.


Notify me about new tech reports.

Search the technical reports.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu


Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.