Self-stabilizing Total-order Broadcast

Oskar Lundström [Chalmers Univ. Tech., Sweden ] Michel Raynal [Institut Universitaire de France IRISA, France ]  Elad Michael Schiller ^∗

The problem of total-order (uniform reliable) broadcast is fundamental in fault-tolerant distributed computing since it abstracts a broad set of problems requiring processes to uniformly deliver messages in the same order in which they were sent. Existing solutions (that tolerate process failures) reduce the total-order broadcast problem to the one of multivalued consensus.

Our study aims at the design of an even more reliable solution. We do so through the lenses of self-stabilization—a very strong notion of fault-tolerance. In addition to node and communication failures, self-stabilizing algorithms can recover after the occurrence of arbitrary transient faults; these faults represent any violation of the assumptions according to which the system was designed to operate (as long as the algorithm code stays intact).

This work proposes the first (to the best of our knowledge) self-stabilizing algorithm for total-order (uniform reliable) broadcast for asynchronous message-passing systems prone to process failures and transient faults. As we show, the proposed solution facilitates the elegant construction of self-stabilizing state-machine replication using bounded memory.

Fault-tolerant distributed applications span many domains in the area of banking, transport, tourism, production, and commerce, to name a few. The implementations of these applications use message-passing systems and require fault-tolerance. The task of designing and verifying these systems is known to be hard, because the joint presence of failures and asynchrony creates uncertainties about the application state (from the process's point of view).
Our focal application is the distributed emulation of finite-state machines. For the sake of consistency maintenance, all emulating processes need to apply identical sequences of state transitions. Existing fault-tolerant solutions divide the problem into two: (i) propagation of user input to all emulating processes, and (ii) agreeing on a uniform order according to which messages are delivered. Uniform reliable broadcast [31, 23] can solve Problem (i). Consensus can facilitate the solution of Problem (ii).
The challenge of combining the solutions to problems (i) and (ii) is called total-order uniform reliable broadcast [31], TO-URB from now on. TO-URB lets each emulating process execute identical sequences of state transitions.
There are fault-tolerance TO-URB implementations.
This work aims at a more fault-tolerant TO-URB than the existing ones.

Problem definition

We study the TO-URB problem (Definition <ref>). It uses the operations TO-broadcast (for sending application messages) and TO-deliver (for receiving them).

TO-URB requires the satisfaction of the following.

* TO-validity.   Suppose a process TO-delivers $m$. Message $m$ was previously TO-broadcast by its sender, which is denoted by $m.sender$.

* TO-integrity.   A process TO-delivers $m$ at most once.

* TO-delivery.   Suppose a process TO-delivers $m$ and later TO-delivers $m'$. No process TO-delivers $m'$ before $m$.

* TO-completion-1.   Suppose a non-faulty process TO-broadcasts $m$. All non-faulty processes TO-delivers $m$.

* TO-completion-2.   Suppose a process TO-delivers $m$. All non-faulty processes TO-deliver $m$.

The context of the studied problems, ,which appear in bold font

The studied problems and their architectural context

It is known that TO-broadcast's implementation requires the computability power of consensus, but FIFO-URB does not, see Raynal [31].
Thus, our reference architecture ( <ref>) includes consensus (specified in Section <ref>) and a failure detector for eventually identifying faulty nodes (Section <ref>).

It also uses the communication abstraction of FIFO-URB, which is simpler than TO-URB since it does not require the computability power of consensus.
One can specify FIFO-URB (Section <ref>) by substituting the TO-delivery requirement of Definition <ref> with the following FIFO-delivery requirement.
Suppose a process FIFO-delivers $m$ and later FIFO-delivers $m'$, such that the sender of these messages is the same, $m.sender=m'.sender$. Then, no process FIFO-delivers $m'$ before $m$.

Fault model

We study an asynchronous message-passing system that has no guarantees on the communication delay and the algorithm cannot explicitly access the local clock.
We assume that this asynchronous system is prone to (detectable) fail-stop failures after which the failed node stops taking steps forever. We also consider communication failures, packet loss, duplication, and reordering, as long as fair communication holds, a message that is sent infinitely often is received infinitely often. We say that the faults above are foreseen since they are known at the design time.

In addition, we consider (arbitrary) transient faults, i.e., any temporary violation of assumptions according to which the system was designed to operate, e.g., state corruption due to soft errors.
We assume that these transient faults arbitrarily change the system state in unpredictable manners (while keeping the program code intact).
We say that these faults are unforeseen since their exact impact is unknown  at the design time.
In practice, a distributed system can have a non-trivial set of unknown faults that are hard to observe due to their transient nature, and thus, they cannot be individually specified as part of the fault model.

Design criteria

We aim at assuring that (if no unforeseen failures ever occur) the system, always, remains in a correct state.
the system satisfies the task requirements, under the assumption that it starts in a correct state and that its state changes only due to algorithmic steps and foreseen failures.
Arora and Gouda [3] refer to this as the Closure property.

The Closure property is unattainable in the presence of unforeseen failures.
To address such concerns, we consider a design criterion that requires the eventual system recovery (in the presence of all foreseen failures) after the occurrence of the last unforeseen and transient failure.
Arora and Gouda [3] refer to this requirement as the Convergence property.

In other words, our design criteria require the correctness proof to demonstrate Closure and Convergence.
In detail:

* Since unforeseen failures are rare, it is assumed that all transient faults occurred before the start of the system run.

* As mentioned, transient faults can corrupt the entire system state.
Thus, starting from an arbitrary state, Convergence is demonstrated in the presence of foreseen failures (while assuming that the last unforeseen failure has already occurred) without the need to show that the system satisfies the task requirements.

* Also, if unforeseen failures had never occurred (or after Convergence is done), the Closure property is demonstrated, i.e., the system satisfies the task requirements under the assumption that, starting from a legitimate state, the system state changes only due to the algorithmic steps and the foreseen failures.

Self-stabilizing systems

Dijkstra [12] requires self-stabilizing systems, which may start in any state, to return to correct behavior eventually.
within a finite period, Convergence is done, and Closure is never violated.

Asynchronous systems in the presence of stale information

Asynchronous systems (with bounded memory and channel capacity) can indefinitely hide stale information that transient faults introduce unexpectedly.
At any time, this corrupted data can cause the system to violate safety requirements, e.g., data consistency might be lost.

the adversarial scheduler can both (i) violate liveness guarantees, defer the task completion, and (ii) use a bounded number of opportunities to disrupt the system via a systematic exposure of hidden stale information.
The timing of these exposures can aim at prolonging (and, if possible, preventing) recovery from the last occurrence of a transient fault.

Due to such reasons, self-stabilizing systems often assume fair scheduling, i.e., nodes that have applicable steps (infinitely often) are allowed to take any step eventually.
This allows self-stabilizing systems to remove, within a bounded time, all stale information whenever they appear.
Convergence is done within a bounded time after which Closure always holds.

Asynchronous systems without any fairness assumptions

Without any kind of fairness assumptions, some elementary problems do not have a straightforward answer.
For example, a transient fault can cause a bounded counter to reach its maximum value, and yet the system might need to increment the counter an unbounded number of times after that overflow event.
There are cases in which there is no elegant way to maintain order among the different counter values, say, by wrapping around to zero upon counter overflow.
Thus, without any assumption on fair scheduling, a system that takes an extraordinary (or even an infinite) number of steps is bound to break any ordering constraint, because the scheduler can arbitrarily suspend node operations and defer message arrivals until such violations occur.
Having practical systems in mind, we consider this number of (sequential) steps to be no more than practically infinite [1, 15, 17, 32], say, $2^{64}$, since sequentially counting from zero to $2^{64}$ takes longer than the system's practical lifetime.
For example, assuming a message is sent or received every nanosecond, counting from zero to $2^{64}$ takes more than $580$ years.

Self-stabilizing systems in the presence of seldom fairness

Dolev, Petig, and Schiller [18] studied self-stabilizing systems that their scheduler is seldom fair. Specifically, after the occurrence of the last transient fault, fairness eventually holds, but only for the bounded period that is sufficient for enabling Convergence. Note that, in the absence of transient faults (or after Convergence is done), Closure is demonstrated without any fairness assumptions. Since transient faults are rare, our fairness assumption is seldom needed.

Related work

Non-self-stabilizing fault-tolerant TO-URB exists [31, 23], but we are interested in self-stabilizing solutions.
Seldom fairness was used for solving self-stabilizing FIFO-URB [25], binary and multivalued consensus [27, 28], atomic shared memory emulation and their wait-free snapshots [18, 21], as well as set-constraint broadcast [26], to name a few.
This earlier literature assumes seldom fairness and shows how to transform a non-self-stabilizing algorithm into a self-stabilizing one. This work uses some of these solutions [25, 27, 28] as external building blocks.
We note that making one set of assumptions in the absence of transient faults and then another set of assumptions in their presence is also used in the context of self-stabilizing Byzantine-fault tolerance [19, 20, 22]. Also, we are not the first to use self-stabilizing unreliable failure detectors [5, 11, 14, 15].

Dolev  [15] proposed a practically-stabilizing state machine replication via virtual synchrony. Note that practically-self-stabilizing systems cannot guarantee Convergence within a finite time whereas the proposed solution does. Also, the techniques in use, virtual synchrony and consensus, are not identical. We note that the same holds for all related practically-stabilizing systems [1, 7, 32].
Recently, Johnen, Arantes, and Sens [24] proposed a non-self-stabilizing yet bounded FIFO-URB and TO-URB. Our proposal is both bounded and self-stabilizing.

We note the existence of self-stabilizing systems that tolerate Byzantine behavior [8, 10, 6, 9, 30]. Such systems are outside the scope of our fault model since they often require other kinds of solutions. For example, Dolev  [16] used partial synchrony for self-stabilizing Byzantine fault tolerant emulation of state machine replication. Also, Georgiou  [22] provide a self-stabilizing Byzantine fault-tolerant solution for binary consensus using randomization. The proposed solution is deterministic and does not consider partial synchrony.

It is well-known that self-stabilizing systems cannot stop sending messages when the system's task has so-called  “terminated”, see <cit.> for details. This impossibility is, mistakenly, stated as “self-stabilizing system can never terminate”. However, the system's task can terminate but the system cannot stop sending messages. To avoid this confusion, we use the term completion rather than termination, which is the term that often appears in the literature.

Our contribution

We present a fundamental module for dependable distributed systems: a self-stabilizing fault-tolerant TO-URB for asynchronous message-passing systems.

Our solution assumes the availability of self-stabilizing algorithms for FIFO-URB and multivalued consensus. In the absence of transient faults, our asynchronous solution for self-stabilizing TO-URB completes within a constant number of communication rounds. After the occurrence of the last transient fault, the system recovers eventually (while assuming execution fairness among the non-faulty processes). The amount of memory used by the proposed algorithm as well as its communication costs are bounded.

To the best of our knowledge, we propose the first self-stabilizing TO-URB solution.

System Settings

We focus on asynchronous message-passing systems that have no guarantees on the communication delay. Also, the algorithm cannot explicitly access the  (local) clock (or  use timeout mechanisms). The system consists of a set, $\sP$, of $n$ fail-prone nodes  (or processes) with unique identifiers. Any pair of nodes $p_i,p_j \in \sP$ has access to a bidirectional communication channel, $\mathit{channel}_{j,i}$, that, at any time, has at most $\capacity \in \bZ^+$ messages on transit from $p_j$ to $p_i$ (this assumption is due to a known impossibility <cit.>).

When referring to an object $x$, say a variable or a function, that the state of $p_i \in \sP$ includes, and respectively, $p_i$ executes, we write $x_i$, and respectively, $x_i()$. $x$ serves as the object (variable or field) name and $x()$ is the function name. Also, when writing $x_i$, we refer to $p_i$'s storage of variable $x$ and $x_i()$ is $p_i$'s invocation of function $x()$.

In the interleaving model [13], the node's program is a sequence of (atomic) steps. Each step starts with an internal computation and finishes with a single communication operation, a message $send$ or $receive$. 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)$. We define an execution (or run) $R={c[0],a[0],c[1],a[1],\ldots}$ as an alternating sequence of system states $c[x]$ (configurations) and (atomic) steps $a[x]$, such that each $c[x+1]$, except for the starting one, $c[0]$, is obtained from $c[x]$ by $a[x]$'s execution. Note that we use the index, $x$, for the system states ($c[x]$) and steps ($a[x]$).

Task specifications

Returning the decided value

Definition <ref> considers the $\mathsf{propose}(v)$ operation. We refine the definition of $\mathsf{propose}(v)$ by specifying how the decided value is retrieved. This value is either returned by the $\mathsf{propose}()$ operation (as in the studied algorithm <cit.>) or via the returned value of the $\done()$ operation (as in the proposed solution). In the latter case, the symbol $\bot$ is returned as long as no value was decided. Also, the symbol $\blitza$ indicate a (transient) error that occurs only when the proposed algorithm exceed the bound on the number of iterations that it may take.

Invocation by algorithms from higher layers

We assume that the studied problem is invoked by algorithms that run at higher layers, such as total order broadcast, see  <ref>. This means that eventually there is an invocation, $I$, of the proposed algorithm that starts from a post-recycled system state. That is, immediately before invocation $I$, all local states of all correct nodes have the (predefined) initial values in all variables and the communication channels do not include messages related to invocation $I$.

For the sake of completeness, we illustrate briefly how the assumption above can be covered <cit.> in the studied hybrid asynchronous/synchronous architecture presented in  <ref>. Suppose that upon the periodic installation of the common seed, the system also initializes the array of binary consensus objects that are going to be used with this new installation. In other words, once all operations of a given common seed installation are done, a new installation occurs, which also initializes the array of binary consensus objects that are going to be used with the new common seed installation. Note that the efficient implementation of a mechanism that covers the above assumption is outside the scope of this work.

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{MVC}}$ denotes the task of binary consensus, which Section <ref> specifies, and $LE_{\text{MVC}}$ denotes the set of executions in which the system fulfills $T_{\text{MVC}}$'s requirements.

