BIB-VERSION:: CS-TR-v2.0 ID:: ncstrl.dartmouthcs//TR96-277 ENTRY:: March 10, 1997 ORGANIZATION:: Dartmouth College, Computer Science TITLE:: Compositional Reasoning is not possible in Determining the Solvability of Consensus TYPE:: Technical Report (paper) REVISION:: 1 AUTHOR:: Jayanti, Prasad DATE:: January 1996 RETRIEVAL:: For a paper copy, email RETRIEVAL:: For a paper copy, write to Technical Report Librarian Department of Computer Science Dartmouth College 6211 Sudikoff Laboratory Hanover, NH 03755-3510 USA RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR96-277.pdf 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. END:: ncstrl.dartmouthcs//TR96-277