Asymptotic Subspace Consensus in Dynamic Networks

Függer, Matthias; Nowak, Thomas

doi:10.4230/LIPIcs.SAND.2026.10

Asymptotic Subspace Consensus in Dynamic Networks

Matthias Függer

Université Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, Gif-sur-Yvette, France Thomas Nowak

Université Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, Gif-sur-Yvette, France
Institut Universitaire de France, Paris, France

Abstract

We introduce the problem of asymptotic subspace consensus, which requires the outputs of processes to converge onto a common subspace while remaining inside the convex hull of initial vectors. This is a relaxation of asymptotic consensus in which outputs have to converge to a single point, i.e., a zero-dimensional affine subspace.

We give a complete characterization of the solvability of asymptotic subspace consensus in oblivious message adversaries. In particular, we show that a large class of algorithms used for asymptotic consensus gracefully degrades to asymptotic subspace consensus in distributed systems with weaker assumptions on the communication network. We also present bounds on the rate by which a lower-than-initial dimension is reached.

Keywords and phrases:

Averaging, dynamic networks, consensus, higher dimensional

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Distributed computing models

Related Version:

Full Version: https://arxiv.org/abs/2602.19121

Supplementary Material:

Software (Source Code): https://github.com/BioDisCo/roots [13]
archived at

swh:1:dir:51a26eb1029c41b9995702cdc0041af39802d85c

Acknowledgements:

We thank Emmanuel Godard and Eloi Perdereau for introducing us to the question of possible generalizations of the asymptotic consensus problem.

Funding:

The work was supported by the French National Research Agency (ANR) projects DREAMY (ANR-21-CE48-0003) and COSTXPRESS (ANR-23-CE45-0013), as well as the SAIF project, funded by the “France 2030” government investment plan managed by ANR, under the reference ANR-23-PEIA-0006.

DOI:

10.4230/LIPIcs.SAND.2026.10

Event:

5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Editors:

George B. Mertzios and Andréa W. Richa

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

When computation is distributed across several processes, an often encountered problem is the one of reaching consensus on a common property among the processes. Consensus problems have thus been extensively studied in many variants. Examples include agreement on a discrete state like a transaction status [20, 24], on continuous values such as time [18, 25, 26, 11, 19], and on multidimensional properties like three-dimensional coordinates in space [4, 22, 21, 14].

This work falls into the latter category of agreement on multidimensional continuous values. We assume a round-wise computational model in which processes communicate and update their state in rounds. In each round a process sends messages, receives messages, and updates its local state according to the previous state and received messages. The dynamics of the underlying communication network are modeled by a set of communication graphs that may change arbitrarily in each round. So-called oblivious message adversaries have been widely used in distributed computing to model highly dynamic networks [23, 8, 1, 9].

In this model the well-studied problem of asymptotic consensus is formulated as: Each process $i$ starts with an initial input $x_{i}(0)\in\mathbb{R}^{d}$ , for some dimension $d\geqslant 1$ . An algorithm solves asymptotic consensus if all process outputs $x_{i}(t)$ converge to a common value (Agreement property) that lies within the convex hull of initial values (Validity property). Closely related to this problem is the problem of $\varepsilon$ -consensus, or approximate consensus, where processes terminate and (Agreement) is replaced with the requirement that values in the final round are within distance $\varepsilon>0$ .

Charron-Bost, Függer, and Nowak [5] gave a characterization of the oblivious message adversaries in which one-dimensional asymptotic consensus is solvable. The authors showed that simple averaging algorithms with mild conditions on their weights solve the problem whenever it is solvable and that the latter is the case exactly in rooted oblivious message adversaries, i.e., where each communication graph has at least one process (the root of this graph) that reaches all other processes. Subsequent work showed that alternating flooding and averaging considerably speeds up convergence [6]. Algorithms based on this scheme were shown to be asymptotically optimal by Függer, Nowak, and Schwarz [15].

Averaging algorithms naturally generalize to dimensions $d>1$ , with the same characterization of solvability for asymptotic and $\varepsilon$ -consensus, and the main challenge being high convergence rates despite large dimensions [7, 14]. Multidimensional $\varepsilon$ -consensus has also been studied in the context of adversarial faults and asynchrony by Mendes, Herlihy, Vaidya, and Garg [21] with a time to reach $\varepsilon$ -consensus that depends linearly on $d$ . Via a reduction to dynamic networks, Függer and Nowak [14] showed that this dependency can be dropped, with the convergence rate of asymptotic consensus and the termination time in $\varepsilon$ -consensus being independent of $d$ for certain averaging algorithms. Approximate consensus was also investigated in non-synchronous settings [2, 17].

In this work we investigate the behavior of averaging algorithms in weaker than rooted oblivious message adversaries, where asymptotic consensus is not necessarily solvable. This is motivated by an understanding of how averaging algorithms degrade in non-rooted oblivious message adversaries, and by the hypothesis that some applications may not require convergence to a single value.

Results and outline

We define the problem of $d$ -to- $s$ -dimensional asymptotic subspace consensus, with $d>s$ , by weakening (Agreement) into (Subspace Agreement), requiring that the limits of the processes outputs are within an $s$ -dimensional subspace of the $d$ -dimensional space. We show that $d$ -to- $s$ -dimensional asymptotic subspace consensus is solvable if and only if the oblivious message adversary is $(s+1)$ -rooted, i.e., in each graph, each process is reachable from at least one of a set of $s+1$ roots. In case it is solvable, averaging algorithms solve it under weak assumptions on their weights. In particular, this is fulfilled when choosing equal weights (Figure 1a). Figures 1b–d show simulations of averaging in an initially 3-dimensional space that are seen to converge onto 0-dimensional in 1-rooted (b), 1-dimensional in 2-rooted (c), and 2-dimensional subspaces in 3-rooted oblivious message adversaries (d). We prove that this in the general case as outlined:

We introduce the model and the problem in Sections 2 and 3, respectively. Our analysis builds upon a reduction from $k$ -rooted oblivious message adversaries to $k$ -broadcastable adversaries, where each process directly receives a message from one of $k$ processes (called the broadcasting set). Asymptotically optimal bounds for the complexity of this reduction have been proven by El-Hayek, Henzinger, and Schmid [12].

Section 3 also establishes a lower bound for the message adversaries in which the problem of asymptotic subspace consensus can be solved. Section 4 describes a class of algorithms that allow to solve asymptotic subspace consensus, namely averaging algorithms. In Section 5 we prove our two main results: In Section 5.2, a rate at which certain averaging algorithms contract to a space that is of lower dimension than the space of the initial values. The proof is by showing that the volume that contains the process outputs converges to 0. Inspired by the symmetrization of Charron-Bost, Függer, and Nowak [7], we use a Steiner-type symmetrization of the convex hull of the process outputs. Most importantly, this symmetrization preserves volumes of cuts along the first axis and guarantees concavity of the ball-radius function along the first axis. We then establish a lower bound on the volume contraction between successive rounds.

Section 5.3 presents a complete characterization of oblivious message adversaries with respect to the achievable reduction in dimensionality. The proof is based on an observation shown in Figures 1e at the example of $2$ -rooted message adversaries. Tracking the dynamics of the affine subspace spanned by the outputs of two processes that are in the broadcasting set, one observes convergence of this subspace and attraction of the other process outputs to this space. Again, we show that this holds in the general case.

We conclude in Section 6.

Some definitions and results have been formalized in the Lean 4 proof assistant [10] using the Mathlib library. Results marked with have machine-checked proofs; definitions and statements marked with have been formalized without a complete proof. The Lean formalizations and proofs were generated with the assistance of Claude Opus 4.6 and GPT-5.3-Codex. These formalizations serve as supplementary information and are not meant as replacements for the natural-language proofs in this paper. Clicking a badge links to the corresponding Lean source code.

Several proofs are not given there and are instead available in the full version of the paper.

Figure 1: Averaging algorithm running in dynamic networks. a Distributed system with

5

nodes, executing an averaging algorithm in

\mathbb{R}^{3}

. Nodes start with initial values in

\mathbb{R}^{3}

and average values received within the round’s communication graph (

2

-rooted graphs shown). b–d Execution of the equal neighbor algorithm in

\mathbb{R}^{3}

for

10

rounds. Initial values (blue) and round-10 values (black) shown. b In a

1

-rooted oblivious message adversary, convergence onto a single point (black). c In a

2

-rooted oblivious message adversary, convergence onto a line (black) d In a

3

-rooted oblivious message adversary, convergence onto a plane (black). Animated (Movies S1, S2, S3) and interactive (Documents S1, S2, S3) versions of b–d are provided as supplementary material. e Simulation of averaging algorithm within an oblivious message adversary with