Due to the MVC-Completion requirement (Definition <ref>), $LE_{\text{MVC}}$ includes only finite executions. In Section <ref>, we consider executions $R=R_1\circ R_2 \circ,\ldots$ as infinite compositions of finite executions, $R_1, R_2,\ldots \in LE_{\text{MVC}}$, such that $R_x$ includes one invocation of task $T_\text{MVC}$, which always satisfies the liveness requirement, MVC-Completion, but, with an exponentially small probability, it does not necessarily satisfy the safety requirements, MVC-validity and MVC-agreement.

The fault model and self-stabilization

The legal executions ($LE$) set refers to all the executions in which the requirements of task $T$ hold. In this work, $T_{\text{TO-URB}}$ denotes the task of total-order uniform reliable broadcast, which Definition <ref> specifies, and the executions in the set $LE_{\text{TO-URB}}$ fulfill $T_{\text{TO-URB}}$'s requirements.

Benign failures

A failure occurrence is a step that the environment takes rather than the algorithm. When the failure occurrence cannot cause the system execution to lose legality, to leave $LE$, we refer to that failure as a benign one.

Communication failures and fairness

We focus on solutions that are oriented towards asynchronous message-passing systems and thus they are oblivious to the time at which the packets depart and arrive. We assume that any message can reside in a communication channel only for a finite period. Also, the communication channels are prone to packet failures, such as loss, duplication, and reordering.  However, if $p_i$ sends a message infinitely often to $p_j$, node $p_j$ receives that message infinitely often. This is called the fair communication assumption. The correctness proof uses Assumption <ref>.

Any sent message arrives or is lost within $\bigO(1)$ asynchronous cycles. Any URB message arrives within $\bigO(1)$ asynchronous cycles [29]. Each active multivalued consensus object decides within $\bigO(1)$ asynchronous cycles [27].

Fail-stop node failures

The system is prone to (detectable) fail-stop failures, in which nodes stop taking steps forever. We assume at most $t<n/2$ node may fail. Denote by $\Correct$ the set of indices of nodes that never fail. We assume the availability of a self-stabilizing failure detector, such as the one by Beauquier and Kekkonen-Moneta [4] or Blanchard  [5]. The interface to the failure detector offers the register $\mathit{trusted}$ that stores the local set of indexes of all nodes that are currently not suspected of being faulty.

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). The occurrence of a transient fault is rare. Thus, we assume that the last arbitrary transient fault occurs before the system execution starts [13]. Also, it leaves the system to start in an arbitrary state.

Dijkstra's self-stabilization

An algorithm is self-stabilizing with respect to $LE$, when every execution $R$ of the algorithm reaches within a finite period a suffix $R_{legal} \in LE$ that is legal [2, 13]. Namely, Dijkstra [12] requires $\forall R:\exists R': R=R' \circ R_{legal} \land R_{legal} \in LE \land |R'| \in \bZ^+$, where the operator $\circ$ denotes that $R=R' \circ R''$ is the concatenation of prefix $R'$ with suffix $R''$. This work assumes execution fairness only during the period, $R'$, of recovery from the occurrence of the last arbitrary transient fault.

The part of the proof that shows the existence of $R'$ is called the convergence, and the part that shows that $R_{legal} \in LE$ is called the closure proof. The main complexity measure of a self-stabilizing system is the length of the recovery period, $R'$, which is counted by the number of its asynchronous communication rounds during fair executions, as we define in Section <ref>.

Execution fairness

This work assumes execution fairness only during the period in which the system recovers from the occurrence of the last arbitrary transient fault. Given a step $a$, we say that $a$ is applicable to system state $c$ if there exists system state $c'$, such that $a$ leads to $c'$ from $c$. We say that a system execution is fair when every step of a correct node that is applicable infinitely often is executed infinitely often, and fair communication is kept.

Asynchronous communication cycles

Self-stabilizing algorithms cannot (terminate their execution and) stop sending messages <cit.>. Their code includes a do-forever loop. The main complexity measure of a self-stabilizing system is the length of the recovery period, $R'$, which is counted by the number of its asynchronous cycles during fair executions. The first asynchronous cycle $R'$ of execution $R=R'\circ R''$ is the shortest prefix of $R$ in which every correct node executes one complete iteration of the do forever loop and completes one round trip with every correct node that it sent messages to during that iteration. The second asynchronous cycle of $R$ is the first asynchronous cycle of $R''$ and so on.

External building blocks

The proposed solution uses a number of self-stabilizing modules ( <ref>). As mentioned, we assume the availability of a self-stabilizing failure detector (Section <ref>). We also assume the use of the following building blocks.

Global restart

In order to overcome the integer overflow problem (Section <ref>), use a global restart mechanism <cit.> for initializing the system state whenever an overflow occurs.
We assume that the maximum value in these integers is practically infinite, say, $2^{64}-1$.

Also, in the event of integer overflow, the system runs a global restart procedure after which it cannot overflow again before it has taken $2^{64}$ communication rounds.
We assume that no practical setup allows the system to take so many steps during its lifetime.

Multivalued consensus

This work uses the multivalued version of the Consensus problem (Definition <ref>). Existing self-stabilizing solutions include the one by Lundström, Raynal, and Schiller [28].  Note that there is another version of the problem in which this set includes exactly two values, and is referred to as binary consensus. Existing self-stabilizing solutions for the binary and multivalued consensus include the ones by Lundström, Raynal, and Schiller [25, 28].

Every process $p_i$ has to propose a value $v_i \in V$ via an invocation of the $\mathsf{propose}_i(v_i)$ operation, where $V$ is a finite set of values. We say that algorithm $\mathit{Alg}$ solves consensus if it satisfies:

* Validity. Suppose that $v$ is decided. At least one process invoked $\mathsf{propose}(v)$.

* Termination. All non-faulty processes decide.

* Agreement. No two processes decide on different values.

* Integrity. No process decides more than once.

Info. flow among Algorithm <ref>'s components. The proposed solution's operations, $\mathsf{toBroadcast}()$ and $\mathsf{toDeliver}()$, deal with the application messages and the solution itself coordinates its actions via protocol messages, $\SYNC()$ and $\SYNCack()$.

For a given consensus object $x$, we say that $x$ is active if $x\neq\bot$. In order to invoke (and activate) $x$, the algorithm calls $x.propose(v)$, where $v$ is the proposed value. As long as the consensus procedure is not completed, $x.\done()$ returns $\bot$. If an error, which is internal to $x$ occurs, $x.\done()$ returns $\blitza$. The algorithm can return $x$ to its initial state by assigning $\bot$ to $x$. Whenever $x.\done()$ returns a value that is neither $\bot$ nor $\blitza$ that value satisfies the requirements in Definition <ref>.

The proposed solution assumes the availability of a well-known extension to URB called FIFO-URB. We assume the availability of a self-stabilizing FIFO-URB, such as the one by Lundström, Raynal, and Schiller [25]. One can specify FIFO-URB by substituting the TO-delivery requirement of Definition <ref> with the FIFO-delivery requirement (Section <ref>).

We separate data dissemination and control. The former is carried by a FIFO-URB component and the latter by the proposed algorithm. To that end, we assume that the FIFO-URB module has interface functions that can aggregate protocol messages before their delivery.

Specifically, we assume that the interface function $\nonActive_i()$ returns $\true$ whenever there are no active URB transmissions sent by $p_i \in \sP$. Also, given $p_i \in \sP$, the functions $\minReady_i()$ and $\maxReady_i()$ return each a vector, $r_i[0,..,n\text{-}1]$, such that for any $p_j \in \sP$, the entry $r_i[j]$ holds the lowest, and respectively, highest FIFO-delivery message number that is ready-to-be-delivered. These message numbers are the unique sequence numbers that the senders attach to the URB messages.

The function $\bulkRead()$ allows bulk read of a set of FIFO-URB messages. Specifically, suppose $\bulkRead_i(r)$ returns immediately after system state $c$, where $\forall p_k \in \sP: r[k]\leq r_{\max}[k]$ and $r_{\max}=\maxReady_i()$. Its returned value is a deterministically ordered sequence, $sqnc_i$, that includes all the messages with message numbers $\mathit{mn}[k]$ from all senders $p_k \in \sP$, such that $r_{\min}[k] \leq \mathit{mn}[k] \leq r[k]\land r_{\min}=\minReady_i()$ in $c$.

Refinement of the system settings

Our self-stabilizing total-order message delivery implementation (Algorithm <ref>) provides the $\mathsf{toBroadcast}(m)$ operation (line <ref>). It uses a self-stabilizing URB with FIFO-order delivery, such as the one by Lundström, Raynal, and Schiller [29], to broadcast the protocol message,  $\mathsf{toURB}(msg)$. As before, the line numbers of Algorithm <ref> continues the ones of Algorithm REFalg:consensus.

The proposed solution assumes that the FIFO-URB module has interface functions that facilitate the aggregation of protocol messages before their delivery. For example, we assume that the interface function $\nonActive_i()$ returns $\true$ whenever there are no active URB transmissions sent by $p_i \in \sP$. Also, given $p_i \in \sP$, the functions $minReady_i()$ and $\maxReady_i()$ return each a vector, $r_i[0,..,n\text{-}1]$, such that for any $p_j \in \sP$, the entry $r_i[j]$ holds the lowest, and respectively, highest FIFO-delivery message number that is ready-to-be-delivered. These FIFO-delivery message numbers are the unique indices that the senders attach to the URB messages.

