Self-stabilizing Byzantine-tolerant Recycling [This document is a complementary technical report to the extended abstract version of this work [33].]

Self-stabilizing Byzantine-tolerant Recycling

Chryssis Georgiou [ Computer Science, Univ. Cyprus, Cyprus.
Email: ] Michel Raynal [ IRISA, Univ. Rennes 1, France.
Email: ] Elad M. Schiller [ Computer Science and Engineering, Chalmers Univ. Tech., Sweden.
Email: ]

Numerous distributed applications, such as cloud computing and distributed ledgers, necessitate the system to invoke asynchronous consensus objects an unbounded number of times, where the completion of one consensus instance is followed by the invocation of another. With only a constant number of objects available, object reuse becomes vital.

We investigate the challenge of object recycling in the presence of Byzantine processes, which can deviate from the algorithm code in any manner. Our solution must also be self-stabilizing, as it is a powerful notion of fault tolerance. Self-stabilizing systems can recover automatically after the occurrence of arbitrary transient-faults, in addition to tolerating communication and (Byzantine or crash) process failures, provided the algorithm code remains intact.

We provide a recycling mechanism for asynchronous objects that enables their reuse once their task has ended, and all non-faulty processes have retrieved the decided values. This mechanism relies on synchrony assumptions and builds on a new self-stabilizing Byzantine-tolerant synchronous multivalued consensus algorithm, along with a novel composition of existing techniques.

We study the problem of recycling asynchronous consensus objects.
We propose a more robust solution than the state-of-the-art solution to achieve this goal.

Fault model

We study solutions for message-passing systems.
We model a broad set of failures that can occur to computers and networks.
OurSpecifically, our model includes up to $t$ process failures, crashed or Byzantine [37]. In detail, the adversary completely controls any Byzantine node, the adversary can send a fake message that the node never sent, modify the payload of its messages, delay the delivery of its messages, or omit any subset of them.
The adversary can challenge the algorithm by creating failure patterns in which a fault occurrence appears differently to different system components.
The adversary is empowered with the unlimited ability to coordinate the most severe failure patterns.
We assume a known maximum number, $t$, of Byzantine processes.
For solvability's sake, we also restrict the adversary from letting a Byzantine process impersonate a non-faulty one, as in [51], we assume private channels between any pair of nodes.

The proposed solution uses a hybridization of two fault models, which their notations follow Raynal [51].

* $\mathsf{BAMP_{n,t}[FC, t < n/3,RCCs]}$—used by the consensus object.   The studied asynchronous consensus objects are for message-passing systems where the algorithm cannot explicitly access the local clock or assume the existence of guarantees on the communication delay. These systems are also prone to communication failures, packet omission, duplication, and reordering, as long as Fair Communication (FC) holds between non-faulty processes.
That is, we limit the adversary's ability to impact the delivery of messages between any two non-faulty processes by assuming fair scheduling of message arrivals.
For the sake of solvability [37, 48, 57], we also assume that the number of faulty processes $t<n/3$ is less than one-third of the number of processes in the system. This fault model, $\mathsf{BAMP_{n,t}[FC, t < n/3,RCCs]}$, is called the Byzantine Asynchronous Message-Passing model with at most $t$ (out of $n$) faulty processes. The array $\mathsf{[FC, t < n/3,RCCs]}$ denotes the list of all assumptions, FC and $t<n/3$ as well as random common coins (RCCs).
<ref> discusses RCCs in detail.

* The recycling mechanism assumes $\mathsf{BSMP_{n,t}[\kappa\mathit{-}SGC,t < n/3,RCCs]}$.   This model is called the Byzantine Synchronous Message-Passing with at most $t$ (out of $n$) faulty processes, and $t < n/3$. The $\mathsf{BSMP_{n,t}[\kappa\mathit{-}SGC,t < n/3,RCCs]}$ model is defined by enriching the  $\mathsf{BAMP_{n,t}[FC,t < n/3]}$ model with a $\kappa$-state global clock, reliable communication, and an RCC service. A detailed presentation of $\mathsf{BSMP_{n,t}[\kappa\mathit{-}SGC,t < n/3,RCCs]}$ appears in  <ref>.

In addition to the failures captured by our model, we also aim to recover from arbitrary transient-faults, any temporary violation of assumptions according to which the system was designed to operate. This includes the corruption of control variables, such as the program counter, packet payload, and indices, sequence numbers, which are responsible for the correct operation of the studied system, as well as operational assumptions, such as that at least a distinguished majority of processes never fail. Since the occurrence of these failures can be arbitrarily combined, we assume that these transient-faults can alter the system state in unpredictable ways. In particular, when modeling the system, Dijkstra [14] assumes that these violations bring the system to an arbitrary state from which a self-stabilizing system should recover. Dijkstra requires recovery after the last occurrence of a transient-fault and once the system has recovered, it must never violate the task specifications. there could be any finite number of transient faults before the last one occurs, which may leave the system in an arbitrary state. Moreover, recovery from an arbitrary system state is demonstrated once all transient faults cease to happen, see [4, 15] for details.

Memory constraints

In the absence of transient faults, one can safely assume that the algorithm variables, such as a counter for the message sequence number, are unbounded.
This assumption can be made valid for any practical setting by letting each counter use enough bits, say, $64$, because counting (using sequential steps) from zero to the maximum value of the counter will take longer than the time during which the system is required to remain operational.
Specifically, if each message transmission requires at least one nanosecond, it would take at least 584 years until the maximum value can be reached.
However, in the context of self-stabilization, a single transient fault can set the counter value into one that is close to the maximum value.
Thus, any self-stabilizing solution must cope with this challenge and use only bounded memory and communication.

Self-stabilization via algorithmic transformation

This work is dedicated to designing a generic transformer, which takes an algorithm as input and systematically redesigns it into its self-stabilizing variation as output. Existing transformers differ in the range of input algorithms and fault models they can transform, see Dolev <cit.>, Katz and Perry [35], Afek  [2], and Awerbuch  [5].

Dolev, Petig, and Schiller [21] (DPS in short) proposed a transformer of crash-tolerant algorithms for asynchronous message-passing systems into ones that also recover from transient faults via self-stabilization.
Georgiou  [29] implemented DPS.
Lundström show DPS's applicability to various communication abstractions, such as atomic snapshot [30], consensus [41, 42], reliable broadcast [40], and state-machine replication [44].
DPS mandates that (DPS.i) the input algorithm guarantees,  after the last transient fault occurrence, the completion of each invocation of the communication abstraction, it should eventually terminate regardless of the starting state. This condition facilitates the eventual release of resources used by each invocation.
Additionally, (DPS.ii) it associates a sequence number with each invocation to differentiate the resources utilized by different invocations. This enables the recycling of resources associated with obsolete invocations through a sliding window technique, along with a global restart once the maximum sequence number is reached.

Recently, DPS was utilized by Duvignau  [25] for converting Byzantine fault-tolerant (BFT) reliable broadcast proposed by Bracha and Toueg [13] into a Self-Stabilizing BFT (SSBFT) variation.
This solution recycles reliable broadcast objects using synchrony assumptions.
It also relies on the fact that the process may allocate independent local memory and sequence numbers per sender.
However, consensus objects often use shared sequence numbers, and thus, parts of their local memories are codependent.
Therefore, we use another approach.

Problem description

This work studies an important building block that is needed for the SSBFT implementation of asynchronous consensus objects.
With only a bounded number of consensus objects available, it becomes essential to reuse them robustly.
We examine the case in which the repeated invocation of consensus needs to reuse the same memory space and the $(k+1)$-th invocation can only start after the completion of the $k$-th instance.
In an asynchronous system that uses only a bounded number of objects, ensuring the termination of the $k$-th instance before invoking the $(k+1)$-th might be crucial, for total order broadcasting, as in some blockchains.
Thus, we require SSBFT consensus objects to eventually terminate regardless of their starting state, as in (DPS.i).

We focus on addressing the challenge of recycling asynchronous consensus objects after they have completed their task and delivered their decision to all non-faulty processes.
This task becomes complex due to the presence of asynchrony and Byzantine failures.
Utilizing the joint sequence numbers of (DPS.ii) for recycling consensus objects is not straightforward, because it requires ensuring that all non-faulty processes have delivered the decided value (for the $k$-th consensus invocation) as well as agreeing that such collective delivery occurred before incrementing the sequence number counter (that is going to be used by the $(k+1)$-th invocation).
To overcome this chicken-and-egg problem, we relax the problem requirements by allowing the recycling mechanism to depend on synchrony assumptions.
To mitigate the impact of these assumptions, a single recycling action can be performed for a batch of $\delta$ objects, where $\delta$ is a predefined constant determined by the available memory.
Thus, our approach facilitates asynchronous networking in communication-intensive components, the consensus objects, while synchronous recycling actions are performed according to a load parameter, $\delta$.

Our solution in a nutshell

Our solution aims to emulate (DPS.ii) by incorporating synchrony assumptions specifically for the recycling service, while keeping the consensus object asynchronous to handle intensive message exchange.

To begin, we maintain an index that points to the most recently invoked object in a constant-size array.
In order to ensure that all non-faulty processes agree on the value of the index, we utilize a novel technique called simultaneous increment-or-get indexes (SGI-index).
When recycling an object, we increment the index, but this increment is performed only after an agreement among the non-faulty processes that the relevant object has made its decision and delivered it to all non-faulty processes.
Thus, we use a new SSBFT multivalued consensus before each increment, ensuring that consensus is reached before the increment. all needed deliveries had occurred before the increment.

Additionally, our solution answers how an SSBFT asynchronous consensus object can provide an indication that at least one non-faulty process has made a decision and delivered. We utilize this indication as input to trigger the recycling action, effectively incorporating it into the SSBFT multivalued consensus.

Related work

Object recycling

Object recycling was studied mainly in the context of crash-tolerant (non-BFT) systems [49, 58].
There are a few (non-self-stabilizing) implementations of garbage collection in the presence of Byzantine processes,  [47].

As mentioned, FLP [28] concluded that consensus is impossible to solve deterministically in asynchronous settings in the presence of even a single crash failure. In [27] it was shown that a lower bound of $t+1$ communication steps are required to solve consensus deterministically in both synchronous and asynchronous environments.

In the presence of Byzantine faults, the consensus problem is not solvable (without signatures) if a third or more of the processes are faulty [37].

Thus, optimally resilient signature-free Byzantine consensus algorithms, tolerate $t<n/3$ faulty processes.

The task is also impossible if a process can impersonate some other process in its communication with the other entities [6].
As in [46], we assume the absence of spoofing attacks and similar means of impersonation.

Non-self-stabilizing BFT consensus

Rabin [50] offers a solution to BFT consensus (cf.  <ref> for definitions).
It assumes the availability of random common coins (RCCs), allowing for a polynomial number of communication steps and optimal resilience, $t<n/3$, where $n$ is the number of participating processes.
Mostéfaoui, Moumen, and Raynal [46], or MMR in short, is a signature-free BFT binary consensus solution.
MMR is optimal in resilience, uses $O(n^2)$ messages per consensus invocation, and completes within $O(1)$ expected time.

Non-self-stabilizing synchronous BFT multivalued consensus