2

-broadcastable communication graphs (broadcasting set marked in red). Initial values (

t=0

) and outputs until

t=4

are shown (black). The linear subspace spanned by the processes in the current round’s broadcasting set is shown (dashed red). Its polar coordinates (

\varphi

and

\theta

) are seen to converge. An animated execution oscillating on a

1

-dimensional subspace is provided as Movie S4 and Document S4.

2 Computational Model

We write $\mathbb{N}=\{1,2,\dots\}$ and $\mathbb{N}_{0}=\mathbb{N}\cup\{0\}$ . Further, $[n]=\{1,\dots,n\}$ . For directed graphs $G_{1}=([n],E_{1})$ and $G_{2}=([n],E_{2})$ , we write $G_{1}\circ G_{2}$ for the product graph $G=([n],E)$ with $(i,j)\in E$ if and only if there exists a $u\in[n]$ such that $(i,u)\in E_{1}$ and $(u,j)\in E_{2}$ .

We assume a system of $n>1$ processes that communicate via a synchronous message-passing network. In each round, processes update their state deterministically based on their local state and the messages they receive. Part of their local state is an output, with the output of process $i\in[n]$ in round $t\geqslant 0$ denoted as $x_{i}(t)$ . In this work we assume that a process output is within some $\mathbb{R}^{d}$ .

Network links are dynamic, akin to message adversaries [1] or the Heard-Of model [8]. That is, every process $i\in[n]$ sends a message in every round $t\in\mathbb{N}$ , then receives the messages from all incoming neighbors $\operatorname{In}_{i}(t)$ in the (directed) round- $t$ communication graph $G_{t}=([n],E_{t})$ , and updates its local state as a function of its previous state and the received messages. Every process receives its own message, i.e., $(i,i)\in G_{t}$ for all $i\in[n]$ . The execution of a deterministic algorithm is uniquely determined by the initial states and the sequence of communication graphs. Although the model is formally synchronous, it has been shown to capture classical round-based asynchronous [8] and even non-benign [3, 21] models.

Message adversaries

The dynamics of communication links is described by message adversaries. In this work we focus on dynamic networks that can switch arbitrarily between communication graphs from a so-called oblivious message adversary $\mathcal{G}$ , which is a non-empty set of communication graphs. We say an algorithm solves a problem in $\mathcal{G}$ if it satisfies its specification in all executions in which all communication graphs are chosen from $\mathcal{G}$ .

For many non-trivial problems, there is no algorithm that solves the problem in an arbitrary $\mathcal{G}$ . For example, Charron-Bost, Függer, and Nowak [5] have shown that asymptotic consensus, i.e., 1-to-0-dimensional asymptotic subspace consensus, is solvable in precisely those $\mathcal{G}$ that contain only rooted graphs. The following definitions are natural generalizations of this concept.

A communication graph $G$ is $k$ -rooted if there exists a set $M\subseteq[n]$ of at most $k$ processes such that every process in $[n]$ is reachable from $M$ in $G$ . In this case, we call $M$ a root set of $G$ . An oblivious message adversary is $k$ -rooted if all its communication graphs are.

Likewise, graphs that contain a star play a central role in consensus-type problems [8]. Generalizing such graphs, we define: A communication graph $G$ is $k$ -broadcastable if there exists a set $M\subseteq[n]$ of at most $k$ processes such that every process in $[n]$ has an incoming edge from at least one process in $M$ in $G$ . In this case, we call $M$ a broadcasting set of $G$ . Every $k$ -broadcastable communication graph is $k$ -rooted, but the converse is not true. An oblivious message adversary is $k$ -broadcastable if all its communication graphs are.

We next discuss links between these two classes of graphs.

From Rooted to Broadcastable Graphs

Relaying messages over multiple rounds with communication graphs $G_{1}$ , …, $G_{t}$ results in reception of the message according to the product graph $G=G_{1}\circ\cdots\circ G_{t}$ in round $t$ . This fact can be used in reductions from one adversary to another by simulating a round with communication graph $G$ from rounds with graphs $G_{1}$ , …, $G_{t}$ .

Charron-Bost, Függer, and Nowak [5] showed a reduction from any sequence of $n-1$ 1-rooted communication graphs to so-called non-split graphs, of which any sequence of $O(\log\log n)$ graphs results in a 1-broadcastable graph [16], i.e., graphs that contain a star. The resulting bound of $O(n\log\log n)$ rounds from 1-rooted to 1-broadcastable was later improved by El-Hayek, Henzinger, and Schmid [12] to $\lceil(1+\sqrt{2}n)-1\rceil$ graphs.

For the more general $k$ -broadcastable graphs, one can show that from $k$ -rooted communication graphs, one also obtains $k$ -broadcastable graphs in a bounded number of rounds. A short argument for a polynomial bound is as follows:

Let $t\geqslant n^{k+1}$ and let $G_{1},\dots,G_{t}$ be $k$ -rooted. By the pigeonhole principle, there exists a subsequence $G_{1}^{\prime},\dots,G_{s}^{\prime}$ of at least $s\geqslant n^{k+1}/\binom{n}{k}\geqslant n^{k+1}/n^{k}=n$ communication graphs in which $M$ is a root set. By considering the influence sets $S_{i}(r)=\big\{j\in[n]\mid(i,j)\in E(G_{1}^{\prime}\circ\cdots\circ G_{r}^{% \prime})\big\}$ for every $i\in M$ and $S(r)=\bigcup_{i\in M}S_{i}(r)$ , one observes that $S(r)$ strictly grows until it covers the set $[n]$ of all processes. Thus, since $\lvert S(0)\rvert\leqslant k$ and $s\geqslant n$ , influence set $S(s)$ covers $[n]$ . In particular this means that $M$ is a broadcasting set in the product graph $G=G_{1}\circ\cdots\circ G_{t}$ .

A more involved analysis by El-Hayek, Henzinger, and Schmid [12] shows that indeed a bound linear in $n$ , and independent of $k$ , holds.

Theorem 1 ([12, Theorem 32]).

Any product of at least $\frac{\pi^{2}+6}{6}n+1$ communication graphs that are $k$ -rooted is $k$ -broadcastable.

3 Asymptotic Subspace Consensus

We start with basic geometric notations. For a set $A\subseteq\mathbb{R}^{d}$ , we denote by $\bar{A}$ the topological closure of $A$ . For any non-empty finite set $X\subseteq\mathbb{R}^{d}$ , denote by $\operatorname{poly}(X)$ the polyhedron generated by $X$ , i.e., its convex hull. For any (Lebesgue) measurable set $A\subseteq\mathbb{R}^{d}$ , denote its volume in $\mathbb{R}^{d}$ by $\operatorname{vol}_{d}(A)$ , or simply $\operatorname{vol}(A)$ if the dimension is clear from the context. We write $\lVert z\rVert=\sqrt{\sum_{k=1}^{d}z_{k}^{2}}$ for the Euclidean norm of any $z\in\mathbb{R}^{d}$ . For sets $A,B\subseteq\mathbb{R}^{d}$ , denote by $\operatorname{dist}(A,B)=\inf_{a\in A,b\in B}\lVert a-b\rVert$ their Euclidean distance. We note that $\operatorname{dist}$ is not a metric; it does not satisfy the triangle inequality and $\operatorname{dist}(A,B)=0$ does not necessarily imply $A=B$ .

We say that a sequence of vectors $x(t)\in\mathbb{R}^{d}$ , $t\in\mathbb{N}$ , converges onto a set $X\subseteq\mathbb{R}^{d}$ if $\displaystyle\lim_{t\to\infty}\operatorname{dist}(x(t),X)=0$ . Equipped with this, we are now in the position to state the asymptotic subspace consensus problem:

In the $d$ -to- $s$ -dimensional asymptotic subspace consensus problem, with $d>s$ , every process $i\in[n]$ starts with an initial vector $x_{i}(0)\in\mathbb{R}^{d}$ and outputs a vector $x_{i}(t)\in\mathbb{R}^{d}$ in every round $t\in\mathbb{N}$ such that in every execution:

(Subspace Agreement): There exists an affine subspace $E\subseteq\mathbb{R}^{d}$ of dimension $s$ , such that all sequences $\big(x_{i}(t)\big)_{t\geqslant 0}$ converge onto $E$ .
(Validity): All sequences $\big(x_{i}(t)\big)_{t\geqslant 0}$ converge onto the convex hull of the set of initial vectors.

Asymptotic consensus on scalar inputs is a special case with $d=1$ and $s=0$ .