Also, the function $\bulkRead_i(r_{\max})$ returns immediately after system state $c$ a deterministically ordered sequence, $sqnc_i$, that includes all the messages between $r_{\min}$ and $r_{\max}$, such that $r_{\min}=\minReady_i()$ in $c$, as well as $r_{\max}$, is a vector that is entry-wise greater or equal to $r_{\min}$ and entry-wise smaller or equal $r=\maxReady_i()$ in $c$.

Algorithm <ref> assumes access to a self-stabilizing perfect failure detector, such as the one by Beauquier and Kekkonen-Moneta [4]. The local set, $\mathit{trusted}_i$, includes the indices of the nodes that $p_i$'s failure detector trusts. We follow Assumption <ref> for the sake of a simple presentation.

Any sent message arrives or is lost within $\bigO(1)$ asynchronous cycles. Any URB message arrives within $\bigO(1)$ asynchronous cycles [29]. Each active multivalued consensus object decides within $\bigO(1)$ asynchronous cycles [27].

For the sake of simple presentation of the correctness proof, when considering fair executions, we assume that any message that arrives in $R$ without being transmitted in $R$ does so within $\bigO(1)$ asynchronous rounds in $R$.

We define the $r$-th asynchronous (communication) round of an algorithm's execution $R=R'\circ A_r \circ R''$ as the shortest execution fragment, $A_r$, of $R$ in which every correct node $p_i \in \sP:i \in \Correct$ starts and ends its $r$-th iteration, $I_{i,r}$, of the do-forever loop. Moreover, let $m_{i,r,j,\mathit{ackReq}=\true}$ be a message that $p_i$ sends to $p_j$ during $I_{i,r}$, where the field $\mathit{ackReq}=\true$ implies that an acknowledgment reply is required. Let $a_{i,r,j,\true},a_{j,r,i,\false} \in R$ be the steps in which $m_{i,r,j,\true}$ and $m_{j,r,i,\false}$ arrive at $p_j$ and $p_i$, respectively. We require $A_r$ to also include, for every pair of correct nodes $p_i,p_j\in \sP:i,j \in \Correct$, the steps $a_{i,r,j,\true}$ and $a_{j,r,i,\false}$. We say that $A_r$ is complete if every correct node $p_i \in \sP:i \in \Correct$ starts its $r$-th iteration, $I_{i,r}$, at the first line of the do-forever loop. The latter definition is needed in the context of arbitrary starting system states.

Asynchronous communication rounds

It is well-known that self-stabilizing algorithms cannot terminate their execution and stop sending messages <cit.>. Moreover, their code includes a do-forever loop. The proposed algorithm uses $M$ communication round numbers. Let $r \in \{1,\ldots, M\}$ be a round number. We define the $r$-th asynchronous (communication) round of an algorithm's execution $R=R'\circ A_r \circ R''$ as the shortest execution fragment, $A_r$, of $R$ in which every correct node $p_i \in \sP:i \in \Correct$ starts and ends its $r$-th iteration, $I_{i,r}$, of the do-forever loop. Moreover, let $m_{i,r,j,\mathit{ackReq}=\true}$ be a message that $p_i$ sends to $p_j$ during $I_{i,r}$, where the field $\mathit{ackReq}=\true$ implies that an acknowledgment reply is required. Let $a_{i,r,j,\true},a_{j,r,i,\false} \in R$ be the steps in which $m_{i,r,j,\true}$ and $m_{j,r,i,\false}$ arrive at $p_j$ and $p_i$, respectively. We require $A_r$ to also include, for every pair of correct nodes $p_i,p_j\in \sP:i,j \in \Correct$, the steps $a_{i,r,j,\true}$ and $a_{j,r,i,\false}$. We say that $A_r$ is complete if every correct node $p_i \in \sP:i \in \Correct$ starts its $r$-th iteration, $I_{i,r}$, at the first line of the do-forever loop. The latter definition is needed in the context of arbitrary starting system states.

For the sake of simple presentation of the correctness proof, when considering fair executions, we assume that any message that arrives in $R$ without being transmitted in $R$ does so within $\bigO(1)$ asynchronous rounds in $R$.

Demonstrating recovery of consensus objects invoked by higher layer's algorithms

Note that the assumption made in Section <ref> simplifies the challenge of meeting the design criteria of self-stabilizing systems. Specifically, demonstrating recovery from transient faults, convergence proof, can be done by showing completion of all operations in the presence of transient faults. This is because the assumption made in Section <ref> implies that, as long as the completion requirement is always guaranteed, then eventually the system reaches a state in which only initialized consensus objects exist.

Self-stabilizing Bounded-memory TO-URB

Algorithm <ref> presents a self-stabilizing algorithm that uses bounded memory for implementing TO-URB.
It uses FIFO-URB broadcasts for disseminating the messages that were sent via TO-broadcast.
It defers the delivery of these FIFO broadcasts (in the buffers of FIFO-URBs) until sufficient information allows all nodes to decide on their total-order.
To that end, the URB objects report the message numbers, per sender, of messages that are ready-to-be-delivered, see Section <ref>. By collecting these reports from the nodes, the solution can decide, via a multivalued consensus, on the set of messages that all trusted nodes are ready to deliver.
Specifically, Algorithm <ref> agrees on the vector of message numbers, one number per sender, that all nodes are ready to deliver their respective messages (and all earlier messages).
Thus, the result of the agreement defines a common set of messages that all nodes are ready to deliver.
Since the message numbers in the set are known to all nodes, one can use a straightforward deterministic total-order for delivering these buffered messages in the same order.

Overview of Algorithm <ref>

<ref> presents an overview of Algorithm <ref>. Before going through the overview, we highlight its key parts.

* Upon the invocation of $\mathsf{toBroadcast}(m)$, disseminate the application message $m$ by using FIFO-URB for broadcasting $\mathsf{toURB}(m)$, which is the name of the URB messages that need to be totally ordered before delivery.

* Do forever

* Query all trusted nodes about the system's consensus round numbers and the vector, $\mathit{allReady}_i$, of ready-to-be-delivered messages.

* Recycle unused consensus objects; use round numbers info. from step (a).

* If the set of consensus round numbers (collected in line <ref>) include just one number, continue to the next consensus round by proposing $\mathit{allReady}_i$. Once the consensus has been completed, $p_i$ delivers the buffered messages that their individual message numbers, per sender, are not greater than the respective entries in the agreed vector.

\begin

$\CS[0..\6]$ $=[\bot,\bot,\bot]:$ consensus objects, where the proposed values are $(seq,ready)$, $seq$ is a consensus round number, and $ready$ is a vector of URB message numbers (one number per node).

$\xS=0:$ a local copy of the highest, possibly obsolete, consensus round number.

$\exceed()$: indicates the need for flushing the buffer, all URBs have been completed, or the number of messages exceeds a predefined constant, $\delta$.

* operation $\mathsf{toBroadcast}(m)$ do  FIFO-URB the message $m$ along with the message name $\mathsf{toURB}$.

* do forever

* Collect info. about round numbers and buffered messages. Query all trusted nodes, $p_j$, about $\xS_j$, $\getSeq_j()$, which is the highest consensus round number known to $p_j$, and $\maxReady_j()$, which is a vector of $p_j$'s ready-to-be-delivered $\mathsf{toURB}()$ messages (lines <ref> to <ref>).

Use the arriving values for calculating:

* $\maxSeq_i$: the greatest collected consensus round number.

* $\mathit{allSeq}_i$: the set of all collected consensus round numbers.

* $\mathit{allReady}_i$: a vector of message numbers, per sender, of the ready-to-deliver broadcasts that all nodes can perform.

* Recycle unused consensus objects. Nullify $\CS[]$'s unused entries, assign $\bot$ to any $\CS[k]$, for which $k \in \{0,1,\6\}$ is not one of the following (line <ref>):

* $\xS_i \bmod \7$, but only when $\xS < \getSeq_i()$, $\CS[]$'s highest consensus round number, $\getSeq_i()$, is higher than the locally highest obsolete round number, $\xS_i$. The reason is that $p_i$ still uses this entry.

* $\getSeq_i()$ $\bmod~ \7$ since there might be another node that is using it.

* $\maxSeq_i\mathit{+}1 \bmod 3$ but only when $|\mathit{allSeq}_i|=1$, there is a single consensus round number. This is because one should not nullify the next entry since another node might have already started to use it.

* Agree on the delivery order. If one collected consensus round number exists and it is time to flush the $\mathsf{toURB}()$ buffer, $\exceed()=\true$, call $\CS_i[\maxSeq_i+1~\bmod 3].propose(\maxSeq_i+1,\mathit{allReady}_i)$ (lines <ref> to <ref>).

If other nodes have higher rounds than $p_i$ or the current consensus object has completed, then:

* If the current object has been completed, deliver all messages that their individual consensus round numbers are not greater than the agreed ones (line <ref>).

* Finish the current consensus round, $\xS \gets \xS+1$ (line <ref>).

Overview of Algorithm <ref>; code for $p_i\in\sP$

\end

Going through the overview of  <ref>

The array $\CS[]$ stores three multivalued consensus objects, where the proposed values are $(seq,ready)$. The field $seq$ is a round number of a multivalued consensus invocation that moderates the ordered delivery of URB messages. The field $ready$ is a vector of URB message numbers (one number per node)—each number, say $ready[j]$, moderates the URB messages sent by $p_j$.
The integer $\xS$ holds the consensus round number that is locally considered to be the highest one, but possibly obsolete.
Once $p_i$ delivers the messages associated with $\CS[\xS \bmod 3].\done()$ (and the earlier ones), $p_i$ considers $\xS_i$ as obsolete.
Node $p_i$ recycles $\CS[\xS \bmod 3]$ once it knows that all other trusted nodes also consider $\xS$ as an obsolete round number.
Algorithm <ref> uses $\CS[]$ cyclically by considering $\xS$'s value modulus three.

As explained in Section <ref>, we use global reset for dealing with the event of $\xS$'s integer overflow.

Since Algorithm <ref> defers message delivery, there is a need to guarantee that such delivery occurs eventually. To that end, the macro $\exceed()$ identifies two cases in which the buffered messages should be flushed ($\exceed()$ returns $\true$): (i) the number of deferred messages exceeds a predefined constant, and (ii) there are no active URBs.

As mentioned, the invocation of $\mathsf{toBroadcast}(m)$ (line <ref>) leads to FIFO-URB of $\mathsf{toURB}(m)$. The do forever loop (line <ref>) makes sure that these $\mathsf{toURB}()$ messages can be delivered according to an order that all nodes agree on. To that end, a query is sent (line <ref>) to all nodes, $p_j$, about their current consensus round number, $\xS_j$, and the highest round numbers stored in $\CS[]$, $\getSeq_j()$, as well as the current status of their ready-to-deliver FIFO-URBs, $\maxReady_j()$. Node $p_i$ uses the arriving and local information (line <ref>) for calculating (i) the message numbers of all-nodes ready-to-deliver broadcasts, $\mathit{allReady}_i$, (ii) the maximum consensus round number, $\maxSeq_i$, and (iii) the set of all consensus round numbers that $p_i$ is aware of, $\mathit{allSeq}_i$.

This information allows $p_i$ to recycle stale entries in $\CS_i[]$. Specifically, line <ref> nullifies entries that are not used (or about to be used). Also, if there is just one collected consensus round number, $|\mathit{allSeq}_i|=1$, and it is time to flush the buffer of the $\mathsf{toURB}()$ messages, as indicated by $\exceed_i()$, then $p_i$ continues to the next agreement round by proposing the pair $(\maxSeq_i+1,\mathit{allReady}_i)$. As mentioned, such agreement on the value of the vector $\mathit{allReady}$ allows all nodes to deliver, in the same order, all the messages that their message numbers, per sender $p_k$, is not greater than  $\mathit{allReady}[k]$.