The proposed recycling mechanism uses an SSBFT multivalued consensus, which is based on a non-self-stabilizing BFT multivalued consensus.
Kowalski and Mostéfaoui [36] proposed the first multivalued optimal resilience, polynomial communication cost, and optimal $t+1$ rounds, but without early stopping. Abraham and Dolev [1] advanced the state of the art by offering also optimal early stopping.
Unlike the above BFT multivalued consensus solutions, our SSBFT multivalued solution adds self-stabilization.

SSBFT solutions

In the broader context of SSBFT solutions for message-passing systems, we find topology discovery [18], storage [11, 10, 9], clock synchronization [22, 38], approximate agreement [12], asynchronous unison [24], communication in dynamic networks [45], and SSBFT state-machine replication [8, 17] to name a few.

SSBFT consensus

To the best of our knowledge, the only SSBFT RCCs construction is the one by Ben-Or, Dolev, and Hoch [7], in short BDH, for synchronous systems with private channels.
BDH uses its SSBFT RCCs construction as a building block for devising an SSBFT clock synchronization solution.
Our work borrows several mechanisms from BDH, such as SSBFT RCCs and SSBFT clock synchronization.
Recently, Georgiou, Marcoullis, Raynal, and Schiller [32], or GMRS in short, presented an SSBFT variation on MMR, which offers a BFT binary consensus solution.
GMRS preserves MMR's optimality properties, and thus, we use base our example consensus object on GMRS in this work.

GMRS follows the design criteria of loosely self-stabilizing systems [53], ensuring task completion but with rare safety violation events. In the context of the studied problem, the former guarantee renders the latter one irrelevant.
We point out that related work to loosely self-stabilizing systems include randomized congestion control [26] and leader election [54, 55, 56, 34].

Self-stabilizing non-Byzantine fault-tolerant solutions

Lundström, Raynal, and Schiller [41] presented the first self-stabilizing solution for the problem of binary consensus for message-passing systems where nodes may fail by crashing.
They provided a line of self-stabilizing solutions [43, 39, 40, 31, 29].
This line follows the approach proposed by Dolev, Petig, and Schiller [20, 19] for self-stabilization in the presence of seldom fairness.
Namely, in the absence of transient-faults, these self-stabilizing solutions are wait-free and no assumptions are made regarding the system's synchrony or fairness of its scheduler. However, the recovery from transient faults does require fair execution, to perform a global reset, see [29], but only during the recovery period.
The studied problem is more challenging than the above due to the presence of Byzantine processes and transient faults.
Thus, we consider synchrony assumptions.

Our contribution

We propose an important building block for reliable distributed systems: a new SSBFT mechanism  for recycling SSBFT consensus objects.
The proposed mechanism stabilizes within expected $\bigO(\kappa)$ synchronous rounds, where $\kappa \in \bigO(t)$ is a predefined constant (that depends on synchrony assumptions) and $t$ is an upper bound on the number of Byzantine processes.
We also present, to the best of our knowledge, the first SSBFT synchronous multivalued consensus solution.
The novel composition of (i) SSBFT recycling and (ii) SSBFT recyclable objects has a long line of applications, such as replication and blockchain.
Thus, our transformation advances the state of the art by facilitating solutions that are more fault-tolerant than the existing implementations, which cannot recover from transient faults.

For convenience, a Glossary is provided in Table <ref>.

Notation     Meaning

BC     Byzantine-tolerant Consensus
BDH         Ben-Or, Dolev, and Hoch [7]
BFT        non-self-stabilizing Byzantine fault-tolerant solutions

COR     Consensus Object Recycling (Definition <ref>)

DPS     Dolev, Petig, and Schiller [21]
MMR     Mostéfaoui, Moumen, and Raynal [46]
RCCs     random common coins
SSBFT        self-stabilizing Byzantine fault-tolerant
$\kappa\mathit{-}SGC$       $\kappa$-state global clock

\begin

local variables:

the algorithm's local state is defined here.

$delivered[\sP]:=[\false,\ldots,\false]$ delivery indications; $delivered[i]$ stores the local

indication and $delivered[j]$ stores the last received indication from $p_j \in \sP$

$\mathit{initState} := (\bullet,$ $[\false,\ldots,\false])$

$\mathsf{recycle}()$ do (local state, $delivered)$ $ \gets \mathit{initState}$  also initialize all attached communication channels <cit.>

$\mathsf{wasDelivered}()$ do {if $\exists S \subseteq\sP: n\mathit{-}t\leq |S|: \forall {p_k \in S} : delivered[k]=\true$ then return $1$ else return $0$;}

operations: $\mathsf{propose}(v)$ do $\{$implement the algorithm logic$\}$

$\mathsf{result}()$ do
there is a decided value{$delivered[i]\gets \true$; $v$}
an error occurred{$delivered[i]\gets \true$; }
else return $\bot$;

do forever

$\mathsf{result}()=\bot$$delivered[i]\gets \bot$consistency test

implementation of the algorithm's logic

$p_j \in \sP$send $\mathrm{EST}(\bullet,$$delivered[i])$  to $p_j$

upon $\mathrm{EST}(\bullet,$$delivered\mathit{J})$  arrival from $p_j$

$delivered[j]\gets delivered\mathit{J}$

merge arriving information with the local one

A recyclable variation on GMRS; code for node $p_i$$p_i$'s code.
\end

Basic Result: Recyclable SSBFT Consensus Objects

In this section, we define a recyclable variation on the consensus problem, which facilitates the use of an unbounded number of consensus instances via the reuse of a constant number of objects (as presented in  <ref>).
Then, we sketch  <ref>, which presents a recyclable variation on an SSBFT asynchronous consensus algorithm (such as GMRS).
Towards the end of this section, Theorem <ref> demonstrates that  <ref> constructs recyclable SSBFT consensus objects.

Byzantine-tolerant Consensus (BC)

This problem requires agreeing on a single value from a given set $V$, which every (non-faulty) node inputs via $\mathsf{propose}()$.
It requires
BC-validity, if all non-faulty nodes propose the same value $v\in V,$ only $v$ can be decided,
BC-agreement, no two non-faulty nodes can decide different values, and
BC-completion, all non-faulty nodes decide a value.
When the set, $V$, from which the proposed values are taken is $\{0,1\}$, the problem is called binary consensus. Otherwise, it is referred to as multivalued consensus.

Recyclable Consensus Objects

We study systems that implement consensus objects using storage of constant size allocated at program compilation time.
Since these objects can be instantiated an unbounded number of times, it becomes necessary to reuse the storage once consensus is reached and each non-faulty node has received the object result via $\mathsf{result}()$.

To facilitate this, we assume that the object has two meta-statuses: used and unused.
The unused status represents both objects that were never used and those that are no longer in current use, indicating they are available (for reuse).
Our definition of recyclable objects assumes that the objects implement an interface function called $\mathsf{wasDelivered}()$ that must return $1$ anytime after the result delivery.
Recycling is triggered by the recycling mechanism ( <ref>), which invokes $\mathsf{recycle}()$ at each non-faulty node, thereby setting the meta-status of the corresponding consensus object to unused.

We specify the task of recyclable object construction as one that requires eventual agreement on the value of $\mathsf{wasDelivered}()$. In detail, if a non-faulty node $p_i$ reports delivery ($\mathsf{wasDelivered}_i()=1$), then all non-faulty nodes will eventually report delivery as well.
We clarify that during the recycling process, when at least one non-faulty node invokes $\mathsf{recycle}()$, there is no need to maintain agreement on the values of $\mathsf{wasDelivered}()$.

Algorithm outline

<ref>'s boxed code lines highlight the code lines relevant to recyclability.
The set of nodes is denoted by $\sP$. We avoid the restatement of the algorithm, and to focus on the parts that matter in this work, the other parts are given in words (cf. GMRS [32] for full details).
The code uses the symbol $\bullet$ to denote any sequence of values.
We assume that the object allows the proposal of $v$ via $\mathsf{propose}(v)$ (line <ref>).
As in $\mathsf{result}()$ (line <ref>), once the consensus algorithm decides, one of the decided value is returned (line <ref>).
Since the algorithm tolerates transient faults, the object may need to indicate an internal error via the return of the (transient) error symbol, $\blitza$ (line <ref>).
In all other cases, as long as no value was decided, the $\bot$-value is returned (line <ref>).
GMRS uses a do-forever loop that broadcasts the protocol messages (line <ref>).
Any node that receives this protocol message, merges the arriving information with the one stored by the local state (line <ref>).

Recyclable variation

<ref> uses the array $delivered[\sP]$ (initialized to the vector $[\false,\ldots,\false]$) for delivery indications, where $delivered_i[i]:p_i \in \sP$ stores the local indication and $delivered_i[j]:p_i,p_j \in \sP$ stores the indication that was last received from $p_j$. This indication is set to $\true$ whenever $\done()$ returns a non-$\bot$ value (lines <ref> to <ref>).  <ref> updates $delivered[j]$ according to the arriving values from $p_j$ (lines <ref> and <ref>). The interface function $\mathsf{wasDelivered}()$ (line <ref>) returns $1$ if at least $n-t$ entries in $delivered[]$ hold $\true$. The interface function $\mathsf{recycle}()$ (line <ref>) allows the node to restart its local state w.r.t.  <ref>.

Theorem <ref> shows that  <ref> satisfies the requirements for Recyclable Consensus Objects, which we defined above.
Following the definition of the BC problem and GMRS, the theorem assumes that every (non-faulty) node invokes $\mathsf{result}()$ infinitely often.

Suppose that every (non-faulty) node invokes $\mathsf{result}()$ infinitely often.
<ref> offers a recyclable asynchronous consensus object.

If $\exists i \in \Correct:\mathsf{wasDelivered}_i()=1$, then $\mathsf{result}_i()\neq\bot$ (line <ref>). By BC-completion, eventually $\forall j \in \Correct: \mathsf{result}_j()\neq\bot \land \mathsf{wasDelivered}_j()=1$ (lines <ref> and <ref>).

Let $R$ be an unbounded execution of  <ref> in which no (non-faulty) node invokes $\mathsf{recycle}()$.
Suppose $\exists i\in \Correct:\mathsf{wasDelivered}_i()=1$ in any system state in $R$.
We show that the system reaches a state $c \in R$ in which $\forall j \in \Correct:\mathsf{wasDelivered}_j()=1$.

By line <ref> and the assumption that $i \in \Correct:\mathsf{wasDelivered}_i()=1$ holds throughout $R$, $\mathsf{result}_i()\neq\bot$ holds in every system state $R$, $p_i$'s state encodes completion.
By BC-completion and the assumption that  <ref> is an SSBFT implementation of consensus, $\forall j \in \Correct: \mathsf{result}_j()\neq\bot$ eventually.
By lines <ref> to <ref> and the theorem assumption that every (non-faulty) node invokes $\mathsf{result}()$ infinitely often, $\forall j \in \Correct:\mathsf{wasDelivered}_j()=1$.

System Settings for the Recycling Mechanism

This model considers a synchronous message-passing system.
The system consists of a set, $\sP$, of $n$ nodes (sometimes called processes or processors) with unique identifiers.
At most $t < n/3$, out of the $n$ nodes, are faulty.
Any pair of nodes $p_i,p_j \in \sP$ has access to a bidirectional reliable communication channel, $\mathit{channel}_{j,i}$.

In the interleaving model [15], the node's program is a sequence of (atomic) steps.
Each step starts with (i) the communication operation for receiving messages that is followed by (ii) an internal computation, and (iii) finishes with a single $send$ operation.
The state, $s_i$, of node $p_i \in \sP$ includes all of $p_i$'s variables and $\mathit{channel}_{j,i}$.
The term system state (or configuration) refers to the tuple $c = (s_1, s_2, \cdots,  s_n)$.

Our model also assumes the availability of a $\kappa$-state global clock, reliable communications, and random common coins (RCCs).

A $\kappa$-state global clock

We assume that the algorithm takes steps according to a common global pulse (beat) that triggers a simultaneous step of every node in the system.
Specifically, we denote synchronous executions by $R=c[0],c[1],\ldots$, where $c[x]$ is the system state that immediately precedes the $x$-th global pulse.
And, $a_i[x]$ is the step that node $p_i$ takes between $c[x]$ and $c[x+1]$ simultaneously with all other nodes.
We also assume that each node has access to a $\kappa$-state global clock via the function $clock(\kappa)$, which returns an integer between $0$ and $\kappa-1$.
Algorithm 3 of BDH [7] offers an SSBFT $\kappa$-state global clock that stabilizes within a constant time.

Reliable communication

Recall that we assume the availability of reliable communication.
Also, any non-faulty node $p_i \in \sP$ starts any step $a_i[x]$ with receiving all pending messages from all nodes. And, if $p_i$ sends any message during $a_i[x]$, it does so only at the end of $a_i[x]$. We require (i) any message that a non-faulty node $p_i$ sends during step $a_i[x]$ to another non-faulty node $p_j$ is received at $p_j$ at the start of step $a_j[x+1]$, and
(ii) any message that $p_j$ received during step $a_j[x+1]$, was sent at the end of $a_i[x]$.

Random common coins (RCCs)

As already mentioned, BDH presented a synchronous SSBFT RCCs solution for message passing systems. Algorithm $\mathcal{A}$, which has the output of $rand_i \in \{0,1\}$, is said to provide an RCC if $\mathcal{A}$ satisfies the following:

* RCC-completion: $\mathcal{A}$ provides an outputcompletes within $\Delta_{\mathcal{A}} \in \mathbb{Z}^+$ synchronous rounds.

* RCC-unpredictability: Denote by $E_{x\in \{0,1\}}$ the event that for any non-faulty process, $p_j$, $rand_j=x$ holds with constant probability $p_x > 0$. Suppose either $E_0$ or $E_1$ occurs at the end of round $\Delta_{\mathcal{A}}$. We require that the adversity can predict the output of $\mathcal{A}$ by the end of round $\Delta_{\mathcal{A}}- 1$ with a probability that is not greater than $1 - \min\{p_0, p_1\}$.

Following [46], we assume that $p_0=p_1=1/2$.

Our solution depends on the existence of a self-stabilizing RCC service, BDH.
BDH considers (progress) enabling instances of RCCs if there is $x \in \{0,1\}$ such that for any non-faulty process $p_i$, we have $rand_i=x$. BDH correctness proof depends on the consecutive existence of two enabling RCCs instances.

Legal executions

The set of legal executions ($LE$) refers to all the executions in which the requirements of task $T$ hold. In this work, $T_{\text{recycl}}$ denotes the task of consensus object recycling (specified in  <ref>), and $LE_{\text{recycl}}$ denotes the set of executions in which the system fulfills $T_{\text{recycl}}$'s requirements.

Arbitrary node failures

As explained in  <ref>, Byzantine faults model any fault in a node including crashes, arbitrary behavior, and malicious behavior [37].
For the sake of solvability [37, 48, 57], our fault model limits only the number of nodes that can be captured by the adversary. That is, the number, $t$, of Byzantine failure needs to be less than one-third of the number, $n$, of nodes.
The set of non-faulty nodes is denoted by $\Correct$.

Arbitrary transient-faults

We consider any temporary violation of the assumptions according to which the system was designed to operate. We refer to these violations and deviations as arbitrary transient-faults and assume that they can corrupt the system state arbitrarily (while keeping the program code intact).
Our model assumes that the last arbitrary transient fault occurs before the system execution starts [4, 15]. Also, it leaves the system to start in an arbitrary state.

An algorithm is self-stabilizing for the task of $LE$, when every (unbounded) execution $R$ of the algorithm reaches within a finite period a suffix $R_{legal} \in LE$ that is legal. Namely, Dijkstra [14] requires $\forall R:\exists R': R=R' \circ R_{legal} \land R_{legal} \in LE \land |R'| \in \mathbb{Z}^+$, where the operator $\circ$ denotes that $R=R' \circ R''$ is the concatenation of $R'$ with $R''$. The part of the proof that shows the existence of $R'$ is called the convergence (or recovery) proof, and the part that shows that $R_{legal} \in LE$ is called the closure proof.
We clarify that once the execution of a self-stabilizing system becomes legal, it stays legal due to the property of closure.
The main complexity measure of a self-stabilizing system is its stabilization time, which is the length of the recovery period, $R'$, which is counted by the number of its synchronous rounds.

SSBFT Recycling Mechanism

We present an SSBFT recycling mechanism for recyclable objects ( <ref>).
The mechanism is a service that recycles consensus objects via the invocation of $\mathsf{recycle}()$ by all (non-faulty) nodes.
The coordinated invocation of $\mathsf{recycle}()$ can occur only after the consensus object has terminated and the non-faulty nodes have delivered the result, via $\mathsf{result}()$, as indicated by $\mathsf{wasDelivered}()$.

Consensus Object Recycling (COR)

Definition <ref> specifies the COR problem for a single object.
COR-validity-1 is a safety property requiring that $\mathsf{recycle}()$ is invoked only if there was at least one reported delivery by a non-faulty node.
COR-validity-2 is a liveness property requiring that eventually $\mathsf{recycle}()$ is invoked.
COR-agreement is a safety property requiring that all non-faulty nodes simultaneously set the object's status to unused.
This allows any node $p_i$ to reuse the object immediately after the return from $\mathsf{recycle}_i()$.

The solution uses recyclable objects ( <ref>), a  recycling mechanism ( <ref>), multivalued consensus ( <ref>), and SIG-index ( <ref>).  <ref> and <ref> solve the BC problem ( <ref>) for asynchronous,  and resp., synchronous settings.  <ref> and <ref> solve the COR,  resp., SGI-index problems ( <ref>).

The following properties are required:

* COR-validity-1: If a non-faulty node, $p_j$, invokes $\mathsf{recycle}_j()$, then at least one non-faulty node, $p_i$, reported delivery.
no non-faulty node, $p_j$, invokes $\mathsf{recycle}_j()$ if only faulty nodes report delivery.

* COR-validity-2: If all non-faulty nodes report delivery, then at least one non-faulty node, $p_j$, eventually invokes $\mathsf{recycle}_j()$.

* COR-agreement: If a non-faulty node invokes $\mathsf{recycle}()$, then all non-faulty nodes, $p_i$, invoke $\mathsf{recycle}_i()$ simultaneously.

Multiple objects

We also specify that the recycling mechanism makes sure that, at any time, there are at most a constant number, $logSize$, of active objects, objects that have not completed their tasks.
Once an object completes its task, the recycling mechanism can allocate a new object by moving to the next array entry as long as some constraints are satisfied.
Specifically, the proposed solution is based on a synchrony assumption that guarantees that every (correct) node retrieves (at least once) the result of a completed object, $x$, within $logSize$ synchronous rounds since the first time in which at least $t+1$ (correct) nodes have retrieved the result of $x$, and thus, $x$ can be recycled.

Solution overview

The SSBFT recycling solution is a composition of several algorithms, see  <ref>. Our recycling mechanism is presented in  <ref>. It allows every (correct) node to retrieve at least once the result of any object that is stored in a constant-size array and yet over time that array can store an unbounded number of object instances.
The proposed service mechanism ( <ref>) ensures that every instance of the recyclable object, which is implemented by  <ref>, is guaranteed that every (correct) node calls $\done()$ (line <ref>) at least once before all (correct) nodes simultaneously invoke $\mathsf{recycle}()$ (line <ref>). This aligns with the solution architecture ( <ref>).

We consider the case in which the entity that retrieves the result of object $obj$ might be external (and perhaps, asynchronous) to the proposed solution. The proposed solution does not decide to recycle $obj$ before there is sufficient evidence that, within $logSize$ synchronous cycles, the system is going to reach a state in which $obj$ can be properly recycled. Specifically, Assumption <ref> considers an event that can be locally learned about when $\mathsf{wasDelivered}()$ returns `1' (line <ref>).

\begin

$indexNum$ number of indices of recyclable objects
$logSize \in \{0,\ldots,indexNum-2\}$ user-defined bound on the object log size

$obj[indexNum]:$ array of recyclable objects, GMRSarray of recyclable objects, GMRS. Note that during legal execution only at most $(logSize+1)$ objects are stored at any given point of time

$\mathit{ssbftIndex}:$ an SSBFT index of the current object in use ( <ref>)

upon pulse
$x \notin \{y ~\bmod$ $ indexNum:y\in \{z-logSize,\ldots,z\}\}$ where $z=indexNum+\mathit{ssbftIndex}.getIndex()$$obj[x].\mathsf{recycle}()$
$x \notin \{y ~\bmod$ $ indexNum:y\in \{z-logSize,\ldots,z\}\}$ where $z=indexNum+\mathit{ssbftIndex}.getIndex()$$obj[x].\mathsf{recycle}()$

SSBFT synchronous recycling with a predefined log size; code for node $p_i$$p_i$'s code
\end

[A bounded time result retrieval]

Let us consider the system state, $c[r]$, in which the result of object $obj$ was retrieved by at least $t+1$ (correct) nodes. We assume, within $logSize$ synchronous cycles from $c[r]$, the system reaches a state, $c[r+logSize]$, in which all $n-t$ (correct) nodes have retrieved the result of $obj$ at least once.

<ref>'s recycling guarantees are facilitated by an SSBFT multivalued consensus object ( <ref>).
It helps to decide on a single piece of evidence from all collected ones (regarding recyclability) and  <ref> uses the agreed evidence for updating the value of the index that points to the current entry in the object array.
We later add details on  <ref> before proving its correctness (Theorem <ref>).

Evidence collection using an SSBFT (multivalued) consensus ( <ref>)

The SSBFT multivalued consensus protocol returns within $t+1$ synchronous rounds an agreed non-$\bot$ value as long as at least $t+1$ nodes proposed that value, at least one (correct) node proposed that value.
As mentioned, $\mathsf{wasDelivered}()$ (line <ref>) provides the input to this consensus protocol.
Thus, whenever '1' is decided, at least one (correct) node gets an indication from at least $n-t$ nodes that they have retrieved the results of the current object.
This implies that by at least $t+1$ (correct) nodes have retrieved the results, and, by Assumption <ref>, all $n-t$ (correct) nodes will retrieve the object result within a known number of synchronous rounds.
Then, the object could be recycled.
We later add details on  <ref> before proving its correctness (Theorem <ref>).

SSBFT simultaneous increment-or-get index (SIG-index)

<ref> allows the proposed solution to keep track of the current object index that is currently used as well as facilitate synchronous increments to the index value.
We call this task simultaneous increment-or-get index (SIG-index).
During legal executions of  <ref>, the (correct) nodes assert their agreement on the index value and update the index according to the result of the agreement on $\mathsf{wasDelivered}()$'s value.
We later add details on  <ref> before proving its correctness (Theorem <ref>).

\begin

variables: $currentResult$ stores the most recent result of $co$

$co$ a (non-self-stabilizing) BFT (multivalued) consensus object

interface required:

$input():$ source of (the proposed values) of the given consensus protocol

interface provided:

$\done()$: do $\Return{(currentResult)}$  most recent $co$'s decided valuedecided value of the most recent $co$'s invocation

message structure:
$\langle appMsg \rangle$, where $appMsg$ is the application message, a message sent by the given consensus protocol

upon pulse

let $M$ be a message that holds at $M[j]$ the arriving $\langle appMsg_j \rangle$ messages from $p_j$ for the current synchronous round and $M'=[\bot, \ldots,\bot]$

$currentResult \gets co.\done()$
$M' \gets co.\mathit{propose}(input())$  for recycling $input()\equiv\mathsf{wasDelivered}()$

$clock(cycleSize) \in \{1,\ldots,t\}$$M' \gets co.\mathit{process}(M)$

$p_j \in \sP$send $\langle M'[j] \rangle$ to $p_j$

SSBFT synchronous multivalued consensus; code for node $p_i$$p_i$'s code
\end

Scheduling strategy

As mentioned, our SSBFT multivalued consensus requires $t+1$ synchronous rounds to complete and provide input to  <ref> and $\kappa-(t+1)$ synchronous rounds after that, any (correct) node can recycle the current object (according to the multivalued consensus result), where $\kappa=\max\{t+1,logSize\}$.
Thus,  <ref> has to defer its index updates until that time.  <ref> depicts this scheduling strategy, which considers the schedule cycle of $\kappa$.
That is, the SIG-index and multivalued consensus starting points are $0$ and $\kappa-4$, respectively.
Note that  <ref> does not require scheduling since it accesses the index only via  <ref>'s interface of SIG-index, see  <ref>.

\begin

constants: $I:$ bound on the number of states an index may have

$\mathit{index} \in \{0,\ldots, I-1\}:$ a local copy of the global logical object index

$\mathit{ssbftCO}:$ an SSBFT multivalued consensus object ( <ref>) that is used for agreeing on the recycling state, 1 when there is a need to recycle (otherwise 0)

interfaces provided:

$getIndex()$ do $index$

message structure:
$\langle index \rangle$: the logical object index

upon pulse

let $M$ be the arriving $\langle index_j\rangle$ messages from $p_j$

$\kappa-4$broadcast $\langle index=getIndex() \rangle$

let $propose := \bot$
$\exists v \neq \bot:|\{  \langle v  \rangle \in M\}|\geq \emsA{n-t}$$propose \gets v$

broadcast $\langle propose \rangle$

let $bit := 0$; $save \gets \bot$

$\exists s \neq \bot:|\{  \langle s  \rangle \in M\}|> n/2$$save\gets s$

$|\{\langle save \neq \bot\rangle \in M\}|\geq \emsA{n-t}$$bit \gets 1$

$save = \bot$$save \gets 0$

broadcast $\langle bit\rangle$

let $\mathit{inc} := 0$

$\mathit{ssbftCO}.\done()$$\mathit{inc}\gets 1$

$|\{\langle 1\rangle \in M\}|\geq \emsA{n-t}$$\mathit{index} \gets (save + \mathit{inc})\bmod I$
$|\{\langle 0\rangle \in M\}|\geq \emsA{n-t}$$\mathit{index} \gets 0$
$\mathit{index} \gets rand(save + \mathit{inc}) \bmod I$

SSBFT synchronous SIG-index; $p_i$'s code
\end

Communication piggybacking and multiplexing

We use a piggybacking technique to facilitate the spread of the result (decision) values of the recyclable objects. As  <ref> illustrates, all communications are piggybacked. Specifically, we consider a meta-message $MSG()$ that has a field for each message sent by all algorithms in  <ref>.
That is, when any of these algorithms is active, its respective field in $MSG()$ includes a non-$\bot$ value.
With respect to GMRS's field, $MSG()$ includes the most recent message that GMRS has sent (or currently wishes to send).
This piggybacking technique allows the multiplexing of timed and reliable communication (assumed for the recycling mechanism) and fair communication (assumed for the recyclable object).

SSBFT recycling in $\mathsf{BSMP_{n,t}[t < n/3,(t+1)\mathit{-}SGC]}$ ( <ref>)

As mentioned,  <ref> has an array, $obj[]$ (line <ref>), of $indexNum$ recyclable objects (line <ref>). The array size needs to be larger than $logSize$ (line <ref> and Assumption <ref>).

<ref>'s variable set also includes $\mathit{ssbftIndex}$, which is an integer that holds the entry number of the latest object in use.  <ref> accesses the agreed current index via $\mathit{ssbftIndex}.getIndex()$.
This lets the code to nullify any entry in $obj[]$ that is not $\mathit{ssbftIndex}.getIndex()$ or at most $logSize$ older than $\mathit{ssbftIndex}.getIndex()$.
Theorem <ref> shows  <ref>'s correctness.

The solution schedule uses a cycle of $\kappa=\max\{t+1,logSize\}$ synchronous rounds.

SSBFT synchronous multivalued consensus

<ref> assumes access to a deterministic (non-self-stabilizing) BFT (multivalued) consensus object, $co$, such as the ones proposed by Kowalski and Mostéfaoui [36] or Abraham and Dolev [1], for which completion is guaranteed to occur within $t+1$ synchronous rounds. We list our assumptions regarding the interface to $co$ in Definition <ref>.

Required consensus object interface

Our solution uses the technique of recomputation of $co$'s floating output <cit.>, where $co$ is specified in Definition <ref>.

Let $co$ be a BFT (non-self-stabilizing) synchronous multivalued consensus that implements the following.

* $\mathit{restart}()$ sets $co$ to its initial state.

* $\mathit{propose}(v)$ proposes the value $v$ when invoking (or re-invoking) $co$. This operation is effective only after $\mathit{restart}()$ was invoked. The returned value is a message vector, $M[]$, that includes all the messages, $M[j]$, that $co$ wishes to send to node $p_j$ for the current synchrony round.

* $\mathit{process}(M)$ runs a single step of $co$. The input vector $M$ includes the arriving messages for the current synchronous round, where $M[j]$ is $p_j$'s message. The returned value is a message vector that includes all the messages that $co$ wishes to send for the current synchrony round. This operation is guaranteed to work correctly only after all (correct) nodes have simultaneously taken a consecutive sequence of steps that include invocations of either (i) $\mathit{process}()$, or (ii) $\mathit{restart}()$ immediately before proposing a non-$\bot$ value via the invocation of $\mathit{propose}()$.

* $\done()$ returns a non-$\bot$ results after the completion of $co$. The returned value is required to satisfy the consensus specifications only if all (correct) nodes have simultaneity taken a sequence of correct $\mathit{process}()$ invocations.

Detailed description

<ref>'s set of variables includes $co$ itself (line <ref>) and the current version of the result, $currentResult$ (line <ref>). This way, the SSBFT version of $co$'s result can be retrieved via a call to $\done()$ (line <ref>).  <ref> proceeds in synchronous rounds. At the start of any round, node $p_i$ stores all the arriving messages at the message vector $M$ (line <ref>).

When the clock value is zero (line <ref>), it is time to start the re-computation of $co$'s result. Thus,  <ref> first stores the current value of $co$'s result at $currentResult_i$ (line <ref>). Then, it restarts $co$'s local state and proposes a new value to $co$ (lines <ref> and <ref>). For the recycling solution presented in this paper, the proposed value is retrieved from $\mathsf{wasDelivered}()$ (line <ref>).

For the case in which the clock value is not zero (line <ref>),  <ref> simply lets $co$ process the arriving messages of the current round.

Both for the case in which the clock value is zero and the case it is not,  <ref> broadcasts $co$'s messages for the current round (line <ref>).

Correctness proof

Theorem <ref> shows that  <ref> stabilizes within $2\kappa$ synchronous rounds.

<ref> is an SSBFT deterministic (multivalued) consensus solution that stabilizes within $2\kappa$ synchronous rounds.

Let $R$ be an execution of  <ref>
Within $\kappa$ synchronous rounds, the system reaches a state $c \in R$ in which $clock(\kappa)=0$ holds.
Immediately after $c$, every (correct) node, $p_i$, simultaneously restarts $co_i$ and proposes the input (lines <ref> and <ref>) before sending the needed messages (line <ref>).
Then, for the $t<\kappa$ synchronous rounds that follow, all (correct) nodes simultaneously process the arriving messages and send their replies (line <ref> and <ref>).
Thus, within $2\kappa$ synchronous rounds from $R$'s start, the system reaches a state $c'\in R$ in which $clock(\kappa)=0$ holds.
Also, in the following synchronous round, all (correct) nodes store $co$'s results.
These results are guaranteed to be correct due to Definition <ref>'s assumptions.

SSBFT simultaneous increment-or-get index

The task of simultaneous increment-or-get index (SGI-index) requires all (correct) nodes to maintain identical index values that all nodes can independently retrieve via $getIndex()$.

The task assumes that all increments are performed according to the result of a consensus object, $\mathit{ssbftCO}$, such as  <ref>.  <ref> presents an SGI-index solution that recovers from disagreement on the index value using RCCs. That is, whenever a (correct) node receives $n-t$ reports from other nodes that they have each observed $n-t$ identical index values, an agreement on the index value is assumed and the index is incremented according to the most recent result of $\mathit{ssbftCO}$. Otherwise, a randomized strategy is taken for guaranteeing recovery from a disagreement on the index value. Our strategy is inspired by BDH [7]'s SSBFT clock synchronization algorithm.

Detailed description

<ref> is active during four clock phases, $\kappa-4$ to $\kappa-1$. Each phase starts with storing all arriving messages (from the previous round) in the array, $M$ (line <ref>). The first phase broadcasts the local index value (line <ref>). The second phase lets each node vote on the majority arriving index value, or $\bot$ in case such value was not received (lines <ref> to <ref>). The third phase resolves the case in which there is an arriving non-$\bot$ value, $save$,  that received sufficient support when voting during phase two (lines <ref> to <ref>). Specifically, if $save\neq \bot$ exists, then $\langle bit=1\rangle$ is broadcast. Otherwise, $\langle bit=0\rangle$ is broadcast. On the fourth phase (lines <ref> to <ref>), the (possibly new) index is set either to be the majority-supported index value of phase two plus $inc$ (lines <ref> to <ref>), where $inc$ is the output of $\mathit{ssbftCO}$, or (if there was insufficient support) to a randomly chosen output of the RCC (lines <ref> and <ref>).

Correctness proof

Theorem <ref> bounds  <ref>'s stabilization time.

<ref> is an SSBFT SGI-index implementation that stabilizes within expected $\bigO(1)$ synchronous rounds.

Lemma <ref> implies that, within $O(1)$ of expected rounds, all (correct) nodes have identical $index$ values. Recall that $c[r] \in R$ is (progress) enabling if $\exists x \in \{0,1\}: \forall i \in \Correct: rand_i=x$ holds at $c[r]$ ( <ref>).
Due to the page limit, the Closure proof appears in [33].

Let $r> \kappa$. Suppose $c[r] \in R$ is (progress) enabling system state ( <ref>) for which $clock(\kappa) = \kappa - 1$ holds. With probability at least $\min \{p_0, p_1\}$, all (correct) nodes have the same $index$ at $c[r+1]$.

The proof is implied by claims <ref> to <ref>.

Suppose no (correct) $p_i \in \sP$ receives $\langle x\rangle$ from at least $n -t$ different nodes  at $a_i[r]$.
With probability $p_0$, any (correct) $p_j $ assigns $0$ to $index_j$ at $a_j[r]$.

The proof is implied directly from lines <ref> to <ref>.

Suppose $p_i : i \in \Correct$ receives $\langle 0\rangle$ from at least $n-t$ different nodes at $a_i[r]$. Also, $p_j : j\in \Correct$ receive $\langle x\rangle$ from at least $n-t$ different nodes at $a_j[r]$, where $i=j$ may or may not hold. The step $a_j[r]$ assigns $0$ to $index_j$.

Line <ref> implies the proof since $x=0$.

Suppose $p_i$ receives $\langle 1\rangle$ from at least $n-t$ different nodes at $a_i[r]$.
At $c[r]$, $(\mathit{ssbftCO}_i.\done(),save_i)=(\mathit{ssbftCO}_j.\done(),save_j):i,j \in \Correct$.

At $c[r]$, $\mathit{ssbftCO}_i.\done() = \mathit{ssbftCO}_j.\done()$ holds (BC-agreement).

There is $p_k :k\in \Correct$ that has sent $\langle 1\rangle$ at $a[r-1]$. By lines <ref> to <ref>, $p_j$ receives at $a_j[r-1]$ the message $\langle x\rangle$ from at least $n-t$ different nodes, where $x=save_j \neq \bot$.

Any (correct) node broadcasts (line <ref>) either $\bot$ or $x$ at $a[r-2]$. At $a[r-1]$, (correct) nodes receive at most $f <n-2f$ values that are neither $\bot$ nor $x\neq \bot$. Thus, $save_i = save_j$.

Let $i,j \in \Correct$. Suppose $p_i$ receives $\langle 1\rangle$ from at least $n-t$ different nodes at $a_i[r]$ and $p_j$ receives $\langle x\rangle$ from at least $n-t$ different nodes at $a_j[r]$. With a probability of at least $\min \{p_0, p_1\}$, $a_i[r]$ and $a_j[r]$ assign the same value to $index_j$, and resp., $index_j$.

Steps $a[r-1]$ and $a[r]$ independently assign $x$, and resp., $rand$.
With a probability of at least $\min \{p_0, p_1\}$, all (correct) nodes update $index$ to either $0$ or $save+inc$ (Claim <ref>).

Let $R$ be an execution of algorithms <ref> and <ref> that is legal w.r.t.  <ref> (Theorem <ref>).  <ref> is an SSBFT SGI-index implementation that stabilizes within expected $\bigO(1)$ synchronous rounds.

Corollaries <ref> and <ref> are needed for Lemmas <ref> and <ref>. The pigeonhole principle implies Corollary <ref>.

Let $V_{x \in \{a,b\}}$ be two $n$-length vectors that differ in at most $f<n/3$ entries. For any $x \in \{a,b\}$, suppose $V_x$ contains $n-t$ copies of $v_x$. Then $v_a = v_b$.

Corollary <ref> is implied by Corollary <ref>.

Let $c[r] \in R$ be a system state in which $clock(\kappa)=\kappa-3$ and $X=\{x_i:i\in\Correct\}$ be the set of values encoded in the messages $\langle x_i\rangle$ that any (correct) node, $p_i \in \sP$, broadcasts in line <ref> at the end of $a_i[r]$. The set $X$ includes at most one non-$\bot$ value.

Lemma <ref> implies that, within $O(1)$ of expected rounds, all (correct) nodes have identical $index$ values. Recall that $c[r] \in R$ is (progress) enabling if $\exists x \in \{0,1\}: \forall i \in \Correct: rand_i=x$ holds at $c[r]$ ( <ref>).

Let $r> \kappa$. Suppose $c[r] \in R$ is (progress) enabling system state ( <ref>) for which $clock(\kappa) = \kappa - 1$ holds. With probability at least $\min \{p_0, p_1\}$, all (correct) nodes have the same $index$ at $c[r+1]$.

The proof is implied by claims <ref> to <ref>.

Suppose (i) there is no value $x \in \{0,1\}$ and (ii) there is no (correct) node $p_i \in \sP$ that receives at the start of step $a_i[r]$ the message $\langle x\rangle$ from at least $n-t$ different nodes. For any (correct) node, $p_j \in \sP$, it holds that step $a_j[r]$ assigns $0$ to $index_j$ with probability $p_0$.

The proof is implied directly from lines <ref> to <ref>.

Suppose there is a (correct) node $p_i \in \sP$ that receives at the start of step $a_i[r]$ the message $\langle 0\rangle$ from at least $n-t$ different nodes. Also, suppose there is $x \in \{0,1\}$ and a (correct) node $p_j \in \sP$ that receives at the start of step $a_j[r]$ the message $\langle x\rangle$ from at least $n-t$ different nodes, where $i=j$ may or may not hold. The step $a_j[r]$ assigns $0$ to $index_j$.

Line <ref> implies the proof since $x=0$ (Corollary <ref>).

Suppose there is a (correct) $p_i \in \sP$ that receives at the start of step $a_i[r]$ the message $\langle 1\rangle$ from at least $n-t$ different nodes. Let $p_j \in \sP$ be a (correct) node. At $c[r]$, $\mathit{ssbftCO}_i.\done() = \mathit{ssbftCO}_j.\done()$ and $save_i=save_j$ hold.

At $c[r]$, $\mathit{ssbftCO}_i.\done() = \mathit{ssbftCO}_j.\done()$ holds ( <ref>'s agreement property). We show that $save_i=save_j$ holds at $c[r]$.

Since $p_i$ has received $\langle 1\rangle$ from at least $n-t$ different nodes at the start of $a_i[r]$, we know that there is a (correct) node, $p_k \in \sP$, that has sent $\langle 1\rangle$ at the end of $a[r-1]$. By lines <ref> to <ref>, node $p_j$ receives at the start of $a_j[r-1]$ the message $\langle x\rangle$ from at least $n-t$ different nodes, where $x=save_j \neq \bot$.

By Corollary <ref>, any (correct) node broadcasts (line <ref>) either $\bot$ or $x$ at the end of step $a[r-2]$. This means that at the start of $a[r-1]$, (correct) nodes receive at most $f <n-2f$ messages with values that are neither $\bot$ nor $x\neq \bot$. Therefore, $save_i = save_j$ since, at the start of $a_i[r]$ and $a_j[r]$ both $p_i$, and resp., $p_j$ receive from at least $n-t$ different nodes the messages  $\langle x_i \rangle$, and resp., $\langle x_j \rangle$, where neither $x_i$ nor $x_j$ is $\bot$.

Suppose there is a (correct) node $p_i \in \sP$ that receives at the start of step $a_i[r]$ the message $\langle 1\rangle$ from at least $n-t$ different nodes. Suppose there is $x \in \{0,1\}$ and a (correct) node $p_j \in \sP$ that receives at the start of step $a_j[r]$ the message $\langle x\rangle$ from at least $n-t$ different nodes, where $i=j$ may or may not hold. With a probability of at least $\min \{p_0, p_1\}$, the steps $a_i[r]$ and $a_j[r]$ assign the same value to $index_j$, and resp., $index_j$.

By Corollary <ref>, $x=1$. The step $a[r-1]$ determines $x$'s value and $rand$ is chosen at the start of step $a[r]$. Due to $rand$'s unpredictability ( <ref>), $rand$ and $x$ are two independent values.

Thus, with a probability of at least $\min \{p_0, p_1\}$, all (correct) nodes update $index$ in the same manner, to either $0$ or $save+inc$ (Claim <ref>), where $save$ and $inc$ are values determined by lines <ref> to <ref>, and resp. <ref> to <ref>.

Lemma <ref> shows that all (correct) nodes forever agree on their indexes and simultaneously increment them by one (modulo $I$) only when $clock(\kappa)=\kappa-1$ and $\mathit{ssbftCO}_i.\done()=1$. Lemma <ref> uses the following notation. Let $R=c[0],c[1],\ldots,c[r],\ldots$ an unbounded synchronous execution of  <ref>, where $c[r]$ is the system state that immediately precedes the arrival of the $r$-th common pulse. Denote by $indices^{start}_r$ and $indices^{end}_r$ the sets of all $index_i: i \in \Correct$ values of (correct) nodes at $c[r]$, and resp., $c[r+1]$, the beginning, and resp., the end of step $a[r]$. Note that, for all $r$ and $x \in \{start, end\}$, we have $indices^{x}_r \subseteq \{0, 1,\ldots, I -1\}$.

Let $c[r] \in R$, such that $clock(\kappa) = \kappa-1$ at $c[r]$. Suppose $indices^{end}_r = \{v\neq\bot\}$. For every $c[r'] \in R:r'  \in \{r+1,r+\kappa \}$ it holds that $indices^{start}_{r'} = \{ v + x \bmod  I \}$ where $x1$ when $r'=r+\kappa$ and $\mathit{ssbftCO}.\done()=1$. Otherwise, $x=0$, when $r'  \in \{r+1,\ldots ,r+\kappa-1 \}$ or $\mathit{ssbftCO}.\done()\neq 1$.

For $r' = r + 1$ the lemma holds since, by definition, $\forall r'': indices^{end}_{r''} = indices^{start}_{r''+1}$. Also, for any system state $c[r']:r' \in \{r+1,\ldots,r +\kappa-1\}$, no (correct) node, $p_i \in \sP$, updates $index_i$ during the step, $a_i[r']$, since $clock(\kappa)\neq\kappa-1$ at $c[r']:r' \in \{r+1,\ldots,r +\kappa-1\}$ and thus lines <ref> to <ref> are not executed, which are the only lines that update $index_i$.

It remains to show that all (correct) nodes, $p_i \in \sP$, update $index_i$ in the same way during the steps $a_i[r']:r'=r+\kappa$ that immediately follow $c[r']$. This is due to the agreement property of  <ref>, the arguments above about $c[r']:r' \in \{r+1,r +\kappa-1\}$ as well as Claim <ref>.

$indices^{start}_{r+\kappa} = \{v\}:v\neq\bot$.

By the schedule ( <ref>) and its cycle length, $\kappa$, we know that  <ref> is not active between $c[r+1]$ and $c[r+\kappa-3]$, but it is active during steps $a[r+\kappa-3]$, $a[r+\kappa-2]$, $a[r+\kappa-1]$, and $a[r+\kappa]$. During steps $a[r+\kappa-3]$, all (correct) nodes broadcast $\langle v \rangle$ (line <ref>). Thus, at the start of steps $a[r+\kappa-3]$, all (correct) nodes receive $\langle v \rangle$ at least $n-t$ times (from different nodes). Thus, during $a[r+\kappa-2]$, all (correct) nodes assign $v$ to their $propose$ variables (line <ref>) and broadcast  $\langle v \rangle$ (line <ref>). By similar arguments, during $a[r+\kappa-1]$, all (correct) nodes assign $v$ and $1$ to their $save$, and resp., $bit$ variables (lines <ref> to <ref>) and broadcast $\langle 1 \rangle$ (line <ref>). Therefore, all (correct) nodes receive $\langle 1 \rangle$ at least $n -t$ times. This implies that during $a[r+\kappa]$, the if-statement condition in line <ref> holds and thus $indices^{start}_{r+\kappa} = \{v\neq\bot\}$ holds.

<ref> is an SSBFT recycling mechanism (Definition <ref>) for $\mathsf{BSMP_{n,t}[\kappa\mathit{-}SGC,t < n/3,RCCs]}$ that stabilizes within expected $\bigO(\kappa)$ synchronous rounds.

COR-validity-1 and COR-validity-2 are implied by arguments 1 and 2, respectively.

COR-agreement is implied by Argument 3.
The stabilization time is due to the underlying algorithms.

Argument 1 During legal executions, if the value of $index$ is incremented (line <ref>), $\exists i \in \Correct:\mathsf{wasDelivered}()=1$ holds.

By the assumption that $\mathsf{wasDelivered}()$ provides the proposed values used by the SSBFT multivalued consensus.
Specifically,  <ref> explicitly requires this, see the comment in line <ref>.
The value decided by this SSBFT consensus is used in line <ref> determines whether, during legal executions, the value of $index$ is incremented module $I$ (line <ref>), say, from $ind_1$ to $ind_2$.

Argument 2 During legal executions, if $\forall i \in \Correct:\mathsf{wasDelivered}_i()=1$ holds, $index$ is incremented.

Implied by Argument 1 and BC-validity of the consensus protocol.

Argument 3 During legal executions, the increment of $index$ is followed by the recycling of a single object, $obj[x]$, the same for all (correct) nodes.

Line <ref> ( <ref>) uses the value of $index$ as the returned value from $\mathit{ssbftIndex}.getIndex()$ when calculating the set $S(ind) = \{y ~\bmod indexNum:y\in \{ indexNum + ind-logSize,\ldots, indexNum + ind\}\}$, where $ind \in \{ind_1,ind_2\}$.
For every $x \notin S(ind)$, $obj[x].\mathsf{recycle}()$ is invoked.
Since $ind_2=ind_1+1 \bmod I$, during legal executions, there is exactly one index, $x$, that is in $S(ind_1)$ but not in $S(ind_2)$.
$x=(indexNum + ind_1-logSize) \bmod indexNum$ and only $obj[x]$ is recycled by all (correct) nodes (BC-agreement of the SSBFT consensus).

We have presented an SSBFT algorithm for object recycling.

Our proposal can support an unbounded sequence of SSBFT object instances.
The proposed solution offers optimal fault-tolerance, and the expected stabilization time is in $\bigO(t)$ synchronous rounds.
We believe that this work is preparing the groundwork needed to construct SSBFT algorithms for distributed systems, such as Blockchains and the Cloud.

When deploying an asynchronous solution, such as a consensus algorithm, in real-world systems, it is crucial to ensure the solution's correctness remains independent of any timing bounds, which are assumed to be unknown at the time in which the solution is designed and developed. However, given a specific real-world system, which has bounded computation and communication delays, the consensus algorithm can be expected to terminate and deliver results to all non-faulty nodes within a known bounded time, which we refer to as $logSize$ (Assumption <ref>). This time corresponds to the duration in which it is required to log consensus objects until their results reach all non-faulty nodes. It is important to note that synchrony assumptions are imperative for any deterministic solution to the studied problem since it is equivalent to consensus. This is because the problem entails deciding both the termination of an asynchronous consensus object and whether the agreed-upon value was received by all non-faulty nodes.

As a potential avenue for future research, one could explore deterministic recycling mechanisms, say by utilizing the Dolev and Welch approach to SSBFT clock synchronization [23], to design an SSBFT SIG-index. However, their solution has exponential stabilization time, making it unfeasible in practice.

§.§ Acknowledgments

We express our gratitude to anonymous reviewers for their valuable comments.
The work of E. M. Schiller was partially supported by VINNOVA, the Swedish Governmental Agency
for Innovation Systems through the CyReV project under Grant 2019-03071.

[1]
I. Abraham and D. Dolev.
Byzantine agreement with optimal early stopping, optimal resilience
and polynomial complexity.
In STOC, pages 605–614. ACM, 2015.

[2]
Y. Afek, S. Kutten, and M. Yung.
Memory-efficient self stabilizing protocols for general networks.
In WDAG, volume 486 of Lecture Notes in Computer
Science, pages 15–28. Springer, 1990.

[3]
N. Alon, H. Attiya, S. Dolev, S. Dubois, M. Potop-Butucaru, and S. Tixeuil.
Practically stabilizing SWMR atomic memory in message-passing
J. Comput. Syst. Sci., 81(4):692–701, 2015.

[4]
K. Altisen, S. Devismes, S. Dubois, and F. Petit.
Introduction to Distributed Self-Stabilizing Algorithms.
Synthesis Lectures on Distributed Computing Theory. Morgan &
Claypool Publishers, 2019.

[5]
B. Awerbuch, B. Patt-Shamir, G. Varghese, and S. Dolev.
Self-stabilization by local checking and global reset (extended
In WDAG, volume 857 of Lecture Notes in Computer
Science, pages 326–339. Springer, 1994.

[6]
M. Ben-Or.
Another advantage of free choice: Completely asynchronous agreement
protocols (extended abstract).
In Proceedings of the Second Annual ACM SIGACT-SIGOPS
Symposium on Principles of Distributed Computing, pages 27–30, 1983.

[7]
M. Ben-Or, D. Dolev, and E. N. Hoch.
Fast self-stabilizing Byzantine tolerant digital clock
In Proceedings of the Twenty-Seventh Annual ACM Symposium on
Principles of Distributed Computing, PODC 2008, Toronto, Canada, August
18-21, 2008, pages 385–394. ACM, 2008.

[8]
A. Binun, T. Coupaye, S. Dolev, M. Kassi-Lahlou, M. Lacoste, A. Palesandro,
R. Yagel, and L. Yankulin.
Self-stabilizing Byzantine-tolerant distributed replicated state
In Stabilization, Safety, and Security of Distributed Systems -
18th International Symposium, SSS, pages 36–53, 2016.

[9]
S. Bonomi, S. Dolev, M. Potop-Butucaru, and M. Raynal.
Stabilizing server-based storage in Byzantine asynchronous
message-passing systems: Extended abstract.
In Proceedings of the 2015 ACM Symposium on Principles of
Distributed Computing, PODC, pages 471–479, 2015.

[10]
S. Bonomi, M. Potop-Butucaru, and S. Tixeuil.
Stabilizing Byzantine-fault tolerant storage.
In 2015 IEEE International Parallel and Distributed Processing
Symposium, IPDPS, pages 894–903, 2015.

[11]
S. Bonomi, A. D. Pozzo, M. Potop-Butucaru, and S. Tixeuil.
Brief announcement: Optimal self-stabilizing mobile
Byzantine-tolerant regular register with bounded timestamps.
In Stabilization, Safety, and Security of Distributed Systems -
20th International Symposium, SSS, pages 398–403, 2018.

[12]
S. Bonomi, A. D. Pozzo, M. Potop-Butucaru, and S. Tixeuil.
Approximate agreement under mobile Byzantine faults.
Theor. Comput. Sci., 758:17–29, 2019.

[13]
G. Bracha and S. Toueg.
Resilient consensus protocols.
In PODC, pages 12–26. ACM, 1983.

[14]
E. W. Dijkstra.
Self-stabilizing systems in spite of distributed control.
Commun. ACM, 17(11):643–644, 1974.

[15]
S. Dolev.
MIT Press, 2000.

[16]
S. Dolev, C. Georgiou, I. Marcoullis, and E. M. Schiller.
Practically-self-stabilizing virtual synchrony.
J. Comput. Syst. Sci., 96:50–73, 2018.

[17]
S. Dolev, C. Georgiou, I. Marcoullis, and E. M. Schiller.
Self-stabilizing Byzantine tolerant replicated state machine based
on failure detectors.
In Cyber Security Cryptography and Machine Learning - Second
International Symposium, CSCML, pages 84–100, 2018.

[18]
S. Dolev, O. Liba, and E. M. Schiller.
Self-stabilizing Byzantine resilient topology discovery and message
In Networked Systems - First International Conference, NETYS,
pages 42–57, 2013.

[19]
S. Dolev, T. Petig, and E. M. Schiller.
Brief announcement: Robust and private distributed shared atomic
memory in message passing networks.
In Proceedings of the 2015 ACM Symposium on Principles of
Distributed Computing, PODC, pages 311–313, 2015.

[20]
S. Dolev, T. Petig, and E. M. Schiller.
Self-stabilizing and private distributed shared atomic memory in
seldomly fair message passing networks.
CoRR, abs/1806.03498, 2018.
Also to appear in Springer's Algorithmica.

[21]
S. Dolev, T. Petig, and E. M. Schiller.
Self-stabilizing and private distributed shared atomic memory in
seldomly fair message passing networks.
Algorithmica, 85(1):216–276, 2023.

[22]
S. Dolev and J. L. Welch.
Self-stabilizing clock synchronization in the presence of Byzantine
faults (abstract).
In Proceedings of the Fourteenth Annual ACM Symposium on
Principles of Distributed Computing, page 256, 1995.

[23]
S. Dolev and J. L. Welch.
Self-stabilizing clock synchronization in the presence of Byzantine
J. ACM, 51(5):780–799, 2004.

[24]
S. Dubois, M. Potop-Butucaru, M. Nesterenko, and S. Tixeuil.
Self-stabilizing Byzantine asynchronous unison.
J. Parallel Distributed Comput., 72(7):917–923, 2012.

[25]
R. Duvignau, M. Raynal, and E. M. Schiller.
Self-stabilizing Byzantine fault-tolerant repeated reliable
In SSS, volume 13751 of Lecture Notes in Computer
Science, pages 206–221. Springer, 2022.

[26]
M. Feldmann, T. Götte, and C. Scheideler.
A loosely self-stabilizing protocol for randomized congestion control
with logarithmic memory.
In Stabilization, Safety, and Security of Distributed Systems -
21st International Symposium, SSS, volume 11914 of Lecture Notes in
Computer Science, pages 149–164. Springer, 2019.

[27]
M. J. Fischer and N. A. Lynch.
A lower bound for the time to assure interactive consistency.
Inf. Process. Lett., 14(4):183–186, 1982.

[28]
M. J. Fischer, N. A. Lynch, and M. Paterson.
Impossibility of distributed consensus with one faulty process.
J. ACM, 32(2):374–382, 1985.

[29]
C. Georgiou, R. Gustafsson, A. Lindhé, and E. M. Schiller.
Self-stabilization overhead: A case study on coded atomic storage.
In NETYS, volume 11704 of Lecture Notes in Computer
Science, pages 131–147. Springer, 2019.

[30]
C. Georgiou, O. Lundström, and E. M. Schiller.
Self-stabilizing snapshot objects for asynchronous failure-prone
networked systems.
In P. Robinson and F. Ellen, editors, Proceedings of the 2019
ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto,
ON, Canada, July 29 - August 2, 2019., pages 209–211. ACM, 2019.

[31]
C. Georgiou, O. Lundström, and E. M. Schiller.
Self-stabilizing snapshot objects for asynchronous failure-prone
networked systems.
In Networked Systems - 7th International Conference, NETYS
2019, Marrakech, Morocco, June 19-21, 2019, Revised Selected Papers, pages
113–130, 2019.

[32]
C. Georgiou, I. Marcoullis, M. Raynal, and E. M. Schiller.
Loosely-self-stabilizing Byzantine-tolerant binary consensus for
signature-free message-passing systems.
In NETYS, volume 12754 of Lecture Notes in Computer
Science, pages 36–53. Springer, 2021.

[33]
C. Georgiou, M. Raynal, and E. M. Schiller.
Self-stabilizing byzantine-tolerant recycling.
To appear in SSS, 2023.

[34]
T. Izumi.
On space and time complexity of loosely-stabilizing leader election.
In C. Scheideler, editor, Structural Information and
Communication Complexity - 22nd International Colloquium, SIROCCO, volume
9439 of Lecture Notes in Computer Science, pages 299–312. Springer,

[35]
S. Katz and K. J. Perry.
Self-stabilizing extensions for message-passing systems.
In PODC, pages 91–101. ACM, 1990.

[36]
D. R. Kowalski and A. Mostéfaoui.
Synchronous Byzantine agreement with nearly a cubic number of
communication bits: synchronous byzantine agreement with nearly a cubic
number of communication bits.
In PODC, pages 84–91. ACM, 2013.

[37]
L. Lamport, R. E. Shostak, and M. C. Pease.
The Byzantine generals problem.
ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982.

[38]
C. Lenzen and J. Rybicki.
Self-stabilising Byzantine clock synchronisation is almost as easy
as consensus.
J. ACM, 66(5):32:1–32:56, 2019.

[39]
O. Lundström, M. Raynal, and E. M. Schiller.
Self-stabilizing set-constrained delivery broadcast (extended
In 40th IEEE International Conference on Distributed Computing
Systems, ICDCS, pages 617–627, 2020.

[40]
O. Lundström, M. Raynal, and E. M. Schiller.
Self-stabilizing uniform reliable broadcast.
In Networked Systems - 8th International Conference, NETYS,
pages 296–313, 2020.

[41]
O. Lundström, M. Raynal, and E. M. Schiller.
Self-stabilizing indulgent zero-degrading binary consensus.
In ICDCN '21: International Conference on Distributed
Computing and Networking, pages 106–115, 2021.

[42]
O. Lundström, M. Raynal, and E. M. Schiller.
Self-stabilizing multivalued consensus in asynchronous crash-prone
In EDCC, pages 111–118. IEEE, 2021.

[43]
O. Lundström, M. Raynal, and E. M. Schiller.
Self-stabilizing multivalued consensus in asynchronous crash-prone
CoRR, abs/2104.03129, 2021.

[44]
O. Lundström, M. Raynal, and E. M. Schiller.
Brief announcement: Self-stabilizing total-order broadcast.
In SSS, volume 13751 of Lecture Notes in Computer
Science, pages 358–363. Springer, 2022.

[45]
A. Maurer.
Self-stabilizing Byzantine-resilient communication in dynamic
In OPODIS, volume 184 of LIPIcs, pages 27:1–27:11.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

[46]
A. Mostéfaoui, H. Moumen, and M. Raynal.
Signature-free asynchronous Byzantine consensus with t
n/3, O(n\({}^{\mbox{2}}\)) messages.
In ACM Symposium on Principles of Distributed Computing,
PODC, pages 2–9, 2014.

[47]
T. Oliveira, R. Mendes, and A. N. Bessani.
Exploring key-value stores in multi-writer Byzantine-resilient
register emulations.
In OPODIS, volume 70 of LIPIcs, pages 30:1–30:17.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.

[48]
M. C. Pease, R. E. Shostak, and L. Lamport.
Reaching agreement in the presence of faults.
J. ACM, 27(2):228–234, 1980.

[49]
D. Plainfossé and M. Shapiro.
A survey of distributed garbage collection techniques.
In IWMM, volume 986 of Lecture Notes in Computer
Science, pages 211–249. Springer, 1995.

[50]
M. O. Rabin.
Randomized Byzantine generals.
In 24th Annual Symposium on Foundations of Computer Science,
pages 403–409, 1983.

[51]
M. Raynal.
Fault-Tolerant Message-Passing Distributed Systems - An
Algorithmic Approach.
Springer, 2018.

[52]
I. Salem and E. M. Schiller.
Practically-self-stabilizing vector clocks in the absence of
execution fairness.
In Networked Systems - 6th International Conference, NETYS,
pages 318–333, 2018.

[53]
Y. Sudo, J. Nakamura, Y. Yamauchi, F. Ooshita, H. Kakugawa, and T. Masuzawa.
Loosely-stabilizing leader election in a population protocol model.
Theor. Comput. Sci., 444:100–112, 2012.

[54]
Y. Sudo, F. Ooshita, H. Kakugawa, and T. Masuzawa.
Loosely stabilizing leader election on arbitrary graphs in population
protocols without identifiers or random numbers.
IEICE Trans. Inf. Syst., 103-D(3):489–499, 2020.

[55]
Y. Sudo, F. Ooshita, H. Kakugawa, T. Masuzawa, A. K. Datta, and L. L. Larmore.
Loosely-stabilizing leader election for arbitrary graphs in
population protocol model.
IEEE Trans. Parallel Distributed Syst., 30(6):1359–1373,

[56]
Y. Sudo, F. Ooshita, H. Kakugawa, T. Masuzawa, A. K. Datta, and L. L. Larmore.
Loosely-stabilizing leader election with polylogarithmic convergence
Theor. Comput. Sci., 806:617–631, 2020.

[57]
S. Toueg.
Randomized Byzantine agreements.
In T. Kameda, J. Misra, J. G. Peters, and N. Santoro, editors, Proceedings of the Third Annual ACM Symposium on Principles of Distributed
Computing, pages 163–178. ACM, 1984.

[58]
L. Veiga and P. Ferreira.
Asynchronous complete distributed garbage collection.
In IPDPS. IEEE Computer Society, 2005.

BC Byzantine-tolerant Consensus;
BDH Ben-Or, Dolev, and Hoch [7];
BFT   non-self-stabilizing Byzantine fault-tolerant solutions;
COR Consensus Object Recycling (Definition <ref>);
DPS Dolev, Petig, and Schiller [21];
MMR Mostéfaoui, Moumen, and Raynal [46];
RCCs  random common coins;
SSBFT    self-stabilizing Byzantine fault-tolerant;
$\mathbf{\kappa\mathit{-}SGC}$  $\kappa$-state global clock.

SUBMISSION: 6231
TITLE: Self-stabilizing Byzantine-tolerant Recycling

———————– REVIEW 1 ———————
SUBMISSION: 6231
TITLE: Self-stabilizing Byzantine-tolerant Recycling
AUTHORS: Chryssis Georgiou, Michel Raynal and Elad Michael Schiller

———– Overall evaluation ———–
SCORE: -1 (weak reject)
—– TEXT:
This paper presents a protocol to recycle Consensus objects in a synchronous self-stabilizing Byzantine-prone distributed systems. The motivation relies on the fact that the memory of each process is bounded and that distributed applications rarely execute single consensus. The proposed algorithm is randomized and relies on random common coins. It tolerate up to t<n/3 Byzantine processes and its expected stabilization is in O(t) rounds.

The problem is of interest for the SSS community. Nevertheless, I am not in favor of acceptance of this paper. Indeed, the paper is very hard to follow. I am not sure to understood the main specification of COR, I find the presentation very drafty, I was not able to clearly understand what is new, what is already existing and what the paper really brings. Subalgorithms of Figure 1 have no specification, so it is difficult to grasp what subproblems they solve. I do not understand the motivation to choose an hybrid system that greatly improve the complexity of the paper without bringing any particular insight in my opinion. Technically, the paper does not seem to bring new approaches or new technical tools.

For these reasons, I recommend the authors to carefully rework the presentation of their paper and to try to simplify the context. In particular, I think that specifications of considered problems has to be clarified and motivated.

———————– REVIEW 2 ———————
SUBMISSION: 6231
TITLE: Self-stabilizing Byzantine-tolerant Recycling
AUTHORS: Chryssis Georgiou, Michel Raynal and Elad Michael Schiller

———– Overall evaluation ———–
SCORE: 1 (weak accept)
—– TEXT:
The paper studies a self-stabilizing recycling of consensus objects, in which successive instances of Byzantine consensus must be realized. Its claimed originality is a more robust synchronous solution than the previous solutions to the problem. The solution is randomized.

The proposed algorithm is a composition of existing building blocks with an original block. It gives a solid background for an implementation. The blocks deal with a recycling mechanism, clock synchronization and an original multi-valued consensus. The solution recovers after the last transient fault within expected O(K) rounds, where K depends on the specific synchrony assumptions and on the number of faulty processes.

Comments to authors:
The model is informal in many aspects. Thus, instead of using the constrained space for precise definitions, the paper describes a context that could be interesting in a practical approach, but which is not relevant from the purely algorithmic point of view. As a consequence, the complete proofs and the original algorithm are not presented in the paper (but in the appendix) and thus not destined to appear in the published paper, which diminishes considerably its pertinence.
In particular, the Byzantine fault model is not enough precise and confusing. It considers an adversary able to ”capture” some processes, but at the same time it is said that ”the adversary completely controls the messages that the algorithm sends”.
It is also said informally that a captured process cannot impersonate a correct one. But, in the state of the art part, the possible corruption of private keys is mentioned, without more explanations, and that seems contradictory.

Technically, the notion used in the paper is pseudo-stabilization, since the definition of self-stabilization uses legitimate configurations. Pseudo-stabilization is strictly weaker than self-stabilization. This is not what is used in the seminal paper of Dijkstra. The authors should explain why they made this choice, since from a practical point of view self-stabilization is easier to be observed by an external (correct) observer. Also the claims: “The occurrence of an arbitrary transient fault is rare. Thus, our model assumes that the last arbitrary transient fault occurs before the system execution starts [10]” sound strange, like if not a pure self-stabilization is considered, because a self-stabilizing algorithm recovers after any number of transient faults and which can arrive at any  moment in the execution. This is confusing.
The model indeed seems to assume that there is a single transient failure at the start of an execution. That comes to consider that the initial configuration is arbitrary. Then, when the second instance of recycling starts, no failure ever happens. Thus in fact the problem seems only to stabilize the first iteration. The authors should make this point clear.

The state of the art is difficult to read, due to an accumulation of acronyms (18 in the last 10 lines).

More generally, an informal and intuitive explanation of how the solution works is lacking and should be added. For instance, Figure 1 is interesting, but not sufficiently commented.

The paper should also justify, component by component, the necessity of the assumptions it makes (synchrony, randomization, both).

The paper presents a combination of building blocks for obtaining an original stabilizing algorithm. The construction is interesting in itself and is a good start for an implementation. However the paper in its actual state has to be revised. I would advise the authors to drop some generalities and to focus on the algorithmic part, to include the missing algorithm, the more complete proofs and an informal description of each of the modules and of their interactions.

———————– REVIEW 3 ———————
SUBMISSION: 6231
TITLE: Self-stabilizing Byzantine-tolerant Recycling
AUTHORS: Chryssis Georgiou, Michel Raynal and Elad Michael Schiller

———– Overall evaluation ———–
SCORE: 2 (accept)
—– TEXT:
This paper is about the consensus problem, where all distributed processes should agree on a single value. The authors present a technique for reusing consensus objects, i.e., it enables an unbounded number of repeated invocations on a bounded number of consensus objects.

The presented technique handles the situation where some of the processes are byzantine (however, they cannot impersonate non-faulty processes). Moreover, the recycling mechanism is self-stabilizing.

In particular, the authors take an existing self-stabilizing fault-tolerant consensus algorithm, and give a recyclable variation of it. In their solution, they use randomness and some synchrony assumptions.

This work considers an interesting problem in the field of distributed systems, and the suggested solution seems practical.

Minor comments:
- Page 5, last paragraph: "soultion" –> solution

- Page 10, 1st paragraph: It seems like an explanation about Algorithm 2, but it refers to some parts of Algorithm 1 (line 5, line 6). I suggest to give more details in this explanation.

- Page 14, Proof of Theorem 3, 1st paragraph: "hold are implied by" - Rephrase.

———————– REVIEW 4 ———————
SUBMISSION: 6231
TITLE: Self-stabilizing Byzantine-tolerant Recycling
AUTHORS: Chryssis Georgiou, Michel Raynal and Elad Michael Schiller

———– Overall evaluation ———–
SCORE: 0 (borderline paper)
—– TEXT:
In this paper, the authors study the problem of recycling asynchronous consensus objects when they completed their task and delivered their decision to non-faulty processes in a distributed system. The algorithm consists of (i) a client algorithm that uses consensus objects and the recycling mechanism for the objects and (ii) a recycling mechanism that recycles used consensus objects.

The client algorithm reports the delivery of the result of the consensus using the return value of the interface function wasDelivered(). Also, the algorithm recycles the objects when the recycle mechanism invokes the function recycle(). Using the functions, the consensus object recycling (COR) problem is defined roughly as follows.

(1) COR-client-eventual-agreement: If a non-faulty process p_i set to wasDelivered_i() = True, then all non-faulty processes report delivery eventually.
(2)COR-servie-validity-1: If a non-faulty process p_j invokes recycle_j(), then at least one non-faulty process p_i reported delivery.
(3)COR-servie-validity-2: If all non-faulty processes report delivery, then at least one non-faulty process p_j eventually invokes recycle_j().
(4)COR-servie-agreement: If a non-faulty process invokes recycle(), then all non-faulty processes p_i invokes recycle_i().

For the client algorithm and recycle mechanism, the paper adopts the hybrid synchronous and asynchronous approaches. In the client algorithm, the system is assumed to be asynchronous, and for the recycling mechanism, the synchronous system is assumed.  In more detail, for the client algorithm, the model BAMP_n,t[FC, t < n/3, RCCs] is used. The model assumes asynchronous and fair communication of message passing, the number of faulty processes is at most n/3, and random common coins. For the recycling mechanism, the model BSMP_n,t[¥kappa-SGC, t<n/3, RCCs] is assumed. The model assumes ¥kappa-state global clock, reliable communication, and an RCC service.

As the contribution, the authors propose a self-stabilizing Byzantine fault-tolerant recycling mechanism, which recovers after the occurrence of the last transient fault within expected O(¥kappa) synchronous rounds, where ¥kappa = O(t) (the upper bound on the number of Byzantine processes).

For the recycling mechanism, the paper proposes three components. I can find detailed descriptions of the first two components, namely the main algorithm for the recycling mechanism and the second algorithm called SSBFT SIG-index in the model. However, for the third algorithm, I only find some abstract descriptions. Due to the lack of detailed descriptions of the algorithm and its guarantees, it is hard for me to understand how the whole algorithm works.  Also, since the third algorithm (SSBFT multivalued consensus) is a building block of the algorithm SIG-index, the correctness proof of the second algorithm should use some guarantee of the third algorithm in the correctness proof. Instead of detailed proofs, adding a little more explanation of the SSBFT multivalued consensus algorithm in the extended abstract might help the reader's understanding.

———————– REVIEW 5 ———————
SUBMISSION: 6231
TITLE: Self-stabilizing Byzantine-tolerant Recycling
AUTHORS: Chryssis Georgiou, Michel Raynal and Elad Michael Schiller

———– Overall evaluation ———–
SCORE: -1 (weak reject)
—– TEXT:
These are the comments from the track chairs. We found this paper to be very interesting. However, we also noted that some parts lack formality and clarity, preventing us from verifying the correctness of your claims. Therefore, we suggest you resubmit the revised version of this paper for the second round of SSS 2023. We hope the reviewers' comments will help you improve the paper and that you will consider our recommendation.

———————————-  2nd round of revision ————-

SUBMISSION: 4610
TITLE: Self-stabilizing Byzantine-tolerant Recycling

———————– REVIEW 1 ———————
SUBMISSION: 4610
TITLE: Self-stabilizing Byzantine-tolerant Recycling
AUTHORS: Chryssis Georgiou, Michel Raynal and Elad Michael Schiller

———– Overall evaluation ———–
SCORE: 1 (weak accept)
—– TEXT:
The paper studies the recycling of consensus objects, in which successive instances of consensus must be realized. Its originality is a more robust synchronous solution than the previous solutions to the problem, since the self-stabilization property is added. The solution is synchronous and randomized.
The proposed solution is a composition of existing building blocks with an original block. It gives a solid background for an implementation. The blocks concern a recycling mechanism, a clock synchronization and an original multi-valued consensus. The solution recovers after a transient fault within expected O(K) rounds, where K depends on the specific synchrony assumptions and on the number of faulty processes.
I had many criticisms on the original version of the paper, but the authors made a considerable effort to answer them, point by point.
The paper still does not establish the necessity of the assumptions made, it just indicates now their usefulness. Also, references to impossibility results would be a nice addition.
However the revised version of the paper is much better structured. The problem is clearly defined and the chain of the modules forming the solution is correctly described.
In my opinion, the actual paper fulfills expected requirements of clarity and readability and its publication in the proceedings of SSS can be considered.

p. 13: stabilizing time instead of stabilizes time

———————– REVIEW 2 ———————
SUBMISSION: 4610
TITLE: Self-stabilizing Byzantine-tolerant Recycling
AUTHORS: Chryssis Georgiou, Michel Raynal and Elad Michael Schiller

———– Overall evaluation ———–
SCORE: 0 (borderline paper)
—– TEXT:
This paper is about the consensus problem, where all distributed processes should agree on a single value. The authors present a technique for reusing consensus objects, i.e., it enables an unbounded number of repeated invocations on a bounded number of consensus objects.

The presented technique handles the situation where some of the processes are byzantine (however, they cannot impersonate non-faulty processes). Moreover, the recycling mechanism is self-stabilizing.

In particular, the authors take an existing self-stabilizing fault-tolerant consensus algorithm, and give a recyclable variation of it. In their solutions, they use randomness and some synchrony assumptions.

This work considers an interesting problem in the field of distributed systems, and the suggested solution seems practical.
In the revised version the authors added some important details and explanations that make it easier to follow.
However, the proofs are not formal enough so I could not completely verify the correctness of the suggested solution.

———————– REVIEW 3 ———————
SUBMISSION: 4610
TITLE: Self-stabilizing Byzantine-tolerant Recycling
AUTHORS: Chryssis Georgiou, Michel Raynal and Elad Michael Schiller

———– Overall evaluation ———–
SCORE: 1 (weak accept)
—– TEXT:
The contribution of this paper is to take an existing asynchronous Byzantine-tolerant consensus algorithm and add a number of mechanisms that allow processes to recycle the memory used by the consensus algorithm's state once the results have been received by all of the correct nodes in the system. It does this utilizing a new algorithm referred to as "simultaneous increment-or-get index" that stands between the consensus algorithm and the recycling mechanism. All of this is done in a loosely self-stabilizing setting ("loosely" because the underlying consensus algorithm only self-stabilizes with high probability) in which arbitrary transient faults can be recovered from.

This paper requires a very high degree of familiarity with its subject matter. The underlying consensus algorithm (referred to as GMRS) that the recycling mechanism is built on is never explained in full; only partial pseudocode is presented for it, with omitted segments intermixed with this paper's new additions. This reviewer mostly has experience with non-self-stabilizing, semi-synchronous consensus algorithms, but it is hard to see how even a specialist in this field could understand this paper as a standalone work. The explanations of even simple relevant concepts like random common coins are strictly formal and not intuitive. Also, the "loosely" self-stabilizing nature of the original algorithm is never acknowledged by this paper; the term "self-stabilizing" is presented without qualifiers, which seems potentially misleading.

EMS: Clarified.

However, this paper found a meaningful problem regarding consensus in its chosen setting and solved it using an in-depth spelled-out algorithm with proofs of its correctness. This seems to me to be a worthwhile contribution to the field.

———————– REVIEW 4 ———————
SUBMISSION: 4610
TITLE: Self-stabilizing Byzantine-tolerant Recycling
AUTHORS: Chryssis Georgiou, Michel Raynal and Elad Michael Schiller

———– Overall evaluation ———–
SCORE: 1 (weak accept)
—– TEXT:
In this paper, the authors examine the problem of recycling asynchronous consensus objects after they have reached a consensus and delivered their decision to non-faulty processes. The proposed algorithm comprises two main components:(i) A client algorithm that utilizes consensus objects and the recycling mechanism for these objects. (ii) A recycling mechanism responsible for efficiently reusing consensus objects that have been utilized before.

The proposed recycling mechanism consists of three sub-algorithms as follows. (1)The main part that handles if an object can be recycled. (2) The SIG-index that controls the index of the array of consensus objects globally. (3) SSBFT synchronous multivalued consensus that monitors the global completions of each execution of the client consensus algorithm. Especially the algorithm SIG-index is the original and key algorithm to achieve the recycling of asynchronous consensus objects.

The presentation of the paper has shown improvement compared to the previously submitted version. However, there is still an area of concern regarding the clarity of Assumption 1 on page 9. My understanding is that Assumption 1 states that if at least t + 1 correct nodes have wasDelivered() = True at synchronous round r, then all n - t correct nodes will also have wasDelivered() = True at synchronous round r + logSize. Regarding the model assumed for Algorithm 1 (the client algorithm), it may not be entirely asynchronous since in a fully asynchronous setting, the delay range of any message is unbounded. However, it is possible that the assumption is practical and reasonable. Nonetheless, to ensure a clear understanding of the model for Algorithm 1, some clarification of this assumption is necessary.

EMS: Tried to clarify that the mechanism constraints all synchrony assumptions.

Minor comments:

- Some terminologies such as P and Correct are used before explaining their definitions.

EMS: Fixed.

-In Assumption 1 on page 9, A bounded time result retrial -> A bounded time result retrieval?

EMS: Fixed.

-Is there any difference between the symbols t and f? For example, in the last sentence of page 12, is it more appropriate to use n - t instead of n - f?

EMS: Fixed.