--- title: "Complete Historical Distinguishability in Two-Agent Delayed Asynchronous Consensus" author: "Guillaume Bolduc" version: "v02" format: "Derived Markdown edition" source_tex_sha256: "5923628cefb1eb3e5a35c73794f83bc0bfe0c17f303d821f2824c4f09dc5ec17" --- # Complete Historical Distinguishability in Two-Agent Delayed Asynchronous Consensus **Author:** Guillaume Bolduc **Version:** v02 **Status:** certified frozen source frame; source-bound mathematical CLEAN STOP > This Markdown edition was mechanically derived from the selected LaTeX source. LaTeX mathematics and any complex layout commands are intentionally retained where a safe Markdown equivalent was not available. The exact source binding is SHA-256 `5923628cefb1eb3e5a35c73794f83bc0bfe0c17f303d821f2824c4f09dc5ec17`. ## Abstract We study a scalar two-agent asynchronous averaging process with bounded discrete communication age. At each primitive action, one agent replaces its current value by a fixed convex combination of its own current value and a delayed value of the other agent, while the other agent holds. A maximum age \(D\) gives an augmented history of dimension \(M=2(D+1)\). Every admissible infinite future that reaches consensus induces a linear functional on that history. Finite-word observability and minimal realization are established switched-system concepts. Here the output family consists of asymptotic endpoints; its static row-space interpretation is elementary and is not claimed as new. The contribution is a protocol-specific rank theorem. For every \(D\ge 0\) and every self-weight \(\theta\in(0,1)\), we construct \(2(D+1)\) admissible period-two futures whose consensus endpoint functionals are linearly independent. The future-functional span is therefore the complete dual of the augmented history space. Consequently, no nontrivial linear historical compression can reproduce the consensus endpoint for every admissible future. The same scalar lower bound holds for continuously differentiable encoders and decoders on a nonempty open set of independently initialized histories. For complete probability rows with \(m\ge2\) objective coordinates, the corresponding intrinsic initialized-history dimension is \(M(m-1)\). These counts do not automatically apply to histories constrained by a preceding lawful execution. Finally, equality of consensus endpoints under every admissible future is equivalent to equality of the complete augmented histories; an affine intervention can therefore achieve schedule-robust restoration only by exactly repairing the full history. Exact rational computations corroborate the witness construction for delays through 12 and six rational self-weights. The result concerns the declared two-agent recurrence. It does not characterize larger graphs, packet availability, nonlinear discontinuous encodings, hardware, or publication priority. \begin{IEEEkeywords}asynchronous consensus, communication delay, historical state, observability, restoration.\end{IEEEkeywords} ## Problem Delayed consensus can agree while retaining information from states that are no longer current. For a fixed future recurrence, the consensus endpoint is one weighted combination of the initialized delay registers. Under changing asynchronous update order and changing read age, the weights can also depend on the future schedule. The resulting question is not whether consensus occurs. The question is whether the family of possible future endpoints can distinguish the complete initialized history. Let the maximum read age be \(D\). At the start of the modeled future, supply independently initialized scalar delay-register histories for two agents. No recurrence constraint is imposed on the supplied negative-time data. They are not asserted to be the image of a preceding execution of the update modes below. The two histories are $$ x_0,x_1,\ldots,x_D, \qquad y_0,y_1,\ldots,y_D, $$ where \(x_s\) and \(y_s\) denote values \(s\) actions before the cut. Stack them as $$ \begin{gathered} z= \begin{bmatrix} x_0&x_1&\cdots&x_D&y_0&y_1&\cdots&y_D \end{bmatrix}^{\!\top},\\ z\in\mathbb R^{M}, \qquad M=2(D+1). \end{gathered} $$ A future schedule \(\sigma\) is chosen independently of these data. It is called convergent here when its augmented products converge to \(\mathbf1\pi_\sigma^{\top}\) for every initialized state, with one normalized row independent of that state. Such a schedule produces a scalar endpoint $$ c_\sigma(z)=\pi_\sigma^{\top}z, $$ for a nonnegative unit-sum row \(\pi_\sigma^{\top}\). Define $$ \Pi_D=\{\pi_\sigma:\sigma\text{ is an admissible convergent future}\} $$ and the **future-functional rank** $$ r_F(D)=\dim\operatorname{span}\Pi_D. $$ A single fixed future has rank one. The issue is how large the span becomes when the future schedule is not fixed at the cut. The principal result is $$ \boxed{r_F(D)=2(D+1).} $$ Thus every augmented historical direction is visible to some admissible future. A controller that must restore the same endpoint under every admissible future cannot generally preserve only a current value, a current mean, or one delay-weighted invariant. In the unrestricted initialized-history model below, exact restoration for all these futures requires equality of the entire augmented history. A restricted initialization or coherent-cut domain can have fewer independent coordinates. This is a narrow theorem. It is not a general theory of historical-state complexity. The supplied literature memo identifies established realization and observability frameworks. The present note makes the concrete asymptotic rank calculation and its conditional restoration consequence; it does not claim a new general framework. ## Position relative to prior work ### Switched-system realization and observability A family of future outputs generated by products of mode matrices is an input-output map of a discrete-time linear switched system. Petreczky, Bako, and van Schuppen give finite-rank realization conditions, characterize minimality through span-reachability and observability, and show that minimal realizations are unique up to isomorphism [citation: r1]. Therefore the following general statement is established system theory rather than a contribution here: \begin{quote}The minimum dimension of a linear state that reproduces all switched future outputs is the dimension of the observable quotient.\end{quote} Reference [citation: r1] treats finite-word input-output behavior and minimality through both span-reachability and observability. It is contextual prior work, not a direct proof dependency for this asymptotic-output family. Corollaries 1--2 below use their own row-space and differential-rank arguments. The protocol-specific claim is that a finite period-two endpoint family separates every independently initialized scalar register direction. Observability has also been studied directly in consensus networks. O'Clery, Yuan, Stan, and Barahona relate consensus observability and coarse graining to external equitable partitions for fixed graph dynamics [citation: r2]. That problem concerns observations of a fixed consensus system. Here the switching schedule itself selects one endpoint functional from a family. ### Order-dependent gossip and limit sets Weighted gossip products can have order-dependent limits. Chen, Belabbas, and Liu introduce holonomy to characterize when a weighted gossip process has an order-independent rank-one limit and characterize the corresponding holonomic matrix families [citation: r3]. Their work also shows that suitable local stochastic matrices can realize prescribed interior consensus weights. Bayram, Belabbas, and Ba\c{s}ar extend the holonomy framework to vector-valued gossip and characterize finite limit structures for noncommuting stochastic products [citation: r4]. Later constructive work designs local stochastic matrices for desired averaging weights [citation: r5]. Those results are close in subject but different in target. We fix the local averaging weight and delay-line mode structure, vary only a small family of admissible schedules and read ages, and ask for the linear span of the resulting endpoint functionals on the complete initialized delayed history. We neither characterize holonomic matrix families nor design matrices for a prescribed weight. ### Consensus with communication delays Communication delays are routinely represented by augmented states. Tsianos and Rabbat show convergence for fixed and bounded time-varying delays and note that a row-stochastic delayed process generally loses arithmetic-average preservation [citation: r6]. Atay and related delay-consensus work show that the consensus value can depend on the past history, not only on the state at time zero [citation: r7]. Recent work by Naderi, Blondin, and Roy derives explicit delay-distribution-dependent consensus values for uniform and nonuniform delays [citation: r8]. The supplied HORTRAME delayed-priority analysis likewise gives an endpoint $$ \mu_\sigma=\pi_\sigma^{\top}Y $$ for a future-dependent nonnegative unit-sum functional and proves convergence under bounded used age, positive weights, and repeated connectivity [citation: r9]. These works establish history dependence or calculate one functional for a specified delay model. They do not, in the sources inspected for this revision, prove that a fixed two-agent delayed asynchronous protocol generates a full-dimensional span of endpoint functionals as the admissible future varies. ### Time-varying stochastic chains Absolute probability sequences generalize stationary left eigenvectors to time-varying stochastic chains. Parasnis, Franceschetti, and Touri establish existence, uniqueness, and uniform positivity under strong aperiodicity and connectivity assumptions [citation: r10]. This provides contextual left-weight machinery, rather than a theorem application to our augmented modes. Their shift rows can have zero diagonal entries and their endpoint rows can have zero coordinates; no uniform-positivity conclusion is imported. The rank is proved directly below. ### Literature-review disposition The supplied memo rejects a generic-framework contribution and retains a protocol-specific question. Its search is reported as targeted rather than exhaustive; it is not a proof of priority. No first-publication claim is made. A later source showing the same full-rank theorem for this mode family would require repositioning or withdrawal. ## Delayed asynchronous averaging model Fix an integer \(D\ge0\) and a self-weight $$ 0<\theta<1, \qquad q=1-\theta. $$ At each primitive action exactly one agent updates. For a selected read age \(r\in\{0,\ldots,D\}\), the two update modes are $$ \mathsf U_{1,r}: \begin{cases} x_0^+=\theta x_0+q y_r,\\ y_0^+=y_0, \end{cases} \tag{1} $$ and $$ \mathsf U_{2,r}: \begin{cases} x_0^+=x_0,\\ y_0^+=\theta y_0+q x_r. \end{cases} \tag{2} $$ Every action shifts the delay registers: $$ x_s^+=x_{s-1}, \qquad y_s^+=y_{s-1}, \qquad 1\le s\le D. \tag{3} $$ Equations (1)--(3) define row-stochastic matrices $$ U_{1,r},U_{2,r}\in\mathbb R^{M\times M}. $$ The model is the bounded-age recurrence itself. It assumes that the selected delayed sample exists and is eligible. It does not prove a packet-delivery, queueing, or incarnation-management protocol. Those are separate causal-service obligations in a network implementation. A future schedule is an infinite word over the modes. This article uses only period-two schedules in which each agent updates once per period. Such schedules satisfy positive self-weight, positive cross-weight, bounded age, and repeated bidirectional influence. **Lemma 1. Consensus for the witness futures** Every period-two future used below converges to consensus. There is a unique nonnegative unit-sum row \(\pi^{\top}\) such that $$ x_0(k),y_0(k)\longrightarrow \pi^{\top}z(0). \tag{4} $$ *Proof* Every augmented mode matrix is row stochastic. In each two-action period both directed influence edges are used with positive weight \(q\), and every current row retains positive self-weight at least \(\min(\theta,q)\). The selected read ages are at most \(D\). Over a block of \(2D+2\) primitive actions, a positive coefficient from a current root can reach the other current row after the required history propagation and can then fill every augmented history layer through the shifts. Hence the corresponding augmented product has a common positive column. Subtracting that common column contracts every scalar coordinate range by a factor strictly below one. Repetition gives consensus of current and history rows. The limiting map is linear and row-stochastic, so it has the form \(\mathbf1\pi^{\top}\) with \(\pi\ge0\) and \(\pi^{\top}\mathbf1=1\). Uniqueness follows from convergence. \(\square\) This is a specialized common-column argument. It is not a new delayed-consensus theorem. ## Future-functional rank For every convergent future \(\sigma\), let \(\pi_\sigma\) be the row in (4). Define $$ \mathcal O_D = \operatorname{span} \{\pi_\sigma^{\top}:\sigma\text{ admissible and convergent}\} \subseteq(\mathbb R^M)^*. \tag{5} $$ Then $$ r_F(D)=\dim\mathcal O_D. \tag{6} $$ For the proof, introduce three schedule families. Composition is written in action order from right to left. For \(0\le b\le D\), let $$ P_{A_b}=U_{2,b}U_{1,0}, \tag{7} $$ corresponding to agent 1 reading the current value of agent 2, followed by agent 2 reading age \(b\) from agent 1. For \(1\le a\le D\), let $$ P_{B_a}=U_{2,0}U_{1,a}. \tag{8} $$ Finally, for \(D\ge1\), let $$ P_{C_D}=U_{1,0}U_{2,D}. \tag{9} $$ Write their normalized stationary rows as $$ \pi_{A_b}^{\top}, \qquad \pi_{B_a}^{\top}, \qquad \pi_{C_D}^{\top}. $$ Each is an endpoint functional by Lemma 1. ## Stationary-balance structure Write a generic stationary row in block form $$ \pi^{\top} = (\alpha_0,\ldots,\alpha_D, \beta_0,\ldots,\beta_D). \tag{10} $$ All indices outside \(0,\ldots,D\) are assigned coefficient zero. **Lemma 2. The \(A_b\) family** For \(A_0\), $$ \pi_{A_0}^{\top} = \left( \frac{\theta}{1+\theta},0,\ldots,0, \frac{1}{1+\theta},0,\ldots,0 \right). \tag{11} $$ For \(A_1\), $$ \pi_{A_1}^{\top} = \left( \frac12,0,\ldots,0, \frac12,0,\ldots,0 \right). \tag{12} $$ For every \(2\le b\le D\), the row \(\pi_{A_b}\) has the following properties: 1. \(\beta_s=0\) for every \(s\ge1\); 2. \(\alpha_s=0\) for every \(s\ge b\); 3. \(\alpha_{b-1}>0\). *Proof* For \(b=0\), one period acts on current values by $$ \begin{bmatrix}x_0^+\\y_0^+\end{bmatrix} = \begin{bmatrix} \theta&q\\ q\theta&\theta+q^2 \end{bmatrix} \begin{bmatrix}x_0\\y_0\end{bmatrix}, $$ while all history registers are transient. Solving the two-state stationary equation gives (11). Now take \(b\ge1\). Expanding \(\pi^{\top}P_{A_b}=\pi^{\top}\) gives, for \(s\ge1\), $$ \beta_s=\beta_{s+2}. \tag{13} $$ The boundary condition beyond delay \(D\) therefore gives $$ \beta_s=0, \qquad s\ge1. \tag{14} $$ The current \(y\)-coefficient equation gives $$ \beta_0=\alpha_0+\alpha_1. \tag{15} $$ The \(x\)-coefficients satisfy $$ \alpha_s = \theta\beta_0\mathbf1_{\{s=0\}} +q\beta_0\mathbf1_{\{s=b-1\}} +\alpha_{s+2}. \tag{16} $$ For \(b=1\), both forcing terms in (16) occur at \(s=0\), giving \(\alpha_0=\beta_0\), \(\alpha_s=0\) for \(s\ge1\), and hence (12) by normalization. For \(b\ge2\), backward evaluation of (16) gives \(\alpha_s=0\) for \(s\ge b\) and $$ \alpha_{b-1}=q\beta_0. \tag{17} $$ If \(\beta_0=0\), (14) and backward evaluation of (16) make every coefficient zero, contradicting normalization. Thus \(\beta_0>0\). Since \(q>0\), (17) is strictly positive. \(\square\) The recurrence also gives closed forms for every coefficient, but only the support and the highest nonzero history layer are needed below. **Lemma 3. The \(B_a\) and \(C_D\) families** For every \(1\le a\le D\), the row \(\pi_{B_a}\) satisfies 1. \(\alpha_s=0\) for every \(s\ge1\); 2. \(\beta_s=0\) for every \(s>a\); 3. \(\beta_a>0\). The row \(\pi_{C_D}\) satisfies 1. \(\beta_s=0\) for every \(s\ge1\); 2. \(\alpha_D>0\). *Proof* For \(B_a\), stationarity gives $$ \alpha_s=\alpha_{s+2}, \qquad s\ge1, \tag{18} $$ so every \(\alpha_s\) with \(s\ge1\) vanishes by the upper boundary. The current equation gives $$ \alpha_0=\theta\beta_0. \tag{19} $$ The \(y\)-coefficients obey $$ \beta_s = q\beta_0\mathbf1_{\{s=a\}} +(\theta\beta_0+\beta_1)\mathbf1_{\{s=0\}} +\beta_{s+2}. \tag{20} $$ Thus \(\beta_s=0\) for \(s>a\), while $$ \beta_a=q\beta_0>0. \tag{21} $$ If \(\beta_0=0\), (18)--(20) make every coefficient zero, contradicting normalization. Hence the normalized current mass is positive, and \(q>0\) gives the last inequality. The schedule \(C_D\) is obtained from \(B_D\) by exchanging the two agent labels. Its stationary row therefore has no positive-age \(y\)-coefficients and has a strictly positive coefficient on \(x_D\). \(\square\) ## Full future-functional rank **Theorem 1. Complete historical distinguishability** For every integer \(D\ge0\) and every \(\theta\in(0,1)\), $$ \boxed{r_F(D)=2(D+1).} \tag{22} $$ For \(D\ge1\), the following \(2D+2\) period-two futures already form a basis of the augmented history dual: $$ \{A_0,A_1,\ldots,A_D, B_1,\ldots,B_D, C_D\}. \tag{23} $$ *Proof* The rank cannot exceed \(M=2D+2\). Assume first that \(D\ge1\). The rows \(\pi_{A_0}\) and \(\pi_{A_1}\) are linearly independent because their current-coordinate ratios are respectively $$ \theta:1 \qquad\text{and}\qquad 1:1, $$ and \(0<\theta<1\). For \(b=2,\ldots,D\), Lemma 2 shows that \(\pi_{A_b}\) has a nonzero coefficient on \(x_{b-1}\), while every previous row $$ \pi_{A_0},\ldots,\pi_{A_{b-1}} $$ has zero coefficient on that coordinate and on every later \(x\)-history coordinate. Therefore each \(\pi_{A_b}\) increases the rank by one. The \(D+1\) rows $$ \pi_{A_0},\ldots,\pi_{A_D} $$ are independent. Every \(A_b\) row has zero coefficient on every positive-age \(y\)-coordinate. For \(a=1,\ldots,D\), Lemma 3 shows that \(\pi_{B_a}\) has a nonzero coefficient on \(y_a\), while every earlier \(B\)-row has zero coefficient on that coordinate and on every later \(y\)-history coordinate. Hence $$ \pi_{B_1},\ldots,\pi_{B_D} $$ add \(D\) further independent directions. The span constructed so far contains no \(x_D\) component: the \(A_b\) family reaches only through \(x_{D-1}\), and the \(B_a\) family has no positive-age \(x\)-coefficients. Lemma 3 gives $$ (\pi_{C_D})_{x_D}>0. $$ Therefore \(\pi_{C_D}\) supplies the final independent direction. The witness rows have rank $$ (D+1)+D+1=2D+2=M. $$ For \(D=0\), use the two opposite update orders $$ U_{2,0}U_{1,0} \qquad\text{and}\qquad U_{1,0}U_{2,0}. $$ Their endpoint rows are $$ \left(\frac{\theta}{1+\theta},\frac1{1+\theta}\right), \qquad \left(\frac1{1+\theta},\frac{\theta}{1+\theta}\right), $$ which are independent because \(\theta\ne1\). Thus \(r_F(0)=2\). \(\square\) ### Interpretation Each individual future compresses the augmented history to one scalar endpoint. The family of admissible futures does not. Different schedules act as different linear probes, and the explicit period-two family separates every historical direction. The result is stronger than the claim that delay affects the endpoint. It says that, for this protocol, no nonzero perturbation of the initialized delayed history is invisible to every admissible future. ## Historical representation lower bounds The next statements are standard consequences of full observability. They are included because they state the restoration meaning of Theorem 1. **Corollary 1. Minimum linear summary dimension** Let $$ C:\mathbb R^M\to\mathbb R^r $$ be a linear historical encoder. Suppose that for every admissible future \(\sigma\) there is a linear decoder \(d_\sigma\) satisfying $$ d_\sigma(Cz)=\pi_\sigma^{\top}z \qquad \text{for every }z\in\mathbb R^M. \tag{24} $$ Then $$ r\ge M=2(D+1). \tag{25} $$ The identity encoder attains equality. *Proof* Equation (24) implies $$ \operatorname{span}\Pi_D \subseteq \operatorname{rowspan}C. $$ Theorem 1 gives \(\dim\operatorname{span}\Pi_D=M\), while \(\dim\operatorname{rowspan}C\le r\). \(\square\) This is a concrete application of switched-system observability, not a new general minimal-realization theorem. **Corollary 2. Continuously differentiable encoders** Let \(\mathcal U\subseteq\mathbb R^M\) be nonempty and open. Suppose a \(C^1\) encoder $$ e:\mathcal U\to\mathbb R^r $$ and \(C^1\) decoders \(d_1,\ldots,d_M\), defined on an open neighborhood of \(e(\mathcal U)\), exactly reproduce the endpoint values for the \(M\) witness futures in Theorem 1. Then $$ r\ge M. \tag{26} $$ *Proof* Stack the witness rows into the nonsingular matrix $$ L= \begin{bmatrix} \pi_1^{\top}\\ \vdots\\ \pi_M^{\top} \end{bmatrix}. $$ Define \(d=(d_1,\ldots,d_M)\). Exact reproduction gives $$ d(e(z))=Lz. $$ Differentiation at any \(z\in\mathcal U\) yields $$ Dd(e(z))De(z)=L. $$ Therefore $$ M=\operatorname{rank}L \le\operatorname{rank}De(z) \le r. $$ \(\square\) The claim does not cover discontinuous exact-real encodings that interleave infinitely many digits into one scalar. Any finite-bit or regular representation requires its own declared model. **Corollary 3. Independently initialized positive probability rows** Let each of the \(M\) initialized rows independently belong to \(\Delta_m^+\), with \(m\ge2\). A chosen scalar coordinate has all \(M\) local augmented directions available, so Theorem 1 separates them. If a \(C^1\) encoder and \(C^1\) witness decoders reproduce the **complete** endpoint probability row on a nonempty relatively open subset of this product-simplex domain, the required encoder dimension is at least \(M(m-1)\). Storing the first \(m-1\) coordinates of every row attains that dimension with the public normalization constant. *Proof* At any positive base table, vary one objective coordinate in each row and compensate in a second coordinate. A sufficiently small open box of these \(M\) changes preserves positivity and normalization. This establishes the scalar slice assertion without asserting trajectory reachability. For the complete-row assertion, use the first \(m-1\) coordinates as a chart of the product-simplex interior. The chart is open in \(\mathbb R^{M(m-1)}\). Stacking the first \(m-1\) output coordinates for the \(M\) witness schedules gives a linear map with matrix \(L\otimes I_{m-1}\), up to a fixed coordinate ordering. Its rank is \(M(m-1)\). The chain-rule argument of Corollary 2 therefore gives the claimed lower bound. Coordinate storage reproduces those coordinates and the last follows from unit sum. \(\square\) The row data are freely initialized. Positivity and normalization alone do not prove that every table is generated by a preceding sequence of (1)--(3). On a restricted coherent-cut domain, representation dimension must instead be assessed on its actual degrees of freedom. Equality of all future scalar endpoints still distinguishes any two different states in that restricted domain, because Theorem 1's ambient kernel is zero. ## Schedule-robust restoration Let \(z_{\rm ref}\in\mathbb R^M\) be a reference history. An intervention parameter \(u\in\mathbb R^p\) produces $$ z(u)=z_0+Bu, \qquad B\in\mathbb R^{M\times p}. \tag{27} $$ Call the intervention **schedule-robustly restoring** when $$ \pi_\sigma^{\top}z(u) = \pi_\sigma^{\top}z_{\rm ref} \qquad \text{for every admissible future }\sigma. \tag{28} $$ **Theorem 2. Full-history restoration criterion** Under the model of Section III, (28) holds if and only if $$ \boxed{z(u)=z_{\rm ref}.} \tag{29} $$ For the affine intervention (27), schedule-robust restoration is therefore equivalent to $$ \boxed{Bu=z_{\rm ref}-z_0.} \tag{30} $$ *Proof* The reverse implication is immediate. For the forward implication, apply (28) to the \(M\) witness futures in Theorem 1. Their rows form a nonsingular matrix \(L\), so $$ L(z(u)-z_{\rm ref})=0 $$ implies \(z(u)-z_{\rm ref}=0\). Substituting (27) gives (30). \(\square\) **Corollary 4. Generic intervention obstruction** Let \(r_B=\operatorname{rank}B\). The discrepancies that can be repaired schedule-robustly form the subspace $$ \operatorname{im}B $$ of dimension \(r_B\). When \(r_B