Pending Conflicts Make Progress Impossible Petr Kuznetsov, Pierre Sutra, Guillermo Toyos-Marfurt Abstract In this work, we study progress conditions for commutativity-aware, linearizable implementations of shared objects. Motivated by the observation that commuting operations can be executed in parallel, we introduce conflict-obstruction-freedom : a process is guaranteed to complete its operation if it runs for long enough without encountering step contention with conflicting (non-commuting) operations. This condition generalizes obstruction-freedom and wait-freedom by allowing progress as long as step contention is only induced by commuting operations. We prove that conflict-obstruction-free universal constructions are impossible to implement in the asynchronous read-write shared memory model. This result exposes a fundamental limitation of conflict-aware universal constructions: the mere invocation of conflicting operations imposes a synchronization cost. Progress requires eventual resolution of pending conflicts. 1 Introduction Context Synchronizing operations that access shared data is a crucial task in distributed systems. The conventional safety property, linearizability [ 8 ] , requires that each operation takes effect instantaneously, at some point in time between its invocation and response. Jointly with safety, one also needs to define a progress property specifying under which circumstances an operation should return. The strongest of such guarantees is wait-freedom [ 9 ] , which demands that every operation completes in a finite number of steps of its invoking process. We consider the standard asynchronous shared-memory model, where processes communicate via read-write primitives and may crash at any time. In this model, it is well-established that wait-free linearizable implementations are impossible [ 5 ] . Because linearizability cannot usually be forsaken, without a dire price in usability, a lot of research efforts have focused on exploring weaker progress guarantees. A prominent example is obstruction-freedom [ 7 ] : a process that runs alone (without encountering steps of concurrent processes) for long enough is guaranteed to complete its operation. Although obstruction-free algorithms guarantee progress only without contention, they often behave as wait-free under typical scheduling assumptions and admit simpler implementations [ 4 ] . In particular, one can build an obstruction-free universal construction , which is a universal recipe to create linearizable objects, using just read-write communication primitives [ 7 , 2 ] . Motivation To ensure they apply to a wide variety of shared objects, progress properties are typically agnostic to their semantics. However, a key observation is that the main cost in synchronizing concurrent accesses comes from computing a total order among conflicting (non-commuting) operations [ 8 ] . In contrast, commuting operations [ 12 ] , such as increments on a shared counter, peek operations on a list, or updates to distinct keys in a hash table, may proceed independently, in a coordination-free manner. Some works leverage this to reduce the cost of data replication [ 10 ] , boost transactional memory [ 6 ] , and define smart locks [ 3 ] . In light of these results, a natural question is whether commuting operations may enjoy stronger progress than regular, conflicting ones. Contributions We introduce a novel progress condition, conflict-obstruction-freedom (COF). COF guarantees that a process that encounters no concurrent steps of conflicting operations must be able to complete its operation. This progress condition generalizes obstruction-freedom in a natural sense. Moreover, for objects that only provide commuting operations, COF is identical to wait-freedom. For example, consider a collection of queues , where each of them is implemented in the obstruction-free way [ 7 ] . The resulting composition of queues is conflict-obstruction-free, as any two operations are in conflict if and only if they are applied to the same queue. Further, we investigate whether conflict-obstruction-freedom admits a universal construction in the read-write shared memory model. This model captures minimal communication assumptions in a concurrent system, making it a natural starting point for studying a new progress condition. When all operations conflict, one can build obstruction-free universal constructions [ 7 ] . On the other hand, when all operations commute, wait-freedom is trivially achievable [ 1 ] . Thus, our study aims to characterize whether such a construction is possible in the intermediate cases, that is, when some operations commute and some do not. Our main result is negative. We show that such a universal construction can be used to solve a weaker version of consensus in which processes must terminate when only processes with the same input remain active. We prove that this task is impossible to solve using only reads and writes. This impossibility exposes a fundamental limitation in leveraging operation commutativity in concurrent systems. The mere presence of conflicting operations incurs a synchronization cost, even if these operations later become inactive. While commutativity eases coordination, it does not eliminate the need for synchronization: once a conflict appears, the system must eventually resolve it to make progress. Thus, to date, obstruction-freedom remains the strongest known progress condition that enables a universal construction in the read-write model. 2 Preliminaries Objects A sequential object is defined as a tuple (Q,q_{0},O,R,\sigma) , where Q is a set of states , q_{0}\in Q is the initial state , O is a set of operations , R is a set of responses , and \sigma:\;O\times Q\rightarrow R\times Q is a state transition function specifying the response and next state for each operation and state. Given a state q and a sequence of operations s\in O^{*} , we denote by s(q) the final state after applying the operations in s sequentially starting from q . For two sequences s and s^{\prime} , s\cdot s^{\prime} denotes their concatenation. Given two operations o,o^{\prime}\in O , we say that they commute in a state q if o\cdot o^{\prime}(q)=o^{\prime}\cdot o(q) and each operation returns the same result in both sequences. The object defines a symmetric conflict relation , written \asymp~\subseteq O\times O , where o\asymp o^{\prime} if there exists a state q in which o and o^{\prime} do not commute. When this happens, we say that operations o and o^{\prime} conflict . System Model We consider a system with n asynchronous processes, \{p_{i}\}_{i\in[n]} , that communicate through shared memory using atomic read-write registers. Processes are deterministic, and may fail by crashing, i.e., stopping prematurely and taking no further steps; an arbitrary number of processes may crash. There is no bound on relative process speeds, and no assumptions are made about timing or scheduling fairness. Algorithms and executions To implement a shared object, processes follow an algorithm consisting of deterministic automata, one per process. When a process p invokes an operation on the object, it takes steps , according to its automaton. Each step consists of local computation and one shared memory event – either a read or a write to an atomic register. After each step, p updates its local state according to its state machine and optionally returns a response on the pending high-level operation. In an operation instance \Phi=(x,o,p) , process p performs the operation o on object x . An execution fragment is a (possibly infinite) sequence of steps by the processes, according to their respective state machines. A configuration represents a complete system state, that is, the local states of all processes together with the state of the shared memory. An execution is an execution fragment starting from the algorithm’s initial configuration. If the last step of an operation instance \Phi in execution \alpha returns a response, we say that \Phi completes in \alpha , otherwise \Phi is pending in \alpha . We say that \Phi takes a step in an execution \alpha when the process p that invoked \Phi takes a step and \Phi has not yet returned a response in \alpha . In an infinite execution, a process is correct if it takes an infinite number of steps or it has no pending operation; otherwise, it is faulty . Progress conditions An implementation is wait-free if, in every execution, each operation instance invoked by a correct process completes in a finite number of its own steps. An operation instance \Phi is eventually step-contention free in an execution \alpha if either \Phi completes in \alpha , or there exists a suffix of \alpha in which only \Phi takes steps (i.e., from some point on in \alpha , \Phi runs solo). An implementation is obstruction-free (OF) if, for every infinite execution \alpha , any operation instance \Phi invoked by a correct process completes in \alpha whenever \Phi is eventually step-contention-free in \alpha [ 2 ] . 3 Conflict-obstruction-freedom We now introduce conflict-obstruction-freedom (COF), a natural generalization of obstruction-freedom that leverages operation commutativity. Intuitively, while obstruction-freedom guarantees termination in the absence of step contention , COF only requires the absence of step-contention with conflicting operations. Thus, any operation that takes sufficiently many steps completes, provided it eventually interleaves only with steps of operations that commute with it. Formally, we generalize the notion of obstruction-freedom from [ 2 ] by restricting step-contention to operations that do not commute. p_{1} p_{2} p_{3} read () inc () inc () Figure 1: Execution of three operations on a shared counter. Open brackets mark invocations and dots mark steps. Process p_{1} crashes after some steps, while p_{2} and p_{3} continue concurrently. A read conflicts with an increment. Two increments commute. Conflict-obstruction-freedom guarantees completion of the two increments, while obstruction-freedom does not. Definition 1 . An operation instance \Phi\!=\!(x,o,p) is eventually conflict-step-contention free in an execution \alpha if either \Phi completes in \alpha , or there exists a suffix of \alpha in which no other operation \Phi^{\prime}=(x,o^{\prime},q) takes steps such that o\!\asymp\!o^{\prime} . Definition 2 . An implementation is conflict-obstruction-free if, for every infinite execution \alpha and every operation instance \Phi invoked by a correct process, such that \Phi is eventually conflict-step-contention free in \alpha , \Phi completes in \alpha . To grasp the new progress condition, consider the execution in Figure 1 , where three processes access a shared counter. The object supports two types of operations: read() , which returns the current value of the counter, and inc() , which increments the counter by one. In the figure, process p_{1} invokes o_{1}=read() , while processes p_{2} and p_{3} invoke o_{2}=inc() and o_{3}=inc() , respectively. Reading a counter conflicts with incrementing it ( o_{1}\!\asymp\!o_{2} and o_{1}\!\asymp\!o_{3} ), but two increment operations — and likewise two read operations — commute with each other ( o_{2}\not\asymp o_{3} ). After some steps of p_{1} , p_{1} crashes while p_{2} and p_{3} continue concurrently. In Figure 1 , no operation is eventually step-contention free. As a consequence, OF would not guarantee that the operations of the two correct processes complete. On the contrary, COF would ensure progress because o_{2} and o_{3} are in fact eventually conflict-step-contention free. Lemma 1 . Let \mathcal{I} be an implementation of a shared object (Q,q_{0},O,R,\sigma) . If the induced conflict relation satisfies \asymp=O\times O (i.e., every pair of operations conflicts), then \mathcal{I} is conflict-obstruction-free iff \mathcal{I} is obstruction-free. Proof. By definition, an operation instance \Phi is eventually conflict-step-contention free if either (1) \Phi completes, or (2) there is a suffix of the execution in which no other operation conflicting with \Phi takes steps. If \asymp=\!O\!\times\!O , any operation conflicts with \Phi , so condition (2) holds iff no other operation takes steps in the suffix. Hence, in this case, eventual conflict-step-contention-freedom coincides with eventual step-contention-freedom. Since COF requires termination of every eventually conflict-step-contention free operation, and OF requires termination of every eventually step-contention free operation, the conditions coincide. ∎ Lemma 2 . Let \mathcal{I} be an implementation of a shared object (Q,q_{0},O,R,\sigma) . If the induced conflict relationship is empty, \asymp=\emptyset (i.e., all operations commute), then \mathcal{I} is conflict-obstruction-free iff \mathcal{I} is wait-free. Proof. If \asymp=\emptyset , no two operations conflict. Hence, in every execution, every operation instance is eventually conflict-step-contention free. By definition of COF, every such operation invoked by a correct process must complete, which implies wait-freedom. Conversely, any wait-free implementation guarantees termination of every operation in every execution, satisfying COF. ∎ 4 Impossibility of Conflict-obstruction-freedom Our main result establishes that no algorithm can implement a conflict-obstruction-free universal construction in the read-write shared memory model. The proof proceeds by a reduction to the (binary) consensus problem requiring COF termination. Then, we show that this problem cannot be implemented in the read-write shared memory model. 4.1 Conflict-obstruction-free Consensus In the consensus problem [ 5 ] , processes propose values via invoking single-shot operations propose( v ) and decide on the returned values. A consensus algorithm must satisfy the following properties: (1) Validity: If a process decides value v , then some process proposed v ; (2) Agreement: No two processes decide differently; (3) Termination: Every correct process decides in finitely many steps. Conflict-obstruction-free consensus replaces wait-free termination with a weaker progress requirement, COF termination, while preserving validity and agreement. We now model consensus as a deterministic sequential object, restricting attention to the binary case. Its state space is Q\!=\!\{0,1,\bot\} and initial state q_{0}\!=\!\bot , where 0 and 1 represent the states where values 0 and 1 have been decided, respectively, and \bot represents the initial undecided state. The set of operations is O\!=\!\{\textit{propose}(v)\}_{v\in\{0,1\}} , each returning a value in \{0,1\} . The transition function \sigma sets the state to the argument of the first propose operation and returns that value; subsequent operations return the decision value associated with the state without modifying it. Hence, any pair of propose operations commute in states 0 and 1 , and two operations \textit{propose}(v) and \textit{propose}(v^{\prime}) commute in state \bot iff v\!=\!v^{\prime} . The conflict relation \asymp therefore consists precisely of the pair (\textit{propose}(0),\textit{propose}(1)) : only concurrent proposals of different values conflict. Thus, a COF consensus implementation guarantees termination in executions where, after some point, only processes with the same input value take steps. Conflict-obstruction-free consensus is implementable in the read–write model for two processes. The consensus algorithm in [ 2 ] satisfies COF termination in this case, as it guarantees termination when both processes have the same input. As we show below, this is no longer the case for more than two processes. 4.2 Proof of the Impossibility Result We show that COF consensus cannot be implemented in the read-write shared memory model for three or more processes. To establish this result, we consider a minimal model instance with three processes \{p_{0},p_{1},p_{2}\} , where p_{0} proposes 0 and both p_{1} and p_{2} propose 1 . The proof adapts the classical FLP-style bivalency argument [ 5 , 11 ] , using an appropriate definition of valency that accounts for COF termination. The next step of each process is fully determined by its local state. We denote a step e=(p,m,a) , where p is the process performing the step, m is the memory location accessed, and a\in\{\text{R},\text{W}\} indicates whether p is reading or writing register m . If e is the next step of p in some configuration C , we say that e is enabled in C . An initial configuration , specifying the state of each process and the shared memory, is characterized by the vector assigning inputs to each process. In our consensus instance, we consider the initial input vector to be I\!=\!(0,1,1) . We write C\!\xrightarrow{e}\!C^{\prime} or C\xrightarrow{}C^{\prime} if there exists an enabled step e\!=\!(p,m,a) in C such that process p takes step e , as a result, the configuration of the system changes from C to C^{\prime} . Note that the only difference between C and C^{\prime} is the local state of process p , its next enabled step, and possibly the state of the shared register m . We write C\!\mathrel{\hbox to9.2pt{\vbox to7.11pt{\pgfpicture\makeatletter\hbox{\hskip 4.60138pt\lower-4.95274pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.04861pt}{0.0pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} { {}}{}{{}}{}{{}} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {}{{ { \lxSVG@setdash{0.0pt}\lx@inpgf@ignorespaces\lxSVG@roundcap\lx@inpgf@ignorespaces\lxSVG@roundjoin\lx@inpgf@ignorespaces{} {\lx@inpgf@ignorespaces}{}{} {}{}{} \lxSVG@stroke}} }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 5.54 -3.26 L 0.56 -3.26 L -0.63 -4.22 L -2.99 -2.29 L -6.09 -3.26 L -6.09 -3.26}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{4.20139pt}{-2.35277pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -2.88 3.32 C -2.35 1.33 -1.18 0.39 0 0 C -1.18 -0.39 -2.35 -1.33 -2.88 -3.32}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope {{ {}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}}{}{{\lx@inpgf@ignorespaces}{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}\!C^{\prime} or C\!\mathrel{\hbox to9.78pt{\vbox to10.12pt{\pgfpicture\makeatletter\hbox{\hskip 4.89091pt\lower-6.45969pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.33815pt}{-1.50694pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} { {}}{}{{}}{}{{}} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 5.94 -5.34 L 0.96 -5.34 L -0.23 -6.31 L -2.59 -4.37 L -4.95 -6.31 L -6.49 -5.34 L -6.49 -5.34}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{4.49092pt}{-3.85971pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -2.88 3.32 C -2.35 1.33 -1.18 0.39 0 0 C -1.18 -0.39 -2.35 -1.33 -2.88 -3.32}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope {{ {}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}}{}{{\lx@inpgf@ignorespaces}{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}\!C^{\prime} if C\!=\!C^{\prime} or there exists a sequence of steps \pi\!=\!e_{1},\ldots,e_{k\geq 1} such that C\!\xrightarrow{e_{1}}\!\dots\!\xrightarrow{e_{k}}\!C^{\prime} and say that C^{\prime} is reachable from C , or C^{\prime} is a descendant of C . For a set P\subseteq\{p_{i}\}_{i\in[n]} , we say that an execution fragment \pi is P -only if \pi only contains steps of processes in P . We define the valency of a configuration according to the decisions processes p_{1} and p_{2} take in a subset of reachable configurations. A configuration C is v - deciding if some process has decided v in C . We say that a configuration C is v -valent if there is no \{p_{1},p_{2}\} -only sequence \pi , such that C\mathrel{\hbox to9.78pt{\vbox to10.12pt{\pgfpicture\makeatletter\hbox{\hskip 4.89091pt\lower-6.45969pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.33815pt}{-1.50694pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} { {}}{}{{}}{}{{}} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 5.94 -5.34 L 0.96 -5.34 L -0.23 -6.31 L -2.59 -4.37 L -4.95 -6.31 L -6.49 -5.34 L -6.49 -5.34}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{4.49092pt}{-3.85971pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -2.88 3.32 C -2.35 1.33 -1.18 0.39 0 0 C -1.18 -0.39 -2.35 -1.33 -2.88 -3.32}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope {{ {}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}}{}{{\lx@inpgf@ignorespaces}{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}C^{\prime} and C^{\prime} is (1-v) -deciding. We say that a configuration is univalent if it is 0 -valent or 1 -valent. Otherwise, we say that the configuration is bivalent . Clearly, if a configuration C is v -valent and it has a descendant C^{\prime} , C\mathrel{\hbox to9.78pt{\vbox to10.12pt{\pgfpicture\makeatletter\hbox{\hskip 4.89091pt\lower-6.45969pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.33815pt}{-1.50694pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} { {}}{}{{}}{}{{}} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 5.94 -5.34 L 0.96 -5.34 L -0.23 -6.31 L -2.59 -4.37 L -4.95 -6.31 L -6.49 -5.34 L -6.49 -5.34}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{4.49092pt}{-3.85971pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -2.88 3.32 C -2.35 1.33 -1.18 0.39 0 0 C -1.18 -0.39 -2.35 -1.33 -2.88 -3.32}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope {{ {}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}}{}{{\lx@inpgf@ignorespaces}{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}C^{\prime} , where \pi is \{p_{1},p_{2}\} -only, then C^{\prime} is also v -valent. {\lx@inpgf@ignorespaces{I\ _{\color[rgb]{1,0,0}(1)}}} {\lx@inpgf@ignorespaces{C\ _{\color[rgb]{1,0,0}(1)}}} {\lx@inpgf@ignorespaces{C_{0}\ {}_{\color[rgb]{1,0,0}(0)}}} {\lx@inpgf@ignorespaces{Z_{s}\ {}_{\color[rgb]{1,0,0}(1)}}} {\lx@inpgf@ignorespaces{D_{0}\ {}_{\color[rgb]{1,0,0}(0)}}} {\lx@inpgf@ignorespaces{Z^{\prime}_{s}\ {}_{\color[rgb]{1,0,0}(0)}}} {\lx@inpgf@ignorespaces{Z_{s+1}\ {}_{\color[rgb]{1,0,0}(1)}}} {\lx@inpgf@ignorespaces H\ _{\color[rgb]{1,0,0}(0)}} {\lx@inpgf@ignorespaces{Z_{s+1}^{\prime}\ {}_{\color[rgb]{1,0,0}(1)}}} {\lx@inpgf@ignorespaces{D_{1}\ {}_{\color[rgb]{1,0,0}(1)}}} \scriptstyle{\lx@inpgf@ignorespaces p_{0}\ \text{solo}} \scriptstyle{\lx@inpgf@ignorespaces e} \scriptstyle{\lx@inpgf@ignorespaces p_{1}\ \text{solo}} \scriptstyle{\lx@inpgf@ignorespaces p_{0}\ \text{solo}} \scriptstyle{\lx@inpgf@ignorespaces e} \scriptstyle{\lx@inpgf@ignorespaces e^{\prime}} \scriptstyle{\lx@inpgf@ignorespaces e^{\prime}} \scriptstyle{\lx@inpgf@ignorespaces e} \scriptstyle{\lx@inpgf@ignorespaces p_{1}\ \text{solo}} Figure 2: Valency diagram showcasing the contradiction in Lemma 4 . Lemma 3 . The initial configuration I with input vector (0,1,1) is 1 -valent. Proof. Consider any execution \pi from I in which only p_{1} and p_{2} take steps. This execution is indistinguishable to p_{1} and p_{2} from an execution starting from the input vector (1,1,1) ; therefore, by Validity, no process decides 0 in \pi . By COF Termination, 1 is decided in execution \pi . ∎ Lemma 4 . There exists a bivalent configuration reachable from I . Proof. Suppose, by contradiction, that every configuration reachable from I is univalent. Figure 2 illustrates the key configurations and critical steps considered below. Suppose an execution \sigma where p_{0} runs solo from I . As p_{1} and p_{2} take no steps, p_{0} decides 0 in \sigma by COF Termination and Validity. Let D_{0} be the configuration reached in \sigma where p_{0} decides 0 . By Agreement (and linearizability), D_{0} is 0 -valent. By our assumption, all configurations reachable from I are univalent (in particular, all configurations in \sigma , from I to D_{0} ). By Lemma 3 , I is 1 -valent. Hence, there exist configurations C , C_{0} and a critical step e=(p_{0},m,a) such that I\mathrel{\hbox to9.2pt{\vbox to7.11pt{\pgfpicture\makeatletter\hbox{\hskip 4.60138pt\lower-4.95274pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.04861pt}{0.0pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} { {}}{}{{}}{}{{}} {}{} {}{{}{}\lx@inpgf@ignorespaces}{}{}{}\lx@inpgf@ignorespaces{{}}{{}}{{}{}\lx@inpgf@ignorespaces}{{}{}\lx@inpgf@ignorespaces} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}\lx@inpgf@ignorespaces}{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {} }{{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}} {{}} } {{{{}{}{{}} }}{{\lx@inpgf@ignorespaces}}{{}}} {}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 5.54 -3.26 L 0.56 -3.26 L -0.63 -4.22 L -2.99 -2.29 L -6.09 -3.26 L -6.09 -3.26}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{4.20139pt}{-2.35277pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -2.88 3.32 C -2.35 1.33 -1.18 0.39 0 0 C -1.18 -0.39 -2.35 -1.33 -2.88 -3.32}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope {{ {}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}}{}{{\lx@inpgf@ignorespaces}{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}C\xrightarrow{e}C_{0} , where C is 1 -valent and C_{0} is 0 -valent. Now consider an execution \pi where p_{1} runs solo from C until it decides. By Termination and the fact that C is 1 -valent, \pi ends at a configuration D_{1} where p_{1} decides 1 . Let C=Z_{0}\ldots Z_{k\geq 1}=D_{1} be the sequence of configurations obtained by applying the steps in \pi . Since p_{0} takes no step in \pi , e is enabled in each Z_{i\in[0,k]} . Let Z^{\prime}_{i}:Z_{i}\xrightarrow{e}Z^{\prime}_{i} be the resulting configuration from applying step e from Z_{i} . Then Z^{\prime}_{0}=C_{0} is 0 -valent and Z^{\prime}_{k} is 1 -valent by Agreement. Hence, there exists s\in[0,k\!-\!1] such that Z_{s}^{\prime} is 0 -valent, and Z_{s} , Z_{s+1} and Z^{\prime}_{s+1} are 1 -valent. Let e^{\prime}=(p_{1},m^{\prime},a^{\prime}) be the step such that Z_{s}\xrightarrow{\smash{e^{\prime}}}Z_{s+1} , and H the configuration such that Z^{\prime}_{s}\xrightarrow{\smash{e^{\prime}}}H . We observe that step e=(p_{0},m,a) must be a write. Otherwise, H and Z_{s+1} are indistinguishable to p_{2} , however, H is 0 -valent and Z_{s+1} is 1 -valent. Similarly, e^{\prime} must also be a write; otherwise Z^{\prime}_{s} and Z^{\prime}_{s+1} are indistinguishable to p_{2} , yet p_{2} would decide differently from Z^{\prime}_{s} and Z^{\prime}_{s+1} . Now there are two cases to consider, both leading to a contradiction. If m\!\neq\!m^{\prime} , then e^{\prime} and e commute, leading to H=Z^{\prime}_{s+1} , and contradicting that H is 0 -valent while Z^{\prime}_{s+1} is 1 -valent. If instead m\!=\!m^{\prime} , then p_{1} cannot distinguish Z^{\prime}_{s+1} from Z^{\prime}_{s} , yet Z^{\prime}_{s} is 0 -valent while Z_{s+1}^{\prime} is 1 -valent; a contradiction. ∎ Lemma 5 . Any bivalent configuration C has an enabled step e by a process in \{p_{1},p_{2}\} such that the resulting configuration C^{\prime} with C\xrightarrow{e}C^{\prime} is bivalent. Proof. Let e_{1} and e_{2} be the steps by, resp., p_{1} and p_{2} that are enabled in C . Let C_{1} and C_{2} be the configurations obtained by applying, resp., e_{1} and e_{2} to C . By contradiction, assume that that both C_{1} and C_{2} are univalent. Moreover, C_{1} and C_{2} must have different valencies, otherwise C would not be bivalent. Without loss of generality, assume that C_{1} is 0 -valent and C_{2} is 1 -valent. Let C_{1}^{\prime} and C_{2}^{\prime} be the resulting configurations of applying steps e_{2} and e_{1} from C_{1} and C_{2} respectively ( C_{1}\xrightarrow{e_{2}}C_{1}^{\prime} and C_{2}\xrightarrow{e_{1}}C_{2}^{\prime} ). If both e_{1} and e_{2} are read steps, configurations C_{1}^{\prime} and C_{2}^{\prime} are indistinguishable to any process and have opposite valencies—a contradiction since p_{1} has to decide differently in any \{p_{1}\} -only execution right after C_{1}^{\prime} and C_{2}^{\prime} . The same argument applies if e_{1} and e_{2} access different registers. Thus, the two steps access the same register and (at least) one of them is a write. Without loss of generality, suppose that e_{1} is a write step. By termination, if we schedule \{p_{1}\} -only executions right after C_{1} and C_{2}^{\prime} , it should eventually decide. Let D_{1} and D_{2} be the corresponding deciding configurations. Process p_{1} cannot distinguish C_{1} from C_{2}^{\prime} : if e_{2} is a write step, it writes to the same location as step e_{1} and occurs before it ( C\!\xrightarrow{e_{2}}\!C_{2}\!\xrightarrow{e_{1}}\!C_{2}^{\prime} ), and if e_{2} is a read step, it affects only the local state of p_{2} . Hence, p_{1} cannot distinguish between D_{1} and D_{2} , and thus should decide the same value in both configurations—a contradiction with the fact that C_{1} (and, thus, D_{1} ) is 0 -valent and C_{2} (and, thus, D_{2} ) is 1 -valent. ∎ Theorem 6 . No algorithm implements conflict-obstruction-free consensus in the read-write shared memory model of three or more processes. Proof. By contradiction, suppose that there exists an algorithm \mathcal{A} implementing COF consensus for three processes \{p_{0},p_{1},p_{2}\} . Let us consider the initial configuration I with the input vector (0,1,1) , i.e., p_{0} proposes 0 and p_{1} and p_{2} propose 1 . By Lemma 4 , \mathcal{A} has a bivalent configuration C reachable from I . Lemma 5 shows that from any bivalent configuration we can take a step by a process in \{p_{1},p_{2}\} to reach another bivalent configuration. By repeating this argument, we construct an infinite execution starting from I in which, from some point on, only \{p_{1},p_{2}\} take steps. As the execution goes through bivalent configurations only, no process can decide in it. However, because \{p_{1},p_{2}\} have the same input, this execution is conflict-step-contention free, and both p_{1} and p_{2} are required to complete their operations—a contradiction. Hence no such algorithm exists. ∎ A COF universal construction is an algorithm that takes as input a sequential object specification and produces a linearizable shared-memory implementation satisfying COF termination — in particular it implements COF consensus. Corollary 7 . No universal construction algorithm is conflict-obstruction-free in the read-write shared memory model of three or more processes.