Proof. We start by establishing that two read operations that return v and u respectively occur in ei. As v is written in T [R + K], v is also written in T [R + i + 1] (Lemma 1). Let p the process that performs the first write of v in T [R + i + 1]. By the code, p executes round R + i before performing that write operation, and v is the estimate of p in that round. At the beginning of round R + i, p either reads v in T [R + i] or writes v in T [R + i]. Moreover, the read operation on T [R + i + 1] performed by p at the beginning of round R + i + 1 returns ⊥ (Otherwise p does not perform a write operation on T [R + i + 1]). Therefore, every operation performed by p while it is executing round R + i occurs in epoch eR+i. K In particular, the read of T [R + j] performed by p at line 10 occurs in eR+i. This read must return v. Otherwise, p writes true in C[R + i], and this operation occurs in eR+i. As no process ever writes false in C[R + i], every read operation performed on C[R + i] that occurs in later epochs return true. Consider a process p′ executing round R + K. p′ reads C[R + i] at line 15. This read operation occurs after a write operation has been performed on T [R + ], so it occurs after the end of epoch eR+i. Hence, that operation returns true and thus p′ cannot write in D in that round. Therefore, no value is committed in round R + K, contradicting assumption H. Similarly, by considering the process that performs the first write of u in T [R + i + 1], we get that a read operation of T [R + j] that returns u occurs in eR+i. j Finally, as there are two read operations of T [R + j] returning two different values occur in ei, there must exist a write operation on T [R+j] that occurs in ei. We thus conclude that Wi /= ∅.

Proof. If the height of α is 0, and the common frontier (α itself) exists, then α is common. If the height of α is σ, the children of α are all in common by using induction hypothesis with the height of the children at σ-1, then the vertex α is common. ■