If $p_i$ notices that other nodes use a higher consensus round number than its own (which implies that they have already continued to the next consensus round) or its current consensus object has been completed, $p_i$ can deliver the buffered messages (line <ref>). Specifically, it tests whether the current consensus object has been completed. If so, it then delivers all messages that their individual message numbers are not greater than the one agreed by the completed object (line <ref>). In any case, it finishes the current consensus round by incrementing the agreement round number, $\xS$ (line <ref>).

A more detailed description of Algorithm <ref>

Algorithm <ref> queries all nodes about the messages that are ready-to-be-delivered (lines <ref> to <ref>), recycles unused consensus objects (line <ref>), agrees on the set of messages that are ready-to-be-delivered (line <ref>), and delivers these messages in the same order (lines <ref> to <ref>). We discuss in detail each part after describing notation, constants, variables (and how to bound them), and macros. The boxed code lines refer to the part that deals with the removal of stale information, which we explain  in Section <ref>.

Notations, constants, variables, and macros

<ref> presents the preliminaries for Algorithm <ref>. Modulo $3$ operations are denoted by $\mathsf{opr}_\7$, $x~ +_\7~ y\equiv (x+y)\bmod\7$ and $x~ -_\7~ y\equiv (x-y)\bmod\7$. The function $\text{entrywise-min}(V)$ takes the set of vectors, $V$, and returns the vector $v[]$, such that $v[k]:p_k \in \sP$ is the smallest $k$-th entry in any vector $v \in V$, $v[k]=\min \{v'[k]:v'\in V\}$.

As said, $\CS[]$ holds the consensus objects  that Algorithm <ref> accesses.

Algorithm <ref> aims at aggregating URB messages and delivering them only when all transmission activities have been completed, the $\nonActive()$ function returns $\true$ (Section <ref>). Since the number of such transmissions is unbounded, there is a need to stop aggregating after some predefined constant number of transmissions, $\delta$. The variable $\xS$ points to the local (highest), possibly obsolete, consensus round number.
The integer $\nextQuery$ stores the sequence number of the next query. As explained in Section <ref>, we use global reset for dealing with the event of integer overflow for the variables $\xS$ and $\nextQuery$.

The macro $\Sset()$ returns the set of consensus round numbers used by the active, non-$\bot$ entries in $\CS[]$. The macro $\getSeq()$ returns the maximum consensus round number in $\Sset()$.

The macro $\exceed()$ facilitates the decision about whether to invoke a new consensus. It returns $\true$ if there are non-delivered messages but no ongoing transmissions, $\nonActive()$ returns $\true$. It also returns $\true$ when the number of ready-to-be-delivered messages exceeds $\delta$ (regardless of the presence of active URB transmissions).

Querying (lines <ref> to <ref>)

Algorithm <ref> uses a query mechanism. Each query instance is associated with a unique query number that is stored in the variable $\nextQuery$ and incremented in line <ref>. Line <ref> broadcasts the synchronization query repeatedly until a reply is received from every trusted node. The query response (line <ref>) includes the correspondent's maximum consensus round number stored locally by any multivalued consensus object (that the macro $\getSeq()$ retrieves), the maximum possibly obsolete consensus round number (that its respective consensus object is, perhaps, no longer needed), and the latest value returned from $\maxReady_i()$. Using these responses (line <ref>), line <ref> aggregates the query results and store them in $\mathit{allReady}$, $\maxSeq$, and $\mathit{allSeq}$.
Specifically, the vector $\mathit{allReady}$ includes the entry-wise minimum (per sender) for $\mathsf{toURB}()$'s message identifiers that their messages are ready-to-be-delivered at all nodes. Also, $\maxSeq$ is the maximum known consensus round number. And, the set $\mathit{allSeq}$ includes all the maximum collected consensus round numbers and obsolete consensus round numbers.

Agreement (line <ref>)

The if-statement condition in line <ref> tests whether all trusted nodes share the same round number in $\xS$. This happens when all trusted nodes, $p_j \in \sP$, have $\xS_j=\getSeq_j()$. Line <ref> also checks whether $\exceed()$ indicates that it is the time to deliver. If this is the case, then line <ref> proposes to agree on the pair $(\xS,\mathit{allReady})$ using object $\CS[\xS+1\bmod 3]$.

Message delivery (lines <ref> to <ref>)

The delivery of a new $\mathsf{toURB}()$ message batch is possible once consensus has been achieved  (line <ref>). Before the delivery (line <ref>), there is a need to check that the consensus has been completed correctly (line <ref>), cf. the interface details in Section <ref>. In any case, $\xS$ is incremented (line <ref>) so that even if an error occurred, the object is recycled.

\begin
notations: $x~ \mathsf{opr}_\7~ y \equiv (x~ \mathsf{opr}~ y) \bmod \7:\mathsf{opr} \in \{\text{-},\text{+}\}$, $x~ +_\7~ y\equiv (x+y)\bmod\7$
$\text{entrywise-min}(V)\equiv [x_0,\ldots,x_k,\ldots,x_{n-1}] :  x_k =\min \{v[k] :v \in V\}$.

$\delta \in \mathbb{Z}^+$ max number of messages after which delivery is enforced.

$\CS[0..\6]$ $=[\bot,\bot,\bot]:$ array of multivalued consensus objects, where the proposed values are $(seq,ready)$, $seq$ is an instance number of a consensus object, and $ready$ is a vector of URB message numbers (one per node).

$\xS=0:$ a local copy of the highest, possibly obsolete, consensus round number.

$\nextQuery=0:$ is a query number.

required interface: $\mathsf{fifoURB}(m)$ FIFO-broadcast operation.

$\nonActive()$ indicates that, currently, there are no active URBs.

$\minReady()$ and $\maxReady()$ return each a vector, $r_i[0,..,n\text{-}1]$, such that $r[j]$ is the lowest, and resp., highest ready-to-deliver message number.

$\bulkRead(v)$ reads all locally ready-to-deliver messages that their individual message numbers, per sender $p_k$, is at most $v[k]$.

macros: $\Sset()= \{\CS[k].\mathit{seq}:\CS[k]\neq\bot \}_{k \in \{0,\ldots,\6 \}}$

$\getSeq()$ do $\max(\{\xS\} \cup \Sset())$

$\exceed()$ do $((\nonActive() \land 0<\ell)$ $\lor \delta \leq\ell)$ where $(x,y,\ell)=(\minReady(),$ $\maxReady(), \sum_{p_k \in \sP}(y[k]-x[k]))$

Notations, constants, variables, and macros for Algorithm <ref>

\end

\begin

For notations, constants, variables, and macros see  <ref>

operation $\mathsf{toBroadcast}(m)$ do $\mathbf{fifoURB}(\mathsf{toURB}(m))$

do forever

$(\exists k \in \{0,\ldots,\6 \} : \CS[k]\neq \bot \land \CS[k].\mathit{seq} \bmod \7 \neq k)\lor (\Sset()\neq \emptyset \land (\xS$ $ >\max \Sset() \lor$ $\max \Sset() - \min\Sset() > 1))$$\CS \gets [\bot, \bot ,\bot]$

$\nextQuery \gets \nextQuery+1$*start query number $\nextQuery$. Repeat until all trusted nodes have replied (line <ref>)

$\SYNCack(\nextQuery, \bullet)$ received from all $p_j: j\in \mathit{trusted}$
$p_j \in \sP$$\mathbf{send}~\SYNC(\nextQuery)~ \mathbf{to}~ p_j$

let $(\mathit{allReady},\maxSeq,\mathit{allSeq})=(\text{entrywise-min}\{x\}_{(\bullet,x) \in X}$, $\max \{x\}_{(\bull,x,\bullet) \in X}$, $\cup_{(\bull,x,y,\bull) \in X}\{x,y\})$ where $X$ is the set of messages received in line <ref>

let $(x,y,z)=(\xS,\getSeq(), \maxSeq)$;

$\neg (x\text{+}1 = y = z \lor x = y =z \lor x = y= z\text{-}1)$$\xS \gets \max \{x,y,z\}$

nullify entries in $\CS[]$ that are not used (or about to be)

$k \in \{0,\ldots,\6\} \setminus ( \{\xS \bmod \7 : \xS < \getSeq()\} \cup \{\getSeq()$ $\bmod~ \7 \}  \cup \{\maxSeq\text{+}_{\7}1 :|\mathit{allSeq}|=1\})$$\CS[k] \gets \bot$

start the next agreement round if there is just one consensus round number and it's time to flush the FIFO-URB buffer

$(|\mathit{allSeq}|=1\land \exceed())$

deliver buffered messages if other nodes use a higher consensus round number or the current consensus object has been completed

$\xS+ 1 = \getSeq() \land x \neq \bot  \land x.\done() \neq \bot$ where $x=\CS[(\xS+_{\7}1)]$

()$x.\done() \neq \blitza$foreach $m \in \bulkRead(x.\done())$ do $\mathsf{toDeliver}(m)$

$\xS \gets \xS+1$

reply to $\SYNC()$ messages with $\getSeq()$, $\xS$, and $\maxReady()$, which is a vector of $p_i$'s ready-to-be-delivered messages

upon $\SYNC(\mathit{\nextQueryJ})$ arrival from $p_j$ do $\mathbf{send}~\SYNCack(\mathit{\nextQueryJ}, \getSeq(), \xS, \maxReady())~ \mathbf{to}~ p_j$

Self-stabilizing TO-URB via consensus; code for $p_i$

\end

The removal of stale information

The occurrence of transient faults can introduce stale information via the corruption of the system state.
As mentioned, the variables $\xS$ and $\nextQuery$ may overflow (due to a transient fault). This can lead to a global restart (Section <ref>). Naturally, stale information can appear in the consensus objects of $\CS[]$. Therefore, line <ref> deactivates all the consensus objects, $x=\CS[k]$, whenever inconsistencies are observed. This occurs, specifically in line <ref>, if $k$ is not equal to $x$'s consensus round number modulo $\7$ or when $\xS$ is greater than any of the consensus round numbers stored in $\CS$, as well as the case in which that set includes anything but than one or two consecutive numbers.

Lines <ref> to <ref> consider the locally stored and query-collected consensus round numbers. Specifically, consistent values of $\xS$, $\getSeq()$, and $\maxSeq$ have to follow one of the three scenarios. (i) The locally highest obsolete consensus round number is smaller by one than the highest locally stored or collected number, $\xS+1=\getSeq()=\maxSeq$. (ii) All locally stored or collected round numbers are the same, $\xS=\getSeq()=\maxSeq$. (iii) The highest collected round number is higher by one than all local ones, $\xS=\getSeq()=\maxSeq-1$.

Correctness Proof of Algorithm <ref>

Definition <ref> defines Algorithm <ref>'s legal executions.
Invariants (i) and (ii) consider consistent states, which have no stale information.
Invariant (iii) considers predicate $Pred$, which depicts a system state in which all correct nodes use only one consensus round number in all of their variables, and thus, the nodes continue to the next consensus round and the delivery of pending messages (lines <ref> to <ref>).
Invariant (iii.a) investigates the case in which no $\mathsf{toBroadcast}()$ is invoked and requires the predicate $Pred$ to hold eventually.
Invariant (iii.b) investigates the complementary case in which $\mathsf{toBroadcast}()$ is invoked infinitely often, and requires the predicate $Pred$ to hold infinitely often.

Let $c$ be a system state and $p_i \in \sP$ be any node in the system. Suppose that in $c$, it holds that (i) the if-statement condition in line <ref> holds.

Moreover, (ii.a) $\nextQuery_i$'s value is greater than or equal to any $\mathit{\nextQueryJ}$ field in the message $\mathsf{SYNC}(\mathit{\nextQueryJ})$ in a communication channel from $p_i$ as well as $\mathrm{SYNCack}(\mathit{\nextQueryJ},\bullet)$ message in a communication channel to $p_i$. And (ii.b) $\xS_i \leq \getSeq_i() \leq \xS_i+\5$. In this case, we say that $c$ is consistent concerning Algorithm <ref>.

Suppose that $R$ is an execution of Algorithm <ref>, such that every $c \in R$ is consistent. In addition, (iii.a) suppose that if $\mathsf{toBroadcast}()$ is not invoked during $R$ nor do any FIFO-broadcast becomes available for delivery, then the predicate $pred$ holds throughout $R$, where $pred \equiv \exists z \in \mathbb{Z}^+:\forall k \in \mathit{Correct}: \getSeq_k()=z \land \mathit{maxSeq}_k=z \land \xS_k=z\land \mathit{allSeq}_k=\{z\}$. Furthermore, (iii.b) suppose that if $\mathsf{toBroadcast}()$ is invoked during $R$ infinitely often, then $pred$ holds infinitely often. In this case, we say that $R$ is legal.

Theorem <ref> uses Definition <ref> for showing that Algorithm <ref> is a self-stabilizing implementation of TO-URB. Its proof gives both the high-level proof overview and the exact proof arguments.

Within $\bigO(1)$ asynchronous cycles, Algorithm <ref>'s execution is legal w.r.t. TO-URB.

Due to line <ref>, Definition <ref>'s Invariant (i) holds after $p_i$ first complete iteration of the do-forever loop (lines <ref> to <ref>). (See Section <ref> for dealing with the case of $\xS$'s integer overflow event.) Lemma <ref> demonstrates Invariant (ii.a) by showing that, eventually,  Algorithm <ref> lets $p_i$ introduce a $\nextQuery_i$'s value that did not exist in the system. This value overtakes any stale information associated with $\nextQuery_i$.

Line <ref> implies Invariant (ii.b). 	Lemma <ref> shows invariant (iii).

Invariant (ii.a) holds.
Let $\nextQuery_i=x$ be the value of $p_i$'s $\nextQuery$ value in $R$'s starting system state. Within $\bigO(1)$ asynchronous cycles, $\nextQuery_i$'s value is greater than or equal to $x$ and any $\mathit{\nextQueryJ}$ field in the message $\mathsf{SYNC}(\mathit{\nextQueryJ})$ in a communication channel from $p_i$ as well as $\mathrm{SYNCack}(\mathit{\nextQueryJ},\bullet)$ message in a communication channel to $p_i$.

Only line <ref> modifies $\nextQuery_i$'s value, by increasing $\nextQuery_i$.
If $R$ includes the invocation of the global restart procedure (Section <ref>), then by the end of that procedure (which occurs within $\bigO(1)$ asynchronous cycles), Invariant (ii.a) holds.
Otherwise, $R$ does not include an integer overflow event.
By Assumption <ref>, within $\bigO(1)$ asynchronous cycles, any message is either delivered or lost. Therefore, within $\bigO(1)$ asynchronous cycles, the system includes only messages with $\nextQuery_i$'s values that line <ref> introduced to the system.
Thus, within $\bigO(1)$ asynchronous cycles, Invariant (ii.a) holds since $\nextQuery_i$'s value is monotonically increasing.

Lemma <ref>'s proof considers both invariants (iii.a), Claim <ref>, and (iii.b), Claim <ref>. Claim <ref> shows that, in the absence of $\mathsf{toBroadcast}()$ invocations, the system comes to a standstill point that allows all correct nodes to use only one consensus round number, which implies that the predicate $Pred$ holds. Claim <ref> has the form of a proof by contradiction and it shows that if $\mathsf{toBroadcast}()$ is invoked, infinitely often, $Pred$ eventually holds since all consensus objects complete their operations within $\bigO(1)$ asynchronous cycles.

We observe from Algorithm <ref> and Definition <ref> that once invariants (i) and (ii) of Definition <ref> hold, they are not violated. Thus, Lemma <ref>, which shows invariant (iii), assumes that invariants (i) and (ii) hold in every state of $R$.

Within $\bigO(1)$ asynchronous cycles, $R=R'\circ R''$ reaches a suffix, $R''$, in which invariants (iii.a) and (iii.b) hold.

Claim <ref> is needed for Lemma <ref>'s proof. It considers the query mechanism and shows that it collects a fresh dataset, $M_{\nextQuery_i}=\{(\nextQuery_i,s_k,o_k,r_k)\}_{k \in \mathit{trusted}_i}$, that includes one record per trusted node, where $s_k=\getSeq_k()$, $o_k=\xS_k$, and $r_k=\maxReady_k()$ are values sent by $p_k \in \sP$ after $p_i$'s current value has been assigned to $\nextQuery_i$.

Every complete iteration of the do-forever loop (lines <ref> to <ref>) allows $p_i \in \Correct$ to collect a fresh dataset, $M_{\nextQuery_i}$.

Due to invariant (ii.a), $\nextQuery_i$'s increment (line <ref>) creates a query number that is (associated with $p_i$ and) greater than all associated query numbers in the system. With this unique query number, the repeat-until loop (lines <ref> to <ref>) gets a fresh collection of $M_{\nextQuery_i}$. This loop cannot block due to the end-condition (line <ref>), which considers only the trusted nodes. The rest of the proof is implied directly by lines <ref>, <ref>, and <ref>.

Invariant (iii.a) holds.

Argument (1) Within $\bigO(1)$ asynchronous cycles, the if-statement condition in line <ref> does not hold.

By the assumption that no FIFO-broadcast becomes ready during $R$, it holds that the if-statement condition in line <ref> does not hold during $R$, because $\exceed()$ does not hold. By Assumption <ref>, all active multivalued consensus objects have been completed with $\bigO(1)$ asynchronous cycles. Therefore, within $\bigO(1)$ asynchronous cycles, the if-statement condition in line <ref> cannot hold. (This is true because every time that it does hold, line <ref> increments $\xS$, but since the if-statement condition in line <ref> does not hold, this can only happen once.)

Argument (2) Within $\bigO(1)$ asynchronous cycles, $\forall i \in \mathit{Correct}:\forall k \in \mathit{trusted}_i :\mathit{maxSeq}_i=\getSeq_k()$.

Due to Lemma <ref>, $\forall i \in \mathit{Correct}:\forall k \in \mathit{trusted}_i :\mathit{maxSeq}_i\geq\getSeq_k()$. Due to the foreach condition in line <ref> and the if-statement in line <ref>, within $\bigO(1)$ asynchronous cycles, line <ref> deactivates any consensus object, $O_{i:p_i \in \sP,x \in \{0,\ldots, \6\}}=\mathit{CS}_i[x]$ for which $O_{i,x}.\mathit{seq}<\mathit{maxSeq}_i-1$. By using Assumption <ref> again, any re-activated multivalued consensus object has to complete with $\bigO(1)$ asynchronous cycles. Thus, the above implies that the state of any multivalued consensus object, active or not, does not change and that $\forall i \in \mathit{Correct}:\forall k \in \mathit{trusted}_i :\mathit{maxSeq}_i=\getSeq_k()$.

Argument (3) Within $\bigO(1)$ asynchronous cycles, $\xS_i = \getSeq_i()$ holds.

By Invariant (ii.b) of Definition <ref>, either $\xS_i+ 1 = \getSeq_i()$ or $\xS_i = \getSeq_i()$.
Suppose $\xS_i+ 1 = \getSeq_i()$ holds. Due $\getSeq()$'s definition as well as lines <ref> and <ref>, $x_i \neq \bot$, where $x_i=\mathit{CS}_i[(\xS_i+_{\7}1)]$ (line <ref>). By Assumption <ref>, within $\bigO(1)$ asynchronous cycles, the consensus object $x_i$ completes. Thus, the if-statement condition in line <ref> holds and line <ref> increments $\xS_i$ once. Therefore, $\xS_i = \getSeq_i()$ within $\bigO(1)$ asynchronous cycles.

Argument (4) Within $\bigO(1)$ asynchronous cycles, the predicate $pred$ (Definition <ref>) holds.

Since $\forall i \in \mathit{Correct}:\forall k \in \mathit{trusted}_i :\mathit{maxSeq}_i=\getSeq_k()=\xS_k$, then $\mathit{allSeq}_k=\{z\}$, where $\forall i \in \mathit{Correct}:\forall k \in \mathit{trusted}_i :z=\mathit{maxSeq}_i=\getSeq_k()=\xS_k$. Thus, $pred$ holds.

Argument (2) Invariant (iii.b) holds.

Note that $\exceed_i()$ holds infinitely often by the assumption that $\mathsf{toBroadcast}()$ is invoked infinitely often and URB-completion.

We show that the if-statement condition in line <ref> holds within $\bigO(1)$ asynchronous cycles once $\exceed_i()$ holds. Suppose, towards a contradiction, $|\mathit{allSeq}|=1$ does not hold for a period longer than $\bigO(1)$ asynchronous cycles. Then, the then-statement in line <ref> is not executed for a period longer than $\bigO(1)$ asynchronous cycles. In other words, for a period longer than $\bigO(1)$ asynchronous cycles, no new round numbers are introduced to the system. By arguments similar to the ones in Claim <ref>, the predicate $pred$ holds within $\bigO(1)$ asynchronous cycles. Thus, the if-statement condition in line <ref> holds within $\bigO(1)$ asynchronous cycles.	In other words, Invariant (iii.b) holds.

\begin

do forever

$(|\mathit{allSeq}|=1\land \exceed())$

$\xS+ 1 = \getSeq() \land x \neq \bot  \land x.\done() \neq \bot$ where $x=\CS[(\xS+_{\7}1)]$
$x.\done() \neq \blitza$$\mathsf{setState}(x.\done().state)$;

foreach $m \in \bulkRead(x.\done().msg)$ do $\mathsf{toDeliver}(m)$;

Self-stabilizing state-machine replication;  code for $p_i\in\sP$

\end

We proposed, to the best of our knowledge, the first self-stabilizing algorithm for total-order uniform reliable broadcast. This is built atop self-stabilizing algorithms for FIFO-URB and multivalued consensus.

As an application to our proposal, Algorithm <ref> explains how to construct a self-stabilizing emulator for state-machine replication. Note that Algorithm <ref>'s line numbers are the ones of Algorithm <ref>. Line <ref> of Algorithm <ref> proposes to agree on both the automaton state, which is retrieved by $\mathsf{getState}()$, and the bulk of FIFO-URB messages, as in line <ref> of Algorithm <ref>. Line <ref> of Algorithm <ref> uses $\mathsf{setState}()$ for updating the local state of the automaton using the agreed state.

We encourage the reader to use our solution and techniques when designing distributed systems that must recover from transient faults.

[1]
Noga Alon, Hagit Attiya, Shlomi Dolev, Swan Dubois, Maria Potop-Butucaru, and
Sébastien Tixeuil.
Practically stabilizing SWMR atomic memory in message-passing
J. Comput. Syst. Sci., 81(4):692–701, 2015.

[2]
Karine Altisen, Stéphane Devismes, Swan Dubois, and Franck Petit.
Introduction to Distributed Self-Stabilizing Algorithms.
Morgan & Claypool Publishers, 2019.

[3]
Anish Arora and Mohamed G. Gouda.
Closure and convergence: A foundation of fault-tolerant computing.
IEEE Trans. Software Eng., 19(11):1015–1027, 1993.

[4]
Joffroy Beauquier and Synnöve Kekkonen-Moneta.
Fault-tolerance and self-stabilization: impossibility results and
solutions using self-stabilizing failure detectors.
Int. J. Systems Science, 28(11):1177–1187, 1997.

[5]
Peva Blanchard, Shlomi Dolev, Joffroy Beauquier, and Sylvie Delaët.
Practically self-stabilizing Paxos replicated state-machine.
In NETYS, volume 8593 of LNCS, pages 99–121. Springer,

[6]
François Bonnet, Xavier Défago, Thanh Dang Nguyen, and Maria
Tight bound on mobile Byzantine agreement.
Theor. Comput. Sci., 609:361–373, 2016.

[7]
Silvia Bonomi, Shlomi Dolev, Maria Potop-Butucaru, and Michel Raynal.
Stabilizing server-based storage in Byzantine asynchronous
message-passing systems: Extended abstract.
In PODC, pages 471–479. ACM, 2015.

[8]
Silvia Bonomi, Antonella Del Pozzo, and Maria Potop-Butucaru.
Optimal self-stabilizing synchronous mobile Byzantine-tolerant
atomic register.
Theor. Comput. Sci., 709:64–79, 2018.

[9]
Silvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru, and Sébastien
Optimal mobile Byzantine fault tolerant distributed storage:
Extended abstract.
In PODC, pages 269–278. ACM, 2016.

[10]
Silvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru, and Sébastien
Optimal storage under unsynchronized mobile Byzantine faults.
In SRDS, pages 154–163. IEEE Computer Society, 2017.

[11]
Marco Canini, Iosif Salem, Liron Schiff, Elad Michael Schiller, and Stefan
Renaissance: A self-stabilizing distributed SDN control
plane using in-band communications.
J. Comput. Syst. Sci., 127:91–121, 2022.

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

[13]
Shlomi Dolev.
MIT Press, 2000.

[14]
Shlomi Dolev, Chryssis Georgiou, Ioannis Marcoullis, and Elad Michael Schiller.
Self-stabilizing reconfiguration.
In NETYS, volume 10299 of LNCS, pages 51–68, 2017.

[15]
Shlomi Dolev, Chryssis Georgiou, Ioannis Marcoullis, and Elad Michael Schiller.
Practically-self-stabilizing virtual synchrony.
J. Comput. Syst. Sci., 96:50–73, 2018.

[16]
Shlomi Dolev, Chryssis Georgiou, Ioannis Marcoullis, and Elad Michael Schiller.
Self-stabilizing Byzantine tolerant replicated state machine based
on failure detectors.
In CSCML, volume 10879 of Lecture Notes in Computer
Science, pages 84–100. Springer, 2018.

[17]
Shlomi Dolev, Ronen I. Kat, and Elad Michael Schiller.
When consensus meets self-stabilization.
J. Comput. Syst. Sci., 76(8):884–900, 2010.

[18]
Shlomi Dolev, Thomas Petig, and Elad Michael Schiller.
Self-stabilizing and private distributed shared atomic memory in
seldomly fair message passing networks.
Algorithmica. Also appears in CoRR, abs/1806.03498, 2022.

[19]
Romaric Duvignau, Michel Raynal, and Elad Michael Schiller.
Self-stabilizing byzantine- and intrusion-tolerant consensus.
CoRR, abs/2110.08592, 2021.

[20]
Romaric Duvignau, Michel Raynal, and Elad Michael Schiller.
Self-stabilizing byzantine-tolerant broadcast.
To appear in SSS'22 and also in CoRR, abs/2201.12880, 2022.

[21]
Chryssis Georgiou, Oskar Lundström, and Elad Michael Schiller.
Self-stabilizing snapshot objects for asynchronous failure-prone
networked systems.
In Networked Systems, NETYS, pages 113–130, 2019.

[22]
Chryssis Georgiou, Ioannis Marcoullis, Michel Raynal, and Elad Michael
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.

[23]
Vassos Hadzilacos and Sam Toueg.
A modular approach to fault-tolerant broadcasts and related problems.
Technical report, Cornell Univ., Ithaca, NY, 1994.

[24]
Colette Johnen, Luciana Arantes, and Pierre Sens.
FIFO and atomic broadcast algorithms with bounded message size for
dynamic systems.
In SRDS, pages 277–287. IEEE, 2021.

[25]
Oskar Lundström, Michel Raynal, and Elad Schiller.
Self-stabilizing uniform reliable broadcast.
In Networked Systems NETYS, volume 12129 of LNCS, pages
296–313. Springer, 2020.

[26]
Oskar Lundström, Michel Raynal, and Elad Michael Schiller.
Self-stabilizing set-constrained delivery broadcast.
In 40th IEEE International Conference on Distributed Computing
Systems, ICDCS, pages 617–627. IEEE, 2020.

[27]
Oskar Lundström, Michel Raynal, and Elad Michael Schiller.
Self-stabilizing indulgent zero-degrading binary consensus.
In 22nd Distributed Computing and Networking ICDCN, pages
106–115, 2021.

[28]
Oskar Lundström, Michel Raynal, and Elad Michael Schiller.
Self-stabilizing multivalued consensus in asynchronous crash-prone
In 17th European Dependable Computing Conference, EDCC, pages
111–118. IEEE, 2021.

[29]
Oskar Lundström, Michel Raynal, and Elad M. Schiller.
Self-stabilizing uniform reliable broadcast.
In Networked Systems, (NETYS'20) Springer LNCS 12129,
pages 296–313, 2020.
Also in CoRR abs/2001.03244.

[30]
Alexandre Maurer and Sébastien Tixeuil.
Self-stabilizing Byzantine broadcast.
In 33rd IEEE International Symposium on Reliable Distributed
Systems, SRDS, pages 152–160, 2014.

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

[32]
Iosif Salem and Elad Michael Schiller.
Practically-self-stabilizing vector clocks in the absence of
execution fairness.
In Networked Systems NETYS, pages 318–333, 2018.


n^{-1/2})\log(1/\varepsilon),$

with sufficiently large $C^{\prime}>0$. We set $\varepsilon=Kn^{-5/8}$ and
$K=n^{1/3}$, then we obtain the result. ∎

##  Appendix G Proof for Examples (Section 6)

We provide a technical details of Section 6 for the explicit M-estimators as
example.

###  G.1. Cubic root estimator

We provide the proof for the cubic root estimator in Section 6.1. Let
$\Theta\ni\theta$ be a compact interval $\Theta=[0,1]$ with
$\|\theta\|=|\theta|$ and assume $P_{Z}$ as a positive finite density on
$\mathcal{Z}=[0,1]$.

###### Proof of Corollary 5.

We verify that the assumptions are satisfied. About Assumption 1, $\Theta$ is
a subset of $\mathbb{R}$, hence the conditions (A1) and (A2) hold. We have an
envelope function $F(x)=1$ such as $\|F\|_{L^{2}(P)}\vee\|F\|_{L^{\infty}}$ by
$1$, hence the condition (A3) is also satisfied. About the condition (A4), a
simple calculation yields
$\|f_{\theta}-f_{\theta^{\prime}}\|_{L^{1}}=2|\theta^{\prime}-\theta|$ and it
is satisfied with $q=1$ and $c=2$.

To verify the condition (A2) in Assumption 1, we calculate
$\|f_{\theta}-f_{\theta^{\prime}}\|_{L^{1}}$ with
$\theta,\theta^{\prime}\in\Theta$ with $\theta\leq\theta^{\prime}$ as

$\displaystyle\|f_{\theta}-f_{\theta^{\prime}}\|_{L^{1}}$
$\displaystyle=\int_{\mathcal{Z}}|\textbf{1}\\{\theta-1\leq
z\leq\theta+1\\}-\textbf{1}\\{\theta^{\prime}-1\leq
z\leq\theta^{\prime}+1\\}|dz$ $\displaystyle=2|\theta^{\prime}-\theta|.$

Hence, the condition (A4) holds with $q=1$ and $c_{\ell}=2$.

We validate Assumption 2. As preparation, we consider there are $p+1$ grids
$\\{\theta_{j}\\}_{j=1}^{p+1}\subset\Theta$ and they are equally spaced such
as $|\theta_{j}-\theta_{j^{\prime}}|=\delta|j-j^{\prime}|$ with
$\delta>0,\delta p\leq 1$. By the grids, we can specify the covariance matrix
$\Sigma$ whose $(j,j^{\prime})$-th element is
$\operatorname{Cov}_{Z}(f_{\theta_{j}}(Z),f_{\theta_{j^{\prime}}}(Z))$ for
$j,j^{\prime}\in[p+1]$. The covariance it written as

$\displaystyle\operatorname{Cov}_{Z}(f_{\theta_{j}}(Z),f_{\theta_{j^{\prime}}}(Z))$
$\displaystyle=\mathbb{E}_{Z}[(f_{\theta_{j}}(Z)-1/2)(f_{\theta_{j^{\prime}}}(Z)-1/2)]$
$\displaystyle=\mathbb{E}_{Z}[f_{\theta_{j}}(Z)f_{\theta_{j^{\prime}}}(Z)]-\mathbb{E}[f_{\theta_{j}}(Z)+f_{\theta_{j^{\prime}}}(Z)]/2+1/4$
$\displaystyle=\mathbb{E}_{Z}[\textbf{1}\\{(\theta^{\prime}\vee\theta)-1\leq
Z\leq(\theta\wedge\theta^{\prime})+1\\}]-1/4$
$\displaystyle=2-|\theta_{j}-\theta_{j^{\prime}}|-1/4$
$\displaystyle=7/4-\delta|j-j^{\prime}|.$ (39)

Then, we obtain the covariance matrix form (4). By Proposition 3, we obtain
the statement. ∎

Proposition 3 plays a critical role for the analysis on the cubic root
estimator. To prove the result, our aim is to develop a lower bound for
diagonal elements of a conditional covariance matrix by $\Sigma$.

###### Proof of Proposition 3.

For brevity, we only investigate a coniditional variance on the first grid
$\theta_{1}$ as

$\displaystyle\operatorname{Var}(f_{\theta_{1}}(z)|f_{\theta_{2}}(z),...,f_{\theta_{p+1}}(z))=\operatorname{Var}(f_{\theta_{1}}(z))-\Sigma_{2:p+1,1}\Sigma_{2:p+1,2:p+1}^{-1}\Sigma_{1,p+1:2}.$

Conditional variance on the other parameter grids is bounded by a similar way.
For the derivation, we define a $p\times p$ matrix $M^{(p)}$ with its
$(i,j)$-th element is

$\displaystyle c-\delta|i-j|.$

for $i,j=1,...,p$, and a vector $v^{(p)}\in\mathbb{R}^{p}$ as

$\displaystyle v^{(p)}:=\begin{pmatrix}c-\delta\\\ c-2\delta\\\ \vdots\\\
c-p\delta\end{pmatrix}.$

Then, we can rewrite the conditional variance as

$\displaystyle\operatorname{Var}(f_{\theta_{1}}(z)|f_{\theta_{2}}(z),...,f_{\theta_{p+1}}(z))=c-(v^{(p)})^{\top}(M^{(p)})^{-1}v^{(p)}$
(40)

To derive the inverse matrix $(M^{(p)})^{-1}$, we utilize a cofactor matrix
based approach. Let $\widehat{M}^{(p)}\in\mathbb{R}^{p\times p}$ be a sign-
adjusted cofactor matrix of $M^{(p)}$, i.e.,
$\widehat{M}_{i,j}^{(p)}={m}^{(p)}_{i,j}:=(-1)^{(i+j)}|M_{-i,-j}^{(p)}|$ where
$M_{-i,-j}^{(p)}$ is a $(p-1)\times(p-1)$ sub-matrix of $M^{(p)}$ by
eliminating its $i$-th row and $j$-th column. Then, we can reform the inverse
matrix as

$\displaystyle(v^{(p)})^{\top}(M^{(p)})^{-1}v^{(p)}=|M^{(p)}|^{-1}(v^{(p)})^{\top}\widehat{M}^{(p)}v^{(p)},$

for arbitrary $i\in[p]$. To achieve the value of $|M^{(p)}|$ and
$\widehat{M}^{(p)}$, we derive an explicit value of $m_{i,j}^{(p)}$ in the
following result:

######  Lemma 11.

For each integer $p\geq 3$, we obtain the following form:

$\displaystyle
m^{(p)}_{1,1}=m^{(p)}_{p,p}=2^{p-2}c\delta^{p-2}-(p-2)2^{p-3}\delta^{p-1},$
$\displaystyle
m^{(p)}_{i,i}=2^{p-1}c\delta^{p-2}-(p-1)2^{p-2}\delta^{p-1},~{}(i=2,...,p-1),$
$\displaystyle
m_{i,j}^{(p)}=-2^{p-2}c\delta^{p-2}+(p-1)2^{p-3}\delta^{p-1},~{}(|i-j|=1),$
$\displaystyle m^{(p)}_{1,p}=m^{p}_{p,1}=2^{p-3}\delta^{p-1}$ $\displaystyle
m^{(p)}_{i,j}=0,~{}(\mbox{otherwise}).$

Furthermore, we obtain

$\displaystyle|M^{(p)}|=2^{p-1}c\delta^{p-1}-(p-1)2^{p-2}\delta^{p}.$

###### Proof of Lemma 11.

The result is shown by the mathematical induction. When $p=3$, simple
calculation yields

$\displaystyle\widehat{M}^{(3)}=\begin{pmatrix}m_{1,1}^{(3)}&m_{1,2}^{(3)}&m_{1,3}^{(3)}\\\
m_{2,1}^{(3)}&m_{2,2}^{(3)}&m_{2,3}^{(3)}\\\
m_{3,1}^{(3)}&m_{3,2}^{(3)}&m_{3,3}^{(3)}\end{pmatrix}=\begin{pmatrix}2c\delta-\delta^{2}&-2c\delta+2\delta^{2}&\delta^{2}\\\
-2c\delta+2\delta^{2}&4c\delta-4\delta^{2}&-2c\delta+2\delta^{2}\\\
\delta^{2}&-2c\delta+2\delta^{2}&2c\delta-\delta^{2}\end{pmatrix}.$

Also, we have

$\displaystyle|M^{(3)}|=cm_{1,1}^{(3)}+(c-\delta)m_{1,2}^{(3)}+(c-2\delta)m_{1,3}^{(3)}=4c\delta^{2}-4\delta^{3}.$

Hence, the statement holds with $p=3$.

Suppose that the statement is valid with $p=k-1$, then consider the case with
$p=k$. Then, troublesome but standard calculation yields

$\displaystyle
m_{1,1}^{(k)}=m_{k,k}^{(k)}=\sum_{i=1}^{k}(c-(i-1)\delta)m_{1,i}^{(k-1)}=2^{k-2}c\delta^{k-2}-(k-2)2^{k-3}\delta^{k-1}.$

For the other terms $m^{(k)}_{i,i},m^{(k)}_{i,j}$ and $m^{(k)}_{i,k}$, the
same way yields the desired result. Also, we obtain

$\displaystyle|M^{(k)}|=\sum_{i=1}^{k}(c-(i-1)\delta)m_{1,i}^{(k)}=2^{k-1}c\delta^{k-1}-(k-1)2^{k-2}\delta^{k}.$

Then, we obtain the statement. ∎

By this lemma, we have

$\displaystyle(b^{(p)})^{\top}\widehat{M}^{(p)}b^{(p)}$
$\displaystyle=\sum_{i=1}^{p}\sum_{j=1}^{p}(c-i\delta)(c-j\delta)m_{i,j}^{(p)}$
$\displaystyle=(c-\delta)^{2}(2^{p-1}c\delta^{p-2}-(p-2)2^{p-3}\delta^{p-1})$
$\displaystyle\quad+(c-p\delta)^{2}(2^{p-1}c\delta^{p-2}-(p-2)2^{p-3}\delta^{p-1})$
$\displaystyle\quad+\sum_{i=2}^{p-1}(c-i\delta)^{2}(2^{p-1}c\delta^{p-2}-(p-1)2^{p-2}\delta^{p-1})$
$\displaystyle\quad+2\sum_{i=1}^{p-1}(c-i\delta)(c-(i+1)\delta)-2^{p-2}c\delta^{p-2}+(p-1)2^{p-3}\delta^{p-1}$
$\displaystyle\quad+2(c-\delta)(c-p\delta)2^{p-3}\delta^{p-1}$
$\displaystyle=2^{p-2}\delta^{p-1}(2c^{2}-(3+p)c\delta+2p\delta^{2}).$

By combining this result with (40), we achieve

$\displaystyle c-(b^{(p)})^{\top}(M^{(p)})^{-1}b^{(p)}$
$\displaystyle=c-\frac{2^{p-2}\delta^{p-1}(2c^{2}-(3+p)c\delta+2p\delta^{2})}{|M^{(p)}|}$
$\displaystyle=c-\frac{2^{p-2}\delta^{p-1}(2c^{2}-(3+p)c\delta+2p\delta^{2})}{2^{p-1}c\delta^{p-1}-(p-1)2^{p-2}\delta^{p}}$
$\displaystyle=\frac{2\delta(2c-p\delta)}{2c-(p-1)\delta}$
$\displaystyle\gtrsim\delta.$

Then, we achieve the statement. ∎

###  G.2. Least Absolute Deviation Regression

We provide the details of the least absolute deviation regression problem in
Section 6.2.

###### Proof of Corollary 6.

We set $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}=[-1,1]\times[-1,1]$ and set
$\Theta=[-1,1]$. Without the loss of generality, we set $Y$ is a uniform
random variable on $[0,1/2]$ and $X=1$ almost surely for brevity. In this
case, the conditions (A1), (A3), and (A4) in Assumption 1 are satisfied. In
this setting, $f_{\theta}$ is bounded by $2$, so we obtain
$\|F\|_{L^{2}(P_{Z})}\vee\leq\|F\|_{L^{\infty}(P_{Z})}\leq 2$. For the
condition (A2), we bound the difference
$\|f_{\theta}-f_{\theta^{\prime}}\|_{L^{2}}$ for
$\theta,\theta^{\prime}\in\Theta$. We have a sub-additivity of the norm
$|x+x^{\prime}|\leq|x|+|x^{\prime}|$, hence we can utilize the reverse
triangle inequality $||x|-|x^{\prime}||\leq|x-x^{\prime}|$. Then,

$\displaystyle\|f_{\theta}-f_{\theta^{\prime}}\|_{L^{1}}$
$\displaystyle=\int||y-x\theta|-|y-x\theta^{\prime}||dP_{Z}(x,y)$
$\displaystyle\leq\int|x\theta-x\theta^{\prime}|d\lambda(x)$
$\displaystyle\leq|\theta-\theta^{\prime}|\int|x|d\lambda(x)$
$\displaystyle\leq\|\theta-\theta^{\prime}\|.$

Hence, the condition (A2) holds with $q=1$ and $c=1$.

We investigate Assumption 2 for this regression model. Similar to the previous
section, we consider $p+1$ grids $\\{\theta_{j}\\}_{j=1}^{p+1}\subset\Theta$
and they are equally spaced such as
$|\theta_{j}-\theta_{j^{\prime}}|=\delta|j-j^{\prime}|$ with $\delta>0,\delta
p\leq 1/2$. By the grids, we can specify the covariance matrix $\Sigma$ whose
$(j,j^{\prime})$-th element is
$\operatorname{Cov}_{Z}(f_{\theta_{j}}(Z),f_{\theta_{j^{\prime}}}(Z))$ for
$j,j^{\prime}\in[p+1]$. Consider parameters
$\theta,\theta^{\prime}\in\\{\theta_{j}\\}_{j=1}^{p+1}$ such that
$\theta^{\prime}\geq\theta$. Its covariance is written as

$\displaystyle\operatorname{Cov}_{Z}(f_{\theta}(Z),f_{\theta^{\prime}}(Z))=\mathbb{E}_{Y}\left[|Y-\theta||Y-\theta^{\prime}|\right]-\mathbb{E}_{Y}\left[|Y-\theta|\right]\mathbb{E}_{Y}\left[|Y-\theta^{\prime}|\right].$
(41)

A simple calculation yields

$\displaystyle\mathbb{E}_{Y}\left[|Y-\theta|\right]$
$\displaystyle=\mathbb{P}_{Y}(Y\leq\theta)\mathbb{E}_{Y}\left[(Y-\theta)\mid
Y\leq\theta\right]+\mathbb{P}_{Y}(Y>\theta)\mathbb{E}_{Y}\left[(Y-\theta)\mid
Y>\theta\right]$ $\displaystyle=\theta^{2}-3\theta+\frac{9}{2}.$

By a similar way, we obtain

$\displaystyle\mathbb{E}_{Y}\left[|Y-\theta||Y-\theta^{\prime}|\right]=9-9\theta+3\theta^{2}-\frac{9}{2}|\theta-\theta^{\prime}|+\frac{1}{3}|\theta^{\prime}-\theta|^{3}+3\theta|\theta-\theta^{\prime}|.$

Substituting the results into (41), we obtain

$\displaystyle\operatorname{Cov}_{Z}(f_{\theta}(Z),f_{\theta^{\prime}}(Z))=C_{0}(\theta)-C_{1}(\theta)|\theta^{\prime}-\theta|+C_{2}(\theta)|\theta^{\prime}-\theta|^{2}+\frac{|\theta^{\prime}-\theta|^{3}}{3},$

where $C_{0}(\theta)=576/64-71\theta/8+5\theta^{2}/2+\theta^{3}-\theta^{4}$,
$C_{1}(\theta)=71/16-5\theta/2-3\theta^{2}/2+2\theta^{3}$, and
$C_{2}(\theta)=-1/8+\theta/2-\theta^{2}/2$. We can simply rewrite the
covariance as

$\displaystyle\operatorname{Cov}_{Z}(f_{\theta}(Z),f_{\theta^{\prime}}(Z))$
$\displaystyle=C_{0}(\theta)-C_{1}(\theta)/16+(C_{2}(\theta)+1/48)|\theta-\theta^{\prime}|^{2}$
$\displaystyle\quad+(C_{1}(\theta)-|\theta^{\prime}-\theta|^{2}/3)(1/16-|\theta^{\prime}-\theta|)$
$\displaystyle=\underbrace{C_{3}(\theta)+(5/48-\theta/2+\theta^{2})(-\theta^{\prime
2}+2\theta\theta^{\prime})}_{=:I(\theta,\theta^{\prime})}$
$\displaystyle\quad+\underbrace{(C_{4}(\theta)-\theta^{\prime
2}/3+2\theta\theta^{\prime}/3)(1/16-|\theta^{\prime}-\theta|)}_{=:II(\theta,\theta^{\prime})},$

where
$C_{3}(\theta)=2233/256-279\theta/32-241\theta^{2}/96-13\theta^{3}/32-3\theta^{4}/2$
and $C_{4}(\theta)=19/4-5\theta/2-\theta^{2}+2\theta^{3}$.

Now, we consider the covariance matrix $\Sigma\in\mathbb{R}^{p\times p}$ by a
matrix form. Based on the covariance form of $I(\theta,\theta^{\prime})$ and
$II(\theta,\theta^{\prime})$, we utilize matrices
$M^{A},M^{B},M^{C},M^{D},M^{E}\in R^{p\times p}$ and obtain

$\displaystyle\Sigma=M^{A}+(M^{B}+M^{C}+M^{D})M^{E},$

where there elements are $M^{E}_{i,j}=1/16-|\theta_{i}-\theta_{j}|$,
$M^{A}_{i,j}=I(\theta_{i},\theta_{j})$,
$M^{B}_{i,j}=\textbf{1}(i=j)C_{4}(\theta_{i})$,
$M^{C}_{i,j}=\textbf{1}(i=j)(-\theta_{j}^{2}/3)$, and
$M^{D}_{i,j}=2\theta_{i}\theta_{j}/3$. WE note that $M^{B}$ and $M^{C}$ are
diagonal matrices, since their elements only depend on one of $\theta$ or
$\theta^{\prime}$.

We will develop a lower bound of $\lambda_{\min}(\Sigma)$ by evaluating an
eigenvalue and positive definiteness of the matrices. For $M^{E}$, Proposition
3 states that $\lambda_{\min}(M^{E})\gtrsim\delta$ as $\delta\to 0$. With a
vector $b=(\theta_{1},...,\theta_{p})$, we obtain a form $M^{D}=bb^{\top}$,
hence $M^{D}$ has one positive eigenvalue and other eigenvalues are zero.
Then, it is positive semi-definite. Since $M^{B}$ and $M^{D}$ are diagonal,
their minimum diagonal elements represent theire minimum eigenvalue. Since
$C_{4}(\theta)>2$ and $-\theta^{2}/3\geq-1/3$, $M^{B}+M^{C}$ is a strictly
positive definite matrix. By the result, we obtain that
$\lambda_{\min}((M^{B}+M^{C}+M^{D})M^{E})\gtrsim\delta$. For the matrix
$M^{A}$, by the similar discussion and the fact $C_{3}(\theta)>2$, we can show
that $M^{A}$ is strictly positive definite. Finally, we have
$\lambda_{\min}(\Sigma)\gtrsim\delta$, and Proposition 1 states the claim. ∎

###  G.3. Minimum Volume Prediction

We verify the conditions with $f_{\theta}(z)$ of the minimum volume prediction
in Section 6.3.

###### Proof of Corollary 7.

Without loss of generality, we assume $Y|X$ follows a uniform distribution on
$[0,1]$ for any $X$ and $\iota>1/2$. For Assumption 1, the conditions (A1) and
(A3) hold immediately by the setting of $\Theta$. The condition (A4) also
holds by the boundedness and integrability of $K$ which follows the setting of
the kernel and $K(x)=o(1/x)$. About the condition (A2), the positivity of the
kernel yields

$\displaystyle\|f_{\theta}-f_{\theta^{\prime}}\|_{L^{1}}$
$\displaystyle=\mathbb{E}_{X,Y}\Biggl{[}K\left(\frac{X_{i}-x}{h_{n}}\right)\\{|\textbf{1}\\{Y_{i}\in[\theta-\iota,\theta+\iota]\\}-\textbf{1}\\{Y_{i}\in[\theta^{\prime}-\iota,\theta^{\prime}+\iota]\\}|\\}\Biggr{]}$
$\displaystyle=\mathbb{E}_{X}\left[K\left(\frac{X-x}{h_{n}}\right)\mathbb{E}_{Y|X}[|\textbf{1}\\{Y_{i}\in[\theta-\iota,\theta+\iota]\\}-\textbf{1}\\{Y_{i}\in[\theta^{\prime}-\iota,\theta^{\prime}+\iota]\\}|]\right]$
$\displaystyle=C_{K}\mathbb{P}_{Y|X}\left(Y\in[\theta\wedge\theta^{\prime}-\iota,\theta\vee\theta^{\prime}-\iota]\cup[\theta\wedge\theta^{\prime}+\iota,\theta\vee\theta^{\prime}+\iota]\right)$
$\displaystyle=2C_{K,n}|\theta-\theta^{\prime}|,$

where $C_{K}=\mathbb{E}_{X}[K((X-x)/h_{n})]$ which is bounded by following the
properties of $K$. The first inequality follows the iterated expectation, and
the last equality follows the distribution of $Y$. Hence, the condition (A2)
holds with $q=1$ and $c_{\ell}=2C_{K}$. For Assumption 2, we obtain
$\mathbb{E}_{Z}[f_{\theta}(Z)]=2C_{K,n}{\iota},\forall\theta\in\Theta$ and

$\displaystyle\operatorname{Cov}_{Z}(f_{\theta}(Z),f_{\theta^{\prime}}(Z))$
$\displaystyle=\mathbb{E}_{Z}[f_{\theta}(Z)f_{\theta^{\prime}}(Z)]-\mathbb{E}_{Z}[f_{\theta}(Z)]\mathbb{E}_{Z}[f_{\theta^{\prime}}(Z)]$
$\displaystyle=\mathbb{E}_{X,Y}\left[K\left(\frac{X-x}{h_{n}}\right)^{2}\textbf{1}\\{\theta\vee\theta^{\prime}-{\iota}\leq
Y\leq\theta\wedge\theta^{\prime}+{\iota}\\}\right]-2C_{K,n}{\iota}^{2}$
$\displaystyle=\widetilde{C}_{K,n}|\theta-\theta^{\prime}|-2C_{K,n}{\iota}^{2},$

where $\widetilde{C}_{K,n}=\mathbb{E}_{X}[K((X-x)/h_{n})^{2}]$ which is
guaranteed to exist. By the form, we obtain that the covariance matrix
$\Sigma$ has the form 4 by substituting $c=\widetilde{C}_{K,n}/2C_{K,n}$. We
note that $C_{K,n}$ is strictly positive by the property of $K$. Hence, by
Proposition 3, Assumption 2 is satisfied. ∎

## References

  * [1] Jason Abrevaya and Jian Huang.  On the bootstrap of the maximum score estimator.  Econometrica, 73(4):1175–1204, 2005.
  * [2] Robert J Adler and Jonathan E Taylor.  Random Fields and Geometry.  Springer Science & Business Media, 2009.
  * [3] David F Andrews and Frank R Hampel.  Robust Estimates of Location: Survey and Advances.  Princeton University Press, 2015.
  * [4] Miguel A Arcones.  On the argmax of a gaussian process.  Statistics & Probability Letters, 15(5):373–374, 1992.
  * [5] Barry C Arnold, Enrique Castillo, and José María Sarabia.  A multivariate version of stein’s identity with applications to moment calculations and estimation of conditionally specified distributions.  Communications in Statistics. Theory and Methods, 30(12):2517–2542, 2001.
  * [6] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  Concentration Inequalities: A Nonasymptotic Theory of Independence.  Oxford University Press, 2013.
  * [7] Matias D Cattaneo, Michael Jansson, and Kenichi Nagasawa.  Bootstrap-based inference for cube root asymptotics.  Econometrica, 88(5):2203–2219, 2020.
  * [8] Herman Chernoff.  Estimation of the mode.  Annals of the Institute of Statistical Mathematics, 16(1):31–41, 1964.
  * [9] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato.  Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors.  The Annals of Statistics, 41(6):2786–2819, 2013.
  * [10] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato.  Comparison and anti-concentration bounds for maxima of gaussian random vectors.  Probability Theory and Related Fields, 162(1-2):47–70, 2015.
  * [11] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato.  Empirical and multiplier bootstraps for suprema of empirical processes of increasing complexity, and related gaussian couplings.  Stochastic Processes and their Applications, 126(12):3632–3651, 2016.
  * [12] Victor Chernozhukov, Denis Chetverikov, Kengo Kato, et al.  Gaussian approximation of suprema of empirical processes.  The Annals of Statistics, 42(4):1564–1597, 2014.
  * [13] Richard M Dudley.  Uniform Central Limit Theorems.  Cambridge University Press, 2014.
  * [14] Dietmar Ferger.  A continuous mapping theorem for the argmax-functional in the non-unique case.  Statistica Neerlandica, 58(1):83–96, 2004.
  * [15] Robert E Gaunt.  Rates of convergence in normal approximation under moment conditions via new bounds on solutions of the stein equation.  Journal of Theoretical Probability, 29(1):231–247, 2016.
  * [16] Ulf Grenander.  On the theory of mortality measurement: part ii.  Scandinavian Actuarial Journal, 1956(2):125–153, 1956.
  * [17] Piet Groeneboom and Jon A Wellner.  Computing chernoff’s distribution.  Journal of Computational and Graphical Statistics, 10(2):388–400, 2001.
  * [18] Qiyang Han and Kengo Kato.  Berry-esseen bounds for chernoff-type non-standard asymptotics in isotonic regression.  arXiv preprint arXiv:1910.09662, 2019.
  * [19] Jeankyung Kim and David Pollard.  Cube root asymptotics.  The Annals of Statistics, 18(1):191–219, 1990.
  * [20] Michael R Kosorok.  Introduction to Empirical Processes and Semiparametric Inference.  Springer Science & Business Media, 2007.
  * [21] Stephen MS Lee and Puyudi Yang.  Bootstrap confidence regions based on m-estimators under nonstandard conditions.  The Annals of Statistics, 48(1):274–299, 2020.
  * [22] Christian Léger and Brenda MacGibbon.  On the bootstrap in cube root asymptotics.  Canadian Journal of Statistics, 34(1):29–44, 2006.
  * [23] Charles F Manski.  Maximum score estimation of the stochastic utility model of choice.  Journal of Econometrics, 3(3):205–228, 1975.
  * [24] J Pfanzagl.  The berry-esseen bound for minimum contrast estimates.  Metrika, 17(1):82–91, 1971.
  * [25] Johann Pfanzagl.  The accuracy of the normal approximation for estimates of vector parameters.  Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 25(3):171–198, 1973.
  * [26] David Pollard.  Asymptotics for least absolute deviation regression estimators.  Econometric Theory, 7(2):186–199, 1991.
  * [27] Wolfgang Polonik and Qiwei Yao.  Conditional minimum volume predictive regions for stochastic processes.  Journal of the American Statistical Association, 95(450):509–519, 2000.
  * [28] BLS Prakasa Rao.  Estimation of a unimodal density.  Sankhyā: The Indian Journal of Statistics, Series A, pages 23–36, 1969.
  * [29] Peter J Rousseeuw.  Least median of squares regression.  Journal of the American Statistical Association, 79(388):871–880, 1984.
  * [30] Larry Schumaker.  Spline functions: basic theory.  Cambridge University Press, 2007.
  * [31] Emilio Seijo, Bodhisattva Sen, et al.  A continuous mapping theorem for the smallest argmax functional.  Electronic Journal of Statistics, 5:421–439, 2011.
  * [32] Bodhisattva Sen, Moulinath Banerjee, and Michael Woodroofe.  Inconsistency of bootstrap: The grenander estimator.  The Annals of Statistics, 38(4):1953–1977, 2010.
  * [33] Myung Hwan Seo and Taisuke Otsu.  Local m-estimation with discontinuous criterion for dependent and limited observations.  The Annals of Statistics, 46(1):344–369, 2018.
  * [34] Chengchun Shi, Wenbin Lu, and Rui Song.  A massive data framework for m-estimators with cubic-rate.  Journal of the American Statistical Association, 113(524):1698–1709, 2018.
  * [35] Charles Stein.  A bound for the error in the normal approximation to the distribution of a sum of dependent random variables.  In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 2: Probability Theory. The Regents of the University of California, 1972.
  * [36] Ingo Steinwart and Andreas Christmann.  Support Vector Machines.  Springer Science & Business Media, 2008.
  * [37] Aad W Van der Vaart.  Asymptotic Statistics.  Cambridge university press, 2000.
  * [38] Aad W Van Der Vaart and Jon A Wellner.  Weak Convergence and Empirical Processes.  Springer, 1996.
  * [39] Andreas Winkelbauer.  Moments and absolute moments of the normal distribution.  arXiv preprint arXiv:1209.4340, 2012.
  * [40] Fuzhen Zhang.  The Schur Complement and Its Applications, volume 4.  Springer Science & Business Media, 2006.