3.1 Lower bound for dimension reduction

We first show a lower bound on the attainable dimensionality reduction in asymptotic subspace consensus in terms of the sizes of the root sets of oblivious message adversaries. The proof is a generalization of the impossibility of asymptotic consensus in non-rooted oblivious message adversaries [5]. It does not rely on the dynamics of the communication network and requires a single static communication graph only, where a sufficiently large number of processes are isolated and remain on their initial values.

Theorem 2 ().

For $d>s\geqslant 0$ , the $d$ -to- $s$ -dimensional asymptotic subspace consensus problem is unsolvable in oblivious message adversaries that are not $(s+1)$ -rooted.

4 Averaging Algorithms

A deceptively simple class of algorithms are averaging algorithms. An averaging algorithm keeps only its current vector $x_{i}(t)$ as its state, which it sends in every round. After having received the vectors of other processes, it updates its vectors to a weighted average of the received vectors, see Algorithm 1. In concordance with the term averaging, the weights $w_{ij}(t)$ are assumed to be non-negative and $\sum_{j\in[n]}w_{ij}(t)=1$ . Averaging algorithms differ in choices of weights. Maybe the most natural averaging algorithm is the equal neighbor algorithm, which assigns the same weight to all received vectors.

Algorithm 1 Averaging algorithm for process

i

.

For ease of notation, we set $w_{ij}(t)=0$ if $j\not\in\operatorname{In}_{i}(t)$ , allowing us to write the update step as $x_{i}(t)=\sum_{j\in[n]}w_{ij}(t)x_{j}(t-1)$ .

Following Charron-Bost, Függer, and Nowak [6], we call an averaging algorithm $\alpha$ -safe if it guarantees a minimum positive weight $w_{ij}(t)\geqslant\alpha>0$ for messages it receives, i.e., from some $j\in\operatorname{In}_{i}(t)$ . For example, the equal neighbor algorithm is $1/n$ -safe.

We next define a property for averaging algorithms executed in $k$ -broadcastable oblivious message adversaries for some $k\geqslant 1$ . The property will be central in quantifying the influence a broadcasting set has on the other processes.

Definition 3 (Minimum broadcasting weight).

Let round $t\geqslant 1$ , graph $G_{t}$ be $k$ -broadcastable for some $k\geqslant 1$ , and $M(t)$ be the broadcasting set in $G_{t}$ . For an averaging algorithm, an update step $x_{i}(t)=\sum_{j\in[n]}w_{ij}(t)x_{j}(t-1)$ has minimum broadcasting weight $\alpha$ if $\sum_{j\in M(t)}w_{ij}(t)\geqslant\alpha$ . An averaging algorithm has minimum broadcasting weight $\alpha$ if all update steps do.

Executed in a $k$ -broadcastable oblivious message adversary, an averaging algorithm that is $\alpha$ -safe has minimum broadcasting weight $\alpha$ , but not necessarily vice versa.

5 Analysis

We start the analysis with some notation. Denote by $X(t)$ the set $\{x_{i}(t)\mid i\in[n]\}$ of vectors in round $t$ and by $P(t)=\operatorname{poly}(X(t))$ the generated polyhedron. For a set $A\subseteq[n]$ , we abbreviate $X_{A}(t)=\{x_{i}(t)\mid i\in A\}$ as well as $P_{A}(t)=\operatorname{poly}(X_{A}(t))$ .

In the following Section 5.1 we establish a lower bound on the attraction a broadcasting set has on the other processes.

5.1 Distance to Hyperplane

The following is a formula for the distance of a point to a half-space.

Lemma 4 ().

Let point $q\in\mathbb{R}^{d}$ and normal vector $v\in\mathbb{R}^{d}\setminus\{0\}$ define the half-space $H=\{h\in\mathbb{R}^{d}\mid\langle h-q,v\rangle<0\}$ . Then $\operatorname{dist}(\{z\},H)=\langle z-q,v\rangle/\lVert v\rVert$ for all points $z\in\mathbb{R}^{d}\setminus H$ .

For any averaging algorithm, processes only update their output to a value within the convex hull, that is, the polyhedron, of received values. Thus any open half-space $H$ that does not contain points in round $t\geqslant 0$ will not contain points in round $t+1$ . In fact one can say more for executions in oblivious message adversaries that are $k$ -broadcastable, for some $k\geqslant 1$ : processes update their outputs to values that have a minimum distance to such empty half-spaces. This is due to them being attracted by the values of the broadcasting set. The following lemma establishes a lower bound on this distance (Figure 2a).

Lemma 5 ().

Consider an averaging algorithm executed in some $k$ -broadcastable oblivious message adversary with minimum broadcasting weight $\alpha>0$ and fix a round $t\geqslant 1$ . Let $H\subseteq\mathbb{R}^{d}$ be an open half-space such that $X(t-1)\cap H=\emptyset$ . Then $\operatorname{dist}(X(t),H)\geqslant\alpha\operatorname{dist}(P_{M(t)}(t-1),H)$ .

5.2 Convergence to Zero Volume

As a first main result, we show that being $d$ -broadcastable is enough for a message adversary to reduce the dimensionality of process values in $\mathbb{R}^{d}$ . We also establish a rate for the contraction to a lower dimension.

Theorem 6.

Let dimension $d\geqslant 1$ . Every averaging algorithm with minimum broadcasting weight $\alpha>0$ solves $d$ -to- $(d-1)$ -dimensional asymptotic subspace consensus in a $d$ -broadcastable oblivious message adversary. Moreover, we have $\operatorname{vol}(P(t))\leqslant\varepsilon$ if $t\geqslant\alpha^{-d}\log\frac{\operatorname{vol}(P(0))}{\varepsilon}$ .

The remainder of the section is devoted to the proof of the theorem: we show that the $d$ -dimensional volume containing the process values converges to $0$ . It follows that the process values lie within a subspace of lower dimension. The proof also establishes a contraction rate towards zero volume. An outline of the proof strategy is given in Figure 2.

We introduce notation for certain symmetric bodies. Let $r:\mathbb{R}\to\mathbb{R}_{+}$ be a measurable function. Then $\operatorname{Sym}(r)\in\mathbb{R}^{d}$ is defined as the (full) body obtained by rotating function $r$ around the first coordinate axis. Formally, we define: For a first-axis value $\xi\in\mathbb{R}$ , write $H_{\xi}$ for the $(d-1)$ -dimensional hyperplane defined by normal vector $(1,0,\dots,0)$ and point $(\xi,0,\dots,0)$ . Let $B_{\xi}(\rho)\subseteq H_{\xi}$ be the $(d-1)$ -dimensional ball with center $(\xi,0,\dots,0)$ and radius $\rho$ . Then $\operatorname{Sym}(r)=\bigcup_{\xi\in\mathbb{R}}B_{\xi}(r(\xi))$ .

Lemma 9 states lower and upper bounds on the volumes of a partitioning of such bodies for concave functions $r$ . We start with some technical results, Lemmas 7 and 8, (Figure 2b–c), which are affine upper and lower bounds to one-dimensional concave functions. We will later use these to bound the radius function $r$ .

Figure 2: Proof strategy for Theorem 6. a Attracting process values away from a hyperplane

H

. b-c Affine upper and lower bounds for concave radius functions. d Volume upper and lower bounds for segments of symmetric rotational objects. e Steiner-type symmetrization of object to rotational object. Volumes of cuts (green) and segments along the rotational axis are preserved. The resulting radius function is concave. Contraction of the volume in one round is shown. f Final assembly into convergence of the polyhedron of process values

P(t)

to

P^{\star}

which lies on a hyperplane.

The following two lemmas on concave functions.

Lemma 7 ().

Let $a,b,c\in\mathbb{R}$ with $a<b<c$ and let $r:[a,c]\to\mathbb{R}$ be a concave function. Define $f:\mathbb{R}\to\mathbb{R}$ to be the unique affine function with $f(b)=r(b)$ and $f(c)=r(c)$ . Then $f(\xi)\geqslant r(\xi)$ for all $\xi\in[a,b]$ and $f(\xi)\leqslant r(\xi)$ for all $\xi\in[b,c]$ .

We will actually only need a weaker linear bound (Figure 2c) for our purposes:

Lemma 8 ().

Let $a,b,c\in\mathbb{R}$ with $a<b<c$ and let $r:[a,c]\to\mathbb{R}$ be a nonnegative concave function. Define $g:\mathbb{R}\to\mathbb{R}$ to be the unique affine function with $g(b)=r(b)$ and $g(c)=0$ . Then $g(\xi)\geqslant r(\xi)$ for all $\xi\in[a,b]$ and $g(\xi)\leqslant r(\xi)$ for all $\xi\in[b,c]$ .

