Explanation of Aset. Aset is the algorithm of Figure 1 executed in HASf [L, ∅, n] to solve set agree- ment. Let id(i) be the identifier of process pi. Note that the values of these process identifiers could be whatever that imposes an order that allows to com- pare them. Also note that several identifiers can be the same (homonymous processes). Like in [1], we consider that a process pi proposes a value v (that is, proposei(v) is invoked) by writing v into a stable storage variable PROPi . Similarly, a pro- cess pi decides a value v (that is, decidei(v) is invoked) by writing v into another stable storage variable DECi . Let us suppose that both variables have the value ⊥ previously to any invocation. If a process pi recovers, it can see easily if it has already proposed or decided a value (that is, if proposei(v) or decidei(v) were invoked) reading these stable storage variables and checking if their values are different of ⊥. proposei(v): % by writing v into PROPi
Explanation of Aset. A L ∅ set is the algorithm of Figure 1 executed in HASf [ , , c/r] to solve set agreement. Let id(i) be the identifier of process pi. Note that the values of these process iden- tifiers could be whatever that imposes an order that allows to compare them. Also note that several identifiers can be the same (homonymous processes). To simplify the code of the algorithm, we consider that the execution of each concurrent task X of every pro- cess pi is not perpetually postponed (i.e., starvation is not possible). Hence, in each run, process pi eventually takes steps executing lines of task X if it is up, and the conditions that activate X are fulfilled. ⊥ ⊥ Like in [1], we consider that a process pi proposes a value v (that is, proposei(v) is invoked) by writing v into a stable storage variable PROPi . Similarly, a process pi decides a value v (that is, decidei(v) is invoked) by writing v into another stable storage variable DECi . Let us suppose that both variables have previously to any invocation. If a process pi recovers, it can see easily if it has already proposed or decided a value (that is, if proposei(v) or decidei(v) were invoked) reading these stable storage variables and checking if their values are different of . The variable vi is used by process pi to keep the current estimate of its decision value (lines 10 and 17). This variable vi contains initially the value v proposed by process pi when it invokes proposei(v) (line 2). In order to remember, in case of re- covering, the changes in vi before crashing, a process pi uses an stable storage variable statusi (lines 9, 16 and 22). ∨ ∧ ≤ L ∅ − L ( ) ≤ ( ) proposei(v) starts four tasks. For simplicity, we consider that tasks 2, 3 and 4 are executed atomically. Task 1 is used in phase 0 (PH0) by each process pi to broadcast (PH0, id(i), vi) messages permanently with a proposal vi (initially vi is pi’s proposal v, line 2) to the rest of processes of the system. Task 2 allows process pi to decide a proposed value when a (PH0, id(k), vk) message is received. This value vk is only decided if the condition id(k), vk id(i), vi happens. This condition is a shortcut for (id(k) < id(i)) [(id(k) = id(i)) (vk vi)]. That is, process pi decides vk if process pk has a lesser identifier or, if they have the same identifier, vi is greater or equal than vk. When a process decides, it moves to phase 1 (PH1). Task 3 allows process pi to decide a value already decided by another process when a (PH1, vk) message is received...