This linear bound allows us to show that any $\alpha$ -quantile of a symmetric body on the first axis (red in Figure 2d) contains a non-negligible portion of the total volume.

Lemma 9 ().

Let $h\in\mathbb{R}_{+}$ , let $\alpha\in(0,1)$ , and let $r:\mathbb{R}\to\mathbb{R}_{+}$ be a measurable function that is concave in $[0,h]$ . Define $r_{\mathrm{left}},r_{\mathrm{right}}:\mathbb{R}\to\mathbb{R}_{+}$ by

\displaystyle r_{\mathrm{left}}(\xi)

\displaystyle=\qquad r_{\mathrm{right}}(\xi)

\displaystyle=

Setting $r_{0}=r\big((1-\alpha)h\big)$ and $C_{d-1}=\pi^{(d-1)/2}/\Gamma(\frac{d-1}{2}+1)$ , we have

\operatorname{vol}(\operatorname{Sym}(r_{\mathrm{left}}))=\int_{0}^{(1-\alpha)% h}C_{d-1}r(\xi)^{d-1}\ d\xi\leqslant C_{d-1}\frac{r_{0}^{d-1}h}{\alpha^{d-1}d}% \left(1-\alpha^{d}\right)

and

\operatorname{vol}(\operatorname{Sym}(r_{\mathrm{right}}))=\int_{(1-\alpha)h}^% {h}C_{d-1}r(\xi)^{d-1}\ d\xi\geqslant C_{d-1}\frac{r_{0}^{d-1}h}{\alpha^{d-1}d% }\alpha^{d}\enspace.

We can now show contraction of the volume of $P(t)$ . We will do this by applying a Steiner-type symmetrization to the polyhedron $P(t)\subseteq\mathbb{R}^{d}$ obtaining a body $\operatorname{Sym}(r)\in\mathbb{R}^{d}$ , with some radius function $r$ (see Figure 2e). The body $\operatorname{Sym}(r)$ is obtained by rotating function $r$ around the first coordinate axis. By construction, the cuts $P(t)\cap H_{x}$ and $\operatorname{Sym}(r)\cap H_{x}$ , the latter of which is the ball $B_{x}(r(x))$ , have the same $(d-1)$ -dimensional volume (green in the figure). Crucial in the proof is showing that the function $r$ is concave, so that Lemmas 7 and 8 can be applied to lower bound the volume shaped off the symmetric body.

Lemma 10 ().

If for round $t\geqslant 1$ , broadcasting set $M(t)$ fulfills $\lvert M(t)\rvert\leqslant d$ , then

\frac{\operatorname{vol}(P(t))}{\operatorname{vol}(P(t-1))}\leqslant 1-\alpha^% {d}\enspace.

(1)

Proof.

For brevity, set $P=P(t-1)$ and $P^{\prime}=P(t)$ . Let $A\subseteq\mathbb{R}^{d}$ be a hyperplane that contains all values of processes of the broadcasting set $M(t)$ . Such a hyperplane exists because $\lvert M(t)\rvert\leqslant d$ . Without loss of generality, by rotating and translating the coordinate system accordingly, we assume that $A=\{z\in\mathbb{R}^{d}\mid z_{1}=0\}$ .

Symmetrization of output polyhedron.

We start with a Steiner-type symmetrization of $P$ along the first axis. That is, we choose the radius function $r:\mathbb{R}\to\mathbb{R}_{+}$ such that

\displaystyle\operatorname{vol}_{d-1}(H_{x}\cap P)=\operatorname{vol}_{d-1}(H_% {x}\cap\operatorname{Sym}(r))=\operatorname{vol}_{d-1}(B_{x}(r(x)))=C_{d-1}% \cdot r(x)^{d-1}\enspace.

(2)

One observes that any sections of $P$ and $\operatorname{Sym}(r)$ within some $[a,b]$ along the first axis have same volumes:

\int_{a}^{b}\operatorname{vol}_{d-1}\left(H_{\xi}\cap P\right)\ d\xi=\int_{a}^% {b}\operatorname{vol}_{d-1}\left(H_{\xi}\cap\operatorname{Sym}(r)\right)\ d\xi\enspace.

In particular, the total volume of both objects is the same.

We next show that the radius function $r$ is concave, following the proof by Charron-Bost, Függer, and Nowak [7]. First, observe that $r$ is zero outside some finite interval $[a,b]$ by the fact that the polyhedron $P$ is finite. We will show that $r$ is concave in $[a,b]$ . Let $t\in[0,1]$ and $x,y\in[a,b]$ , and abbreviate $S=\operatorname{Sym}(r)$ . By definition of the Minkowski sum,

t\left(H_{x}\cap P\right)+(1-t)\left(H_{y}\cap P\right)=\left\{tu+(1-t)v\mid u% \in H_{x}\cap P\wedge v\in H_{y}\cap P\right\}

and from the fact that $P$ is convex, for any $u\in H_{x}\cap P$ and $v\in H_{y}\cap P$ , it is $tu+(1-t)v\in P\cap H_{tx+(1-t)y}$ , and thus,

t\left(H_{x}\cap P\right)+(1-t)\left(H_{y}\cap P\right)\subseteq H_{tx+(1-t)y}% \cap P\enspace.

Consequently,

\displaystyle\operatorname{vol}_{d-1}\left(H_{tx+(1-t)y}\cap P\right)^{\frac{1% }{d-1}}

\displaystyle\geqslant\operatorname{vol}_{d-1}\left(t\left(H_{x}\cap P\right)^% {\frac{1}{d-1}}+(1-t)\left(H_{y}\cap P\right)\right)^{\frac{1}{d-1}}\enspace.

Applying the Brunn-Minkowski inequality

\operatorname{vol}_{d-1}\left(t(H_{x}\cap P)+(1\!-\!t)(H_{y}\cap P)\right)^{% \frac{1}{d-1}}\geqslant t\operatorname{vol}_{d-1}\left(H_{x}\cap P\right)^{% \frac{1}{d-1}}+(1-t)\operatorname{vol}_{d-1}\left(H_{y}\cap P\right)^{\frac{1}% {d-1}}\\

to the right side yields

	$\displaystyle\operatorname{vol}_{d-1}\left(H_{tx+(1-t)y}\cap P\right)^{\frac{1% }{d-1}}$	$\displaystyle\geqslant t\operatorname{vol}_{d-1}\left(H_{x}\cap P\right)^{% \frac{1}{d-1}}+(1-t)\operatorname{vol}_{d-1}\left(H_{y}\cap P\right)^{\frac{1}% {d-1}}\enspace.$
By construction of the symmetrization,
	$\displaystyle\operatorname{vol}_{d-1}\left(H_{tx+(1-t)y}\cap S\right)^{\frac{1% }{d-1}}$	$\displaystyle\geqslant t\operatorname{vol}_{d-1}\left(H_{x}\cap S\right)^{% \frac{1}{d-1}}+(1-t)\operatorname{vol}_{d-1}\left(H_{y}\cap S\right)^{\frac{1}% {d-1}}\enspace.$
Combining with (2), one obtains for the radius function $r$ :
	$\displaystyle r\left(tx+(1-t)y\right)$	$\displaystyle\geqslant t\cdot r(x)+(1-t)\cdot r(y)$

from which concavity of $r$ in $[a,b]$ follows.

Volume bounds.

Next, define the half-spaces $A_{+}=\{z\in\mathbb{R}^{d}\mid z_{1}>0\}$ and $A_{-}=\{z\in\mathbb{R}^{d}\mid z_{1}<0\}$ . It is sufficient to show

{\operatorname{vol}(P^{\prime}\cap A_{+})}\leqslant(1-\alpha^{d}){% \operatorname{vol}(P\cap A_{+})}

(3)

for then

\operatorname{vol}(P^{\prime})={\operatorname{vol}(P^{\prime}\cap A_{+})}+{% \operatorname{vol}(P^{\prime}\cap A_{-})}\leqslant(1-\alpha^{d})\big({% \operatorname{vol}(P\cap A_{+})}+{\operatorname{vol}(P\cap A_{-})}\big)=(1-% \alpha^{d}){\operatorname{vol}(P)}

by symmetry.

Define $h=\sup\{z_{1}\mid z\in P\}$ . The function $r$ is concave on the interval $[0,h]$ . Lemma 5 applied to the open half-space $H=\{z\in\mathbb{R}^{d}\mid z_{1}>h\}$ , we see that $P^{\prime}\cap(1-\alpha)H=\emptyset$ . Thus, by the non-expansion property of averaging algorithms, we have

\operatorname{vol}(P^{\prime}\cap A_{+})\leqslant\operatorname{vol}\big((P\cap A% _{+})\setminus(1-\alpha)H\big)=\operatorname{vol}(\operatorname{Sym}(r_{% \mathrm{left}}))

where $r_{\mathrm{left}}$ and $r_{\mathrm{right}}$ are defined as in Lemma 9. We thus conclude

\begin{split}\frac{\operatorname{vol}(P^{\prime}\cap A_{+})}{\operatorname{vol% }(P\cap A_{+})}&\leqslant\frac{\operatorname{vol}(\operatorname{Sym}(r_{% \mathrm{left}}))}{\operatorname{vol}(\operatorname{Sym}(r_{\mathrm{left}}))+% \operatorname{vol}(\operatorname{Sym}(r_{\mathrm{right}}))}=\frac{1}{1+% \operatorname{vol}(\operatorname{Sym}(r_{\mathrm{right}}))/\operatorname{vol}(% \operatorname{Sym}(r_{\mathrm{left}}))}\\ &\leqslant\frac{1}{1+\alpha^{d}/(1-\alpha^{d})}=1-\alpha^{d}\enspace,\end{split}

which proves (3) and thus the lemma. $\hfill\blacktriangleleft$

Lemma 10 provides everything to establish contraction of the volume to zero. To allow us to conclude that this indeed implies a lower dimensionality, we use the following lemma.

Lemma 11 ().

Let $C\subseteq\mathbb{R}^{d}$ be a convex set. The following are equivalent:

1.

There exists an affine hyperplane $E\subseteq\mathbb{R}^{d}$ such that $C\subseteq E$ .
2.

$\operatorname{vol}(C)=0$ .

Proof of Theorem 6.

We are now in the position to assemble everything to prove Theorem 6. By Lemma 10, we have $\operatorname{vol}(P(t))\to 0$ as $t\to\infty$ . Since the sets $P(t)$ are non-increasing for any averaging algorithm, this is equivalent to the limit set $P^{*}=\lim_{t\to\infty}P(t)=\bigcap_{t\geqslant 0}P(t)$ being contained in some affine hyperplane $E\subseteq\mathbb{R}^{d}$ .

The set $P^{*}$ is convex as the intersection of the convex sets $P(t)$ . By Lemma 10, we have

\operatorname{vol}(P^{*})=\lim_{t\to\infty}\operatorname{vol}(P(t))\leqslant% \lim_{t\to\infty}\left(1-\alpha^{d}\right)^{t}\cdot\operatorname{vol}(P(0))=0\enspace.

Lemma 11 now shows the existence of the hyperplane $E$ such that $P^{*}\subseteq E$ . $\hfill\blacktriangleleft$

From the reductions of $d$ -rooted to $d$ -broadcastable oblivious message adversaries (Theorem 1), and the speed-up construction of alternating sufficiently long consecutive rounds of relaying messages with an averaging round [6], one obtains:

Corollary 12.

Let $0\leqslant\alpha<1$ . In a $d$ -rooted oblivious message adversary, every $\alpha$ -safe averaging algorithm solves $d$ -to- $(d-1)$ -dimensional asymptotic subspace consensus. Moreover, alternating $\frac{\pi^{2}+6}{6}n+1$ rounds of relaying messages with one round of an $\alpha$ -safe averaging algorithm, solves $d$ -to- $(d-1)$ -dimensional asymptotic subspace consensus. Moreover, we have $\operatorname{vol}(P(t))\leqslant\varepsilon$ if $t\geqslant\left(\frac{\pi^{2}+6}{6}n+1\right)\alpha^{-d}\log\frac{% \operatorname{vol}(P(0))}{\varepsilon}$ .

For example, by observing that the equal neighbor averaging algorithm is $1/n$ -safe, Corollary 12 holds with $\alpha=1/n$ for this algorithm with a time in $O\left(n^{d+1}\log\frac{\operatorname{vol}(P(0))}{\varepsilon}\right)$ .

5.3 Convergence to Lower-dimensional Subspace

Theorem 6 showed a contraction to lower dimensionality than the initial dimensionality $d$ . In this section we show that the dimensionality reduction indeed matches the lower bound in Section 3:

Theorem 13 ().

Let $d\geqslant k\geqslant 1$ . Every averaging algorithm with minimum broadcasting weight $\alpha>0$ solves $d$ -to- $(k-1)$ -dimensional asymptotic subspace consensus in a $k$ -broadcastable oblivious message adversary.

Figure 3: Thickness

\Delta

with respect to projection. a Points

X\subseteq\mathbb{R}^{d}

(in blue) are projected orthogonally via

\Pi

(dashed). The thickness is the diameter (green) of the projected image. b Same as in a, for the case

X=X(t-1)

and

\Pi

is chosen as

\Pi_{t}

, i.e., in parallel to the direction (

\vec{d}

) of the outputs in round

t-1

of those processes in the broadcasting

M(t)

. Here,

|M(t)|=2

processes, with outputs in red).

The remainder of the section is devoted to showing this results. The proof idea is to decompose process outputs (Lemma 14) and differences of process outputs (Lemma 15) into components that are within or parallel to the polyhedron of process outputs of the broadcasting set, as well as a remainder. We then define a so-called thickness with respect to an orthogonal projection (Figure 3a) and orthogonal projections onto the linear space spanned by the process outputs in the broadcasting set in Definition 16. We combine these to follow the dynamics of the thickness with respect to the latter projection (Figure 3b) during an execution.

We then show (Lemmas 17 and 18) that the orthogonal projections constructed from the broadcasting set have an accumulation point and the thickness is continuous in the projections, allowing us to measure contraction of the thickness with respect to this accumulation point (Lemma 19).

We start with the decomposition of node values into convex combinations of values from the broadcasting set and all node values.

Lemma 14 ().

Assume an averaging algorithm with minimum broadcasting weight $\alpha>0$ . For any $i\in[n]$ and round $t\geqslant 1$ , there exist points $\xi(t-1)\in P_{M(t)}(t-1)$ and $\xi^{\prime}(t-1)\in P(t-1)$ , such that $x_{i}(t)=\alpha\cdot\xi(t-1)+(1-\alpha)\cdot\xi^{\prime}(t-1)$ .

If not stated otherwise, we consider the inner product space $\mathbb{R}^{d}$ with the inner product $\left\langle\cdot,\cdot\right\rangle$ . For a set $X\subseteq\mathbb{R}^{d}$ , we write $\operatorname{span}(X)$ for the span of $X$ , i.e., the linear sub-space of $\mathbb{R}^{d}$ of all linear combinations of vectors in $X$ . For a set $X$ of points, we write $\operatorname{dir}(X)$ for the direction space $\operatorname{span}(\{x-y\mid x,y\in X\})$ . Of particular interest will be $\operatorname{dir}(X_{M(t)}(t-1))$ which has some dimensionality $m\leqslant k-1$ . For a sub-space $X$ of the inner product space $\mathbb{R}^{d}$ , we write $X^{\bot}$ for the orthogonal complement of $X$ , i.e., the set of vectors $v\in\mathbb{R}^{d}$ that are orthogonal ( $\left\langle v,v^{\prime}\right\rangle=0$ ) to all vectors $v^{\prime}\in X$ .

Using the decomposition for two node values in Lemma 14, we can also decompose their difference as shown in the following lemma.

Lemma 15 ().

Assume an algorithm with minimum broadcasting weight $\alpha>0$ . For any $i,j\in[n]$ and $t\geqslant 1$ , if the broadcasting set fulfills $|M(t)|\geqslant 1$ , there exists a vector $u_{\parallel}(t-1)\in\operatorname{dir}(X_{M(t)}(t-1))$ , and a residual vector $u_{\text{res}}(t-1)\in\{x-y\mid x,y\in P(t-1)\}$ , such that $x_{i}(t)-x_{j}(t)=\alpha\cdot u_{\parallel}(t-1)+(1-\alpha)\cdot u_{\text{res}% }(t-1)$ .

Proof.

Follows from the fact that for $x,y\in X\subseteq\mathbb{R}^{d}$ , it is $x-y\in\operatorname{dir}(X)$ and application of Lemma 14 to both points in the difference $x_{i}(t)-x_{j}(t)$ . $\hfill\blacktriangleleft$

Definition 16 (Projection $\Pi_{t}$ and Thickness $\Delta$ ).

Consider an averaging algorithm with process values in $\mathbb{R}^{d}$ . For a round $t\geqslant 1$ with broadcasting set $M(t)\neq\emptyset$ let $\Pi_{t}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ denote the orthogonal projection onto $\operatorname{dir}(X_{M(t)}(t-1))^{\perp}$ .

Let $X\subseteq\mathbb{R}^{d}$ be a non-empty finite set. Let $\Pi:\mathbb{R}^{d}\to\mathbb{R}^{d}$ be an orthogonal projection. Define the thickness of $X$ under $\Pi$ by $\Delta_{\Pi}(X):=\max_{x,y\in X}\|\Pi(x-y)\|$ .

See also Figure 3 for a visualization. From the fact that $\Pi$ is an orthogonal projection, we have $\|\Pi(x-y)\|\leqslant\|x-y\|$ .

Lemma 17 ().

Assume an averaging algorithm executed in a $k$ -broadcastable oblivious message adversary for some $k\geqslant 1$ . Then the sequence $(\Pi_{t})_{t\geqslant 1}$ has an accumulation point that is an orthogonal projection in $\mathbb{R}^{d}$ .

Proof.

The set $\cal P$ of orthogonal projections in $\mathbb{R}^{d}$ is identified with the set of matrices $\{\Pi\in\mathbb{R}^{d\times d}\mid\Pi^{2}=\Pi=\Pi^{\top}\}$ . For any $\Pi\in{\cal P}$ , eigenvalues are in $\{0,1\}$ and thus $\|\Pi\|_{\text{op}}\in\{0,1\}$ . It follows that $\cal P$ is bounded. Further, if a sequence $(Q_{n})_{n\geqslant 0}$ with $Q_{n}\in{\cal P}$ has limit $Q^{\star}$ , then ${Q^{\star}}^{2}={Q^{\star}}={Q^{\star}}^{\top}$ , from which closedness of $\cal P$ follows. Thus $\cal P$ is compact.

From the compactness of $\cal P$ , it follows that the sequence $(\Pi_{t})_{t\geqslant 1}$ , with each $\Pi_{t}\in{\cal P}$ , has an accumulation point in ${\cal P}$ . $\hfill\blacktriangleleft$

Lemma 18 ().

For any finite non-empty set $X\subseteq\mathbb{R}^{d}$ and with ${\cal P}$ being the set of orthogonal projections in $\mathbb{R}^{d}$ , the function $\Pi\mapsto\Delta_{\Pi}(X):{\cal P}\to\mathbb{R}$ is Lipschitz continuous.

Lemma 19 (Contraction of thickness).

Let $k\geqslant 1$ . Assume an averaging algorithm executed in a $k$ -broadcastable oblivious message adversary with minimum broadcasting weight $\alpha>0$ . Then there exists an orthogonal projection $\Pi:\mathbb{R}^{d}\to\mathbb{R}^{d}$ whose kernel has dimension at most $k-1$ such that $\lim_{t\to\infty}\Delta_{\Pi}(X(t))=0$ .

Proof.

Let $\Pi$ be such an orthogonal projection in the following. We show the lemma in several steps:

Monotonicity of thickness.

Since each process updates its value to a convex combination of received values, we have $P(t)\subseteq P(t-1)$ for $t\geqslant 1$ . For any projection $\Pi$ and sets $A\subseteq B$ , it is $\Delta_{\Pi}(A)\leqslant\Delta_{\Pi}(B)$ . It follows that for all $t\geqslant 1$ ,

\Delta_{\Pi}(P(t))\leqslant\Delta_{\Pi}(P(t-1))\enspace.

(4)

Contraction of thickness in one round.

By Lemma 15 applied at time $t\geqslant 1$ , for every $i,j\in[n]$ there exist $u_{\parallel}(t-1)\in\operatorname{dir}(X_{M(t)}(t-1))$ and $u_{\mathrm{res}}(t-1)\in\{x-y\mid x,y\in P(t-1)\}$ such that

x_{i}(t)-x_{j}(t)=\alpha\,u_{\parallel}(t-1)+(1-\alpha)\,u_{\mathrm{res}}(t-1)\enspace.

Apply the projection $\Pi_{t}$ that is orthogonal onto $\operatorname{dir}(X_{M(t)}(t-1))^{\perp}$ , it is

\Pi_{t}(x_{i}(t)-x_{j}(t))=(1-\alpha)\,\Pi_{t}(u_{\mathrm{res}}(t-1)),

since $\Pi_{t}(u_{\parallel}(t-1))=0$ by construction of the projection. Taking norms, yields

\|\Pi_{t}(x_{i}(t)-x_{j}(t))\|\leqslant(1-\alpha)\,\|\Pi_{t}(u_{\mathrm{res}}(% t-1))\|\enspace.

Combining with

\|\Pi_{t}(u_{\mathrm{res}}(t-1))\|\leqslant\sup_{x,y\in P(t-1)}\|\Pi_{t}(x-y)% \|\leqslant\max_{x,y\in X(t-1)}\|\Pi_{t}(x-y)\|

where the last inequality is due to the distances in a polyhedron being maximized by corner points, we obtain that for all $t\geqslant 1$ ,

\Delta_{\Pi_{t}}(X(t))\leqslant(1-\alpha)\Delta_{\Pi_{t}}(X(t-1))\enspace.

(5)

Contraction for fixed projection.

By Lemma 17, the sequence of projections $(\Pi_{t})_{t\geqslant 1}$ , each with kernel of dimension at most $k-1$ , has an accumulation point $\Pi^{\star}$ that itself is an orthogonal projection with kernel of dimension at most $k-1$ .

Let $(\Pi_{\tau_{i}})_{i\geqslant 0}$ be a subsequence with limit $\Pi^{\star}$ . By (5) and Lemma 18, for each $i\geqslant 1$ we have

\Delta_{\Pi_{\tau_{i}}}(X(\tau_{i}))\leqslant(1-\alpha)\Delta_{\Pi_{\tau_{i-1}% }}(X(\tau_{i-1}))+\varepsilon_{i}

where we choose

\varepsilon_{i}=(1-\alpha)\,\big|\Delta_{\Pi_{\tau_{i}}}(X(\tau_{i-1}))-\Delta% _{\Pi_{\tau_{i-1}}}(X(\tau_{i-1}))\big|\enspace.

By Lemma 18 and boundedness of $X(t)$ , there exists a constant $C>0$ such that

\varepsilon_{i}\leqslant C\,\|\Pi_{\tau_{i}}-\Pi_{\tau_{i-1}}\|_{\mathrm{op}}\enspace.

Since $\Pi_{\tau_{i}}\to\Pi^{\star}$ , it follows that $\varepsilon_{i}\to 0$ .

We next show that the recursion

a_{i}\leqslant(1-\alpha)a_{i-1}+\varepsilon_{i}

with $a_{i}=\Delta_{\Pi_{\tau_{i}}}(X(\tau_{i}))$ implies $\lim_{i\to\infty}a_{i}=0$ .

To see this, let $\delta>0$ . Since $\varepsilon_{i}\to 0$ , there exists a $K$ such that $\varepsilon_{i}\leqslant\delta$ for all $i\geqslant K$ . Unrolling the recursion yields

a_{i}\leqslant(1-\alpha)^{i}a_{0}+\sum_{k=1}^{i}(1-\alpha)^{\,i-k}\varepsilon_% {k}\enspace.

Splitting the sum at $K$ , we obtain

a_{i}\leqslant(1-\alpha)^{i}a_{0}+\sum_{k=1}^{K-1}(1-\alpha)^{\,i-k}% \varepsilon_{k}+\delta\sum_{k=K}^{i}(1-\alpha)^{\,i-k}\enspace.

The first two terms converge to $0$ as $i\to\infty$ , and the last term is bounded by

\delta\sum_{m=0}^{\infty}(1-\alpha)^{m}=\frac{\delta}{\alpha}\enspace.

Hence $\limsup_{i\to\infty}a_{i}\leqslant\delta/\alpha$ . Since $\delta$ was arbitrary, it follows that $\lim_{i\to\infty}a_{i}=0$ .

From Lemma 18, using Lipschitz continuity of $\Pi\to\Delta_{\Pi}(\cdot)$ and the fact that $\Pi_{\tau_{i}}\to\Pi^{\star}$ ,

\lim_{i\to\infty}\Delta_{\Pi^{\star}}(X(\tau_{i}))=0\enspace.

Applying monotonicity from (4) for rounds $t$ between successive $\tau_{i}$ , one obtains convergence of the thickness along the rounds. Thus,

\lim_{t\to\infty}\Delta_{\Pi^{\star}}(X(t))=0\enspace.

The lemma’s statement follows by setting $\Pi=\Pi^{\star}$ and observing that the kernel of $\Pi$ has dimension at most $k-1$ . $\hfill\blacktriangleleft$

Proof of Theorem 13.

Let $d\geqslant k\geqslant 1$ . For an averaging algorithm with initial values in $\mathbb{R}^{d}$ and minimum broadcasting weight $\alpha>0$ executed in a $k$ -broadcastable oblivious message adversary, by Lemma 19 there exists an orthogonal projection $\Pi$ with $\lim_{t\to\infty}\Delta_{\Pi}(X(t))=0$ . From the fact that $\ker(\Pi)$ has dimension at most $k-1$ , the sequence $(X(t))_{t}$ converges onto a $(k-1)$ -dimensional affine subspace, fulfilling (Subspace Agreement) for the $d$ -to- $(k-1)$ -dimensional subspace consensus problem. By the fact that for averaging algorithms $P(t)\subseteq P(0)$ , (Validity) is fulfilled. The theorem’s statement follows. $\hfill\blacktriangleleft$

From Theorem 13, the reduction of message adversaries in Theorem 1, and the lower bound in Theorem 2, one finally obtains a complete characterization in oblivious message adversaries:

Corollary 20 (Characterization of Asymptotic Subspace Consensus).

Let $d>s\geqslant 0$ . The problem of $d$ -to- $s$ -dimensional asymptotic subspace consensus in an oblivious message adversary $\mathcal{G}$ is solvable, if and only if $\mathcal{G}$ is $(s+1)$ -rooted. Any $\alpha$ -safe averaging algorithm with $\alpha>0$ , and in particular the equal neighbor algorithm with $\alpha=1/n$ , with and without bounded periods of intermediate message relaying rounds, is a solution.

6 Conclusion

We showed that a weakening of rooted oblivious message adversaries to $d$ -rooted adversaries achieves a dimension-reduction below the initial dimension $d$ . Central to the proof is a symmetrization of the convex hull of process outputs to a body that is symmetric around the first axis. This allows one to lower bound the volume that is shaped off the body by contraction of the convex hull, establishing also a bound on the convergence speed towards a lower dimensionality.

We then extend this analysis to a complete characterization of when a contraction to a subspace of dimension $s<d$ can be achieved, showing that this is precisely the case if the oblivious message adversary is $(s+1)$ -rooted. Moreover, simple averaging algorithms are shown to be solution to this problem. This shows that averaging algorithms degrade gracefully in (periods of) non-1-rooted message adversaries and that averaging algorithms are also effective if convergence to a single point is not necessary.

The work also raises several follow-up questions. An open problem is the quantification of the speed to dimensions $s<d$ . We also hypothesize that variants of the mid-point algorithm that have been shown to lead to fast convergence in one-dimensional [6] and multidimensional settings [7, 14], provide significantly faster convergence than the $\alpha$ -safe algorithms shown in this work. In particular we conjecture that analogous to asymptotic consensus in rooted adversaries, the dependency on the dimension $d$ can be removed.

References

[1] Yehuda Afek and Eli Gafni. Asynchrony from synchrony. In Davide Frey, Michel Raynal, Saswati Sarkar, Rudrapatna K. Shyamasundar, and Prasun Sinha, editors, Proceedings of the 14th International Conference on Distributed Computing and Networking (ICDCN 2013), volume 7730 of Lecture Notes in Computer Science, pages 225–239, Heidelberg, 2013. Springer. doi:10.1007/978-3-642-35668-1_16.
[2] Hagit Attiya and Faith Ellen. The step complexity of multidimensional approximate agreement. In Eshcar Hillel, Roberto Palmieri, and Etienne Rivière, editors, Proceedings of the 26th International Conference on Principles of Distributed Systems (OPODIS 2022), volume 253 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:12, Dagstuhl, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2022.6.
[3] Martin Biely, Josef Widder, Bernadette Charron-Bost, Antoine Gaillard, Martin Hutle, and André Schiper. Tolerating corrupted communication. In Indranil Gupta and Roger Wattenhofer, editors, Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC 2007), pages 244–253, New York, 2007. ACM. doi:10.1145/1281100.1281136.
[4] Vincent D. Blondel, Julien M. Hendrickx, Alex Olshevsky, and John N. Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking. In Proceedings of the 44th IEEE Conference on Decision and Control and 2005 European Control Conference (CDC-ECC 2005), pages 2996–3000, Piscataway, 2005. IEEE. doi:10.1109/CDC.2005.1582620.
[5] Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Approximate consensus in highly dynamic networks: The role of averaging algorithms. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), volume 9135 of Lecture Notes in Computer Science, pages 528–539, Heidelberg, 2015. Springer. doi:10.1007/978-3-662-47666-6_42.
[6] Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Fast, robust, quantizable approximate consensus. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 137:1–137:14, Dagstuhl, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2016.137.
[7] Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Multidimensional asymptotic consensus in dynamic networks, 2016. arXiv:1611.02496 [cs.DC]. doi:10.48550/arXiv.1611.02496.
[8] Bernadette Charron-Bost and André Schiper. The Heard-Of model: computing in distributed systems with benign faults. Distributed Computing, 22(1):49–71, 2009. doi:10.1007/s00446-009-0084-6.
[9] Étienne Coulouma, Emmanuel Godard, and Joseph Peters. A characterization of oblivious message adversaries for which consensus is solvable. Theoretical Computer Science, 584:80–90, 2015. doi:10.1016/j.tcs.2015.01.024.
[10] Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In André Platzer and Geoff Sutcliffe, editors, Proceedings of the 28th International Conference on Automated Deduction (CADE 28), volume 12699 of Lecture Notes in Computer Science, pages 625–635, Cham, 2021. Springer. doi:10.1007/978-3-030-79876-5_37.
[11] Shlomi Dolev and Jennifer L. Welch. Self-stabilizing clock synchronization in the presence of Byzantine faults. Journal of the ACM, 51(5):780–799, 2004. doi:10.1145/1017460.1017463.
[12] Antoine El-Hayek, Monika Henzinger, and Stefan Schmid. Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In Yael Tauman Kalai, editor, Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1–47:21, Dagstuhl, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2023.47.
[13] Matthias Függer and Thomas Nowak. Lean Proofs and Video Creation Scripts for the Paper “Asymptotic Subspace Consensus in Dynamic Networks”. Software, swhId: swh:1:dir:51a26eb1029c41b9995702cdc0041af39802d85c (visited on 2026-06-12). URL: https://github.com/BioDisCo/roots, doi:10.4230/artifacts.26596.
[14] Matthias Függer and Thomas Nowak. Fast multidimensional asymptotic and approximate consensus. In Ulrich Schmid and Josef Widder, editors, Proceedings of the 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:16, Dagstuhl, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2018.27.
[15] Matthias Függer, Thomas Nowak, and Manfred Schwarz. Tight bounds for asymptotic and approximate consensus. Journal of the ACM, 68(6):1–35, 2021. doi:10.1145/3485242.
[16] Matthias Függer, Thomas Nowak, and Kyrill Winkler. On the radius of nonsplit graphs and information dissemination in dynamic networks. Discrete Applied Mathematics, 282:257–264, 2020. doi:10.1016/j.dam.2020.02.013.
[17] Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Multidimensional approximate agreement with asynchronous fallback. In Kunal Agrawal and Julian Shun, editors, Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2023), pages 141–151, New York, 2023. ACM. doi:10.1145/3558481.3591105.
[18] Joseph Y. Halpern, Barbara Simons, Ray Strong, and Danny Dolev. Fault-tolerant clock synchronization. In Tiko Kameda, Jayadev Misra, Joseph G. Peters, and Nicola Santoro, editors, Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (PODC 1984), pages 89–102, New York, 1984. ACM. doi:10.1145/800222.806739.
[19] Hermann Kopetz and Wilhelm Ochsenreiter. Clock synchronization in distributed real-time systems. IEEE Transactions on Computers, C-36(8):933–940, 1987. doi:10.1109/TC.1987.5009516.
[20] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382–401, 1982. doi:10.1145/357172.357176.
[21] Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K. Garg. Multidimensional agreement in Byzantine systems. Distributed Computing, 28(6):423–441, 2015. doi:10.1007/s00446-014-0240-5.
[22] Richard M. Murray. Recent research in cooperative control of multivehicle systems. Journal of Dynamic Systems, Measurement, and Control, 129(5):571–583, 2007. doi:10.1115/1.2766721.
[23] Nicola Santoro and Peter Widmayer. Time is not a healer. In Burkhard Monien and Robert Cori, editors, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1989), volume 349 of Lecture Notes in Computer Science, pages 304–313, Heidelberg, 1989. Springer. doi:10.1007/BFb0028994.
[24] Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299–319, 1990. doi:10.1145/98163.98167.
[25] T. K. Srikanth and Sam Toueg. Optimal clock synchronization. Journal of the ACM, 34(3):626–645, 1987. doi:10.1145/28869.28876.
[26] Jennifer Lundelius Welch and Nancy Lynch. A new fault-tolerant algorithm for clock synchronization. Information and Computation, 77(1):1–36, 1988. doi:10.1016/0890-5401(88)90043-0.

[bib.bib1] [1] Yehuda Afek and Eli Gafni. Asynchrony from synchrony. In Davide Frey, Michel Raynal, Saswati Sarkar, Rudrapatna K. Shyamasundar, and Prasun Sinha, editors, Proceedings of the 14th International Conference on Distributed Computing and Networking (ICDCN 2013), volume 7730 of Lecture Notes in Computer Science, pages 225–239, Heidelberg, 2013. Springer. doi:10.1007/978-3-642-35668-1_16.

[bib.bib2] [2] Hagit Attiya and Faith Ellen. The step complexity of multidimensional approximate agreement. In Eshcar Hillel, Roberto Palmieri, and Etienne Rivière, editors, Proceedings of the 26th International Conference on Principles of Distributed Systems (OPODIS 2022), volume 253 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:12, Dagstuhl, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2022.6.

[bib.bib3] [3] Martin Biely, Josef Widder, Bernadette Charron-Bost, Antoine Gaillard, Martin Hutle, and André Schiper. Tolerating corrupted communication. In Indranil Gupta and Roger Wattenhofer, editors, Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC 2007), pages 244–253, New York, 2007. ACM. doi:10.1145/1281100.1281136.

[bib.bib4] [4] Vincent D. Blondel, Julien M. Hendrickx, Alex Olshevsky, and John N. Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking. In Proceedings of the 44th IEEE Conference on Decision and Control and 2005 European Control Conference (CDC-ECC 2005), pages 2996–3000, Piscataway, 2005. IEEE. doi:10.1109/CDC.2005.1582620.

[bib.bib5] [5] Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Approximate consensus in highly dynamic networks: The role of averaging algorithms. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), volume 9135 of Lecture Notes in Computer Science, pages 528–539, Heidelberg, 2015. Springer. doi:10.1007/978-3-662-47666-6_42.

[bib.bib6] [6] Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Fast, robust, quantizable approximate consensus. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 137:1–137:14, Dagstuhl, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2016.137.

[bib.bib7] [7] Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Multidimensional asymptotic consensus in dynamic networks, 2016. arXiv:1611.02496 [cs.DC]. doi:10.48550/arXiv.1611.02496.

[bib.bib8] [8] Bernadette Charron-Bost and André Schiper. The Heard-Of model: computing in distributed systems with benign faults. Distributed Computing, 22(1):49–71, 2009. doi:10.1007/s00446-009-0084-6.

[bib.bib9] [9] Étienne Coulouma, Emmanuel Godard, and Joseph Peters. A characterization of oblivious message adversaries for which consensus is solvable. Theoretical Computer Science, 584:80–90, 2015. doi:10.1016/j.tcs.2015.01.024.

[bib.bib10] [10] Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In André Platzer and Geoff Sutcliffe, editors, Proceedings of the 28th International Conference on Automated Deduction (CADE 28), volume 12699 of Lecture Notes in Computer Science, pages 625–635, Cham, 2021. Springer. doi:10.1007/978-3-030-79876-5_37.

[bib.bib11] [11] Shlomi Dolev and Jennifer L. Welch. Self-stabilizing clock synchronization in the presence of Byzantine faults. Journal of the ACM, 51(5):780–799, 2004. doi:10.1145/1017460.1017463.

[bib.bib12] [12] Antoine El-Hayek, Monika Henzinger, and Stefan Schmid. Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In Yael Tauman Kalai, editor, Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1–47:21, Dagstuhl, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2023.47.

[bib.bib13] [13] Matthias Függer and Thomas Nowak. Lean Proofs and Video Creation Scripts for the Paper “Asymptotic Subspace Consensus in Dynamic Networks”. Software, swhId: swh:1:dir:51a26eb1029c41b9995702cdc0041af39802d85c (visited on 2026-06-12). URL: https://github.com/BioDisCo/roots, doi:10.4230/artifacts.26596.

[bib.bib14] [14] Matthias Függer and Thomas Nowak. Fast multidimensional asymptotic and approximate consensus. In Ulrich Schmid and Josef Widder, editors, Proceedings of the 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:16, Dagstuhl, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2018.27.

[bib.bib15] [15] Matthias Függer, Thomas Nowak, and Manfred Schwarz. Tight bounds for asymptotic and approximate consensus. Journal of the ACM, 68(6):1–35, 2021. doi:10.1145/3485242.

[bib.bib16] [16] Matthias Függer, Thomas Nowak, and Kyrill Winkler. On the radius of nonsplit graphs and information dissemination in dynamic networks. Discrete Applied Mathematics, 282:257–264, 2020. doi:10.1016/j.dam.2020.02.013.

[bib.bib17] [17] Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Multidimensional approximate agreement with asynchronous fallback. In Kunal Agrawal and Julian Shun, editors, Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2023), pages 141–151, New York, 2023. ACM. doi:10.1145/3558481.3591105.

[bib.bib18] [18] Joseph Y. Halpern, Barbara Simons, Ray Strong, and Danny Dolev. Fault-tolerant clock synchronization. In Tiko Kameda, Jayadev Misra, Joseph G. Peters, and Nicola Santoro, editors, Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (PODC 1984), pages 89–102, New York, 1984. ACM. doi:10.1145/800222.806739.

[bib.bib19] [19] Hermann Kopetz and Wilhelm Ochsenreiter. Clock synchronization in distributed real-time systems. IEEE Transactions on Computers, C-36(8):933–940, 1987. doi:10.1109/TC.1987.5009516.

[bib.bib20] [20] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382–401, 1982. doi:10.1145/357172.357176.

[bib.bib21] [21] Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K. Garg. Multidimensional agreement in Byzantine systems. Distributed Computing, 28(6):423–441, 2015. doi:10.1007/s00446-014-0240-5.

[bib.bib22] [22] Richard M. Murray. Recent research in cooperative control of multivehicle systems. Journal of Dynamic Systems, Measurement, and Control, 129(5):571–583, 2007. doi:10.1115/1.2766721.

[bib.bib23] [23] Nicola Santoro and Peter Widmayer. Time is not a healer. In Burkhard Monien and Robert Cori, editors, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1989), volume 349 of Lecture Notes in Computer Science, pages 304–313, Heidelberg, 1989. Springer. doi:10.1007/BFb0028994.

[bib.bib24] [24] Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299–319, 1990. doi:10.1145/98163.98167.

[bib.bib25] [25] T. K. Srikanth and Sam Toueg. Optimal clock synchronization. Journal of the ACM, 34(3):626–645, 1987. doi:10.1145/28869.28876.

[bib.bib26] [26] Jennifer Lundelius Welch and Nancy Lynch. A new fault-tolerant algorithm for clock synchronization. Information and Computation, 77(1):1–36, 1988. doi:10.1016/0890-5401(88)90043-0.

Asymptotic Subspace Consensus in Dynamic Networks

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Supplementary Material:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Results and outline

2 Computational Model

Message adversaries

From Rooted to Broadcastable Graphs

Theorem 1 ([12, Theorem 32]).

3 Asymptotic Subspace Consensus

3.1 Lower bound for dimension reduction

Theorem 2 ().

4 Averaging Algorithms

Definition 3 (Minimum broadcasting weight).

5 Analysis

5.1 Distance to Hyperplane

Lemma 4 ().

Lemma 5 ().

5.2 Convergence to Zero Volume

Theorem 6.

Lemma 7 ().

Lemma 8 ().

Lemma 9 ().

Lemma 10 ().

Proof.

Symmetrization of output polyhedron.

Volume bounds.

Lemma 11 ().

Proof of Theorem 6.

Corollary 12.

5.3 Convergence to Lower-dimensional Subspace

Theorem 13 ().

Lemma 14 ().

Lemma 15 ().

Proof.

Definition 16 (Projection Πt and Thickness Δ).

Lemma 17 ().

Proof.

Lemma 18 ().

Lemma 19 (Contraction of thickness).

Proof.

Monotonicity of thickness.

Contraction of thickness in one round.

Contraction for fixed projection.

Proof of Theorem 13.

Corollary 20 (Characterization of Asymptotic Subspace Consensus).

6 Conclusion

References

Definition 16 (Projection $\Pi_{t}$ and Thickness $\Delta$ ).