Distributed Constraint-Coupled Optimization over Lossy Networks

This paper considers distributed resource allocation and sum-preserving constrained optimization over lossy networks, where the links are unreliable and subject to packet drops. We define the conditions to ensure convergence under packet drops and link removal by focusing on two main properties of our allocation algorithm: (i) The weight-stochastic condition in typical consensus schemes is reduced to balanced weights, with no need for readjusting the weights to satisfy stochasticity. (ii) The algorithm does not require all-time connectivity but instead uniform connectivity over some non-overlapping finite time intervals. First, we prove that our algorithm provides primal-feasible allocation at every iteration step and converges under the conditions (i)-(ii) and some other mild conditions on the nonlinear iterative dynamics. These nonlinearities address possible practical constraints in real applications due to, for example, saturation or quantization among others. Then, using (i)-(ii) and the notion of bond-percolation theory, we relate the packet drop rate and the network percolation threshold to the (finite) number of iterations ensuring uniform connectivity and, thus, convergence towards the optimum value.


I. INTRODUCTION
Distributed algorithms are widely considered for optimization and learning over networks with several seminal works addressing the case of networks with reliable links [1]- [10]. Due to the unreliable nature of wireless communication, these results are not readily applicable in wireless networks. In such networks, randomness of the links should be considered as link-failures due to packet dropouts are inevitable. The unreliability of information exchange in such settings can influence the algorithm's convergence and solution feasibility.
Equality-constraint optimization problems intend to optimize the allocation cost subject to constant sum of overall resources. The existing literature either focus on dual-based methods and ADMM solutions [1]- [5] or primal-feasible gradient-tracking methods [6]- [10]. These allocation algorithms are developed over reliable communication networks and require either (i) stochastic weight design over the network or (ii) all-time network connectivity as a giant component [7], [8] or both [1]- [6]. However, in unreliable networks with packet loss and message drops over the communication links, these restrictive conditions do not necessarily hold. As the messages are not delivered over some links at different times, the network resembles a dynamic graph topology over time that may even lose its connectivity at some iterations, failing condition (ii) for high drop rates. On the other hand, even assuming a connectivity guarantee, condition (i) mandates robust consensus algorithms (as in [11], [12]) to modify the stochastic weights on the shared information after the drop of some messages.
The proposed allocation algorithm in this paper relaxes the stochastic condition in [1]- [6] on the adjacency matrix to being only a balanced weight matrix. Assuming the common knowledge of the delivered messages over the undirected links (i.e., both sender and receiver know whether its packet is delivered) [11], [13], there is no need for compensation strategies to readjust the weights to make them stochastic again in case of link removal or packet drops. Further, our solution only needs uniform-connectivity over time relaxing the all-time connectivity requirement over undirected [1]- [5], [7] and directed networks [6], [8]. This implies that the network can lose path-connectivity (i.e., connectivity over a sequence of directly-connected nodes) between some nodes at some iterations.
In this paper, the loss of packets at every iteration is modeled as removing the associated links over the network. Therefore, for high packet drop rates, a connected network may go through a transition phase and lose its connectivity (due to link failure). This is studied via percolation theory in network science literature [14] and is discussed in Section II-A in details. In particular, bond-percolation refers to phase-transition (or percolation) in the network connectivity under certain rate of link failure or removal [15]. Similar threshold-based approaches are adopted in the epidemic processes with a spread of a certain disease or virus over the network [16], [17]. As a typical approach, we analyze this bond-percolation analysis over general random networks, where the randomness stems from the link failures, e.g., due to random packet dropouts in wireless sensor networks [18]. Some well-known existing random models include Erdos-Renyi (ER), Scale-Free (SF), and Small-World (SW) networks. Such models are further known to be a typical representative of networks encountered in many real-world applications. Therefore, the literature focuses on studying such networks' properties to understand and resemble the behaviour of a diverse range of practical large-scale networks, including IoT, social, financial, and transportation networks. We relate the packet drop rate to the uniform connectivity of the network and, in turn, its bond-percolation threshold such that the convergence of the optimization algorithm is guaranteed.
Paper Organization: Section II formulates the problem with some background on the bond-percolation theory. Section III provides the proposed allocation algorithm and its convergence analysis. Section IV states the convergence under packet drops. Section V and VI provide simulations and concluding remarks.

A. Background on Graph Theory
In many networked applications, the topology and interactions of entities resemble a graph model. In such a network topology, connectivity plays a vital role in the convergence of the adopted algorithms. Any change in the network may cause a transition from connected to disconnected, which is studied via percolation theory.
Definition 1: [14] Given the probability of link removal equal to p, bond-percolation is defined as the probability threshold p c such that for p > p c there is no giant connected component in the network with probability 1, i.e., the network loses its connectivity. Recall that, following Kolmogorov's zero-one law, one can also claim that for probability of link removal p < p c the network preserves its connectivity [14]. In other words, this critical probability p c represents a two-sided phase transition point in terms of network connectivity.
In the perspective of packet drop analysis, this percolation threshold is similarly defined as the probability where there exists no reliable delivery-path between (at least) two nodes over the network, where a path between nodes i, j denotes a sequence of linked nodes starting at i and ending at j. Due to its complexity, no analytical solution exists to define the bond-percolation threshold for general networks, and the existing literature is mostly limited to lattice and grid networks. For example, some rigorous bounds for different lattice graphs are given in [14], [19]. However, many experimental and numerical works on this problem exist in the literature based on the Monte-Carlo simulation [15]. For a survey of percolation theory over complex networks and wireless networks see, for example, [19] and [20].
On the other hand, random graph models are analyzed to estimate the percolation thresholds of similar large-scale and complex real networks. An interesting result is reported following the nearest neighbour rule and the well-known scale-free (SF) model, assuming a set of nodes scattered via the Poisson point process, for example, in networks of cellular or mobile phone base stations. One can show that connectivity of nodes to (at least) m = 3 nearest neighbours, in the presence of lossy links and drop-outs, guarantees that the entire network remains connected [20]. For the ER random graph models [21], the bond-percolation threshold is defined equal to 1 N with N denoting the average node degree. For the Small-World (SW) networks, this threshold is exactly determined in [22]. Table I summarizes the bondpercolation thresholds for some typical networks.   TABLE I: Bond-percolation threshold for different networks   Network type Bond-percolation threshold p c Square Grid [15] 0.5 ER [21] 1 N with N as mean degree with θ as shortcut probability SF [19] with ζ(·, ·) as Hurwitz zeta function, N m as min node degree, and σ as power-law degree Next, we provide some relevant notions on algebraic graph theory [23], [24] and Laplacian analysis over graphs [25]. Denote by W the adjacency matrix associated with the network G = {V, E}, with weights W ij > 0 as the weight on the link (j, i) ∈ E and 0 for (j, i) / ∈ E. If the network is undirected with balanced weights, W is symmetric. For such a network, define For a connected network (containing a spanning-tree) with symmetric L, its eigen-spectrum includes one and only one 0 eigenvalue associated with the eigen-vector 1 n . Recall that spectral localization of the L matrix plays a key role on the convergence properties of the consensus algorithms and distributed optimization methods, see more details in [25].

B. The Equality-Constraint Allocation Problem
The constraint-coupled optimization problem in this work is defined as follows: Intuitively, solving P 1 gives the optimal allocation of resources x for which the cost F (x) is minimized. Recall that the equality-constraint is known as the feasibility constraint or the sum-preserving constraint.
In general, there might be some local box constraints m i ≤ x i ≤ M i involved in P 1 that can be addressed using additive penalty terms [26], [27] or the so-called barrier functions [2]. Proper initialization for x i (0) under such box constraints is discussed in [8]. Following the KKT conditions and under Assumption 1, it is clear that for the unique optimal point x * we have ∇F (x * ) = ϕ * 1 n with 1 n as the column vector of 1s and ∇F (x * ) := (∂f 1 (x * 1 ); · · · ; ∂f n (x * n )), assuming that this x * is in the range of the box constraints.

III. THE ALLOCATION ALGORITHM
We consider the following gradient-tracking dynamics to solve P 1 : with g n (·) and g l (·) representing some nonlinear functions on the nodes and the links. The following assumptions hold throughout the paper. Assumption 2: All the links over the network G(k) are undirected and weight-balanced, i.e., the adjacency matrix W (k) is symmetric. Further, there exists a B ∈ Z ≥0 such that the network G B (k) = k+B k G(k) is connected, i.e., the union network G B (k) includes a spanning-tree for all k ≥ 0 (implying uniform connectivity or B-connectivity).
Given the network structure, its associated balanced weight matrix W can be designed in a distributed manner using the strategy in [28]. In case of quantized updates, similar to allocation in [6], [29], integer weight-balancing strategy [30] can be used, however, with convergence to the ε-neighborhood of the optimizer [29].
Assumption 3: The nonlinear mappings g n , g l : R → R are odd and "strongly" sign-preserving with g(z)z > 0 for z = 0, g(0) = 0, and lim z→0 g(z) with κ l , K l and κ n , K n defined for g l (·) and g n (·), respectively. Such g n (·) and g l (·) include, for example, all monotonically increasing and Lipschitz functions. It can be proved that under Assumptions 2-3, the gradient-tracking solution (2) satisfies the feasibility constraint at all times k. This is called all-time feasibility, and, in resource allocation perspective, implies that the assigned resources n i=1 x i always meet the demand b and is a privilege of our gradient-tracking solution (2). Note that violating this constraint can damage or disrupt the service in many applications [2]. Our proposed allocation scheme is summarized in Algorithm ??.
Data: Input: W , N i , η, f i (·) Result: Output: Final state x(k) and cost F (x(k)) Initialization: Every node i sets k = 0 and randomly chooses m i ≤ x i (0) ≤ M i satisfying the feasibility while termination criteria NOT true; do Each node i receives g l (∂f j (x j (k)) from j ∈ N i ; Updates x i (k + 1) via Eq. (2) ; Shares ∂f i (x i (k + 1)) with its neighboring nodes j ∈ N i ; Sets k ← k + 1 ; end Algorithm 1: The Resource Allocation Algorithm Example applications in economic dispatch problem [9] and CPU scheduling and battery reservation over the smart grid [10] are given for g n (z) = z|z| v1−1 + z|z| v2−1 with 0 < v 1 < 1, v 2 > 1, and logarithmic quantizer q l (z) = sgn(z) exp(q u (log(|z|, ρ))) with q u (z) = ρ z ρ as the uniform quantizer, sgn(·) as the sign function, and [·] as rounding to the nearest integer. In case the function g n (·) or g l (·) is sign-preserving, but violates condition (3), one can guarantee convergence to the ε-neighborhood of the optimizer x * ; for example, with uniform quantization [31] and single-bit data exchange scenarios [32].
Theorem 1: Let Assumptions 1-3 hold. The dynamics converges to the optimal solution of P 1 for η(B + 1) < η := κnκ l λ2 uλ 2 n K 2 n K 2 l with λ 2 , λ n as the smallest non-zero and largest eigenvalue of G B (k) for all k ≥ 0.
Proof: We provide the sketch of the proof here. Uniqueness: Following Assumption 1 and the KKT conditions one can prove that there exists a unique optimizer x * to P 1 satisfying ∇F ∈ span(1 n ) [7].
Following the strong-convexity in Assumption 1 we have [26] F (x(k + B)) ≤ F (x(k)) We first consider the case B = 1. To prove F (k+1) ≤ F (k), we need to show where we dropped the k for notation simplicity. Recall the definition of the Laplacian-gradient tracking dynamics in [8] and define dispersion parameter ξ(k) := ∇F (k)−1 ⊤ n ∇F (k). Using the results in [25, Section V], from (2) and some mathematical manipulations based on Assumptions 2-3 it is sufficient that with the strict inequality for and for ξ = 0 n holds the equality implying ∇F ∈ span(1 n ). For B ≥ 1, the right-hand-side of (8) changes to η(B + 1) with parameters λ 2 , λ n defined for G B . This completes the proof. Note that, in the case of versatile network topology, one can choose the ratio λ2 λ 2 n for the spanning tree contained by G B (k) as the minimum connectivity ensured by Assumption 2. This min spanning tree problem could be a promising direction of future research to determine the bound on the convergence rate of the algorithm.
Some relevant results on the eigen-spectrum of L are given in the literature, for example, to estimate the spectral range based on the node degrees [25], its variation under link removal/addition [17], bounds on the algebraic connectivity λ 2 (G) ≥ 1 ndg with d g as the network diameter [24, p. 571]. The following remark distinguishes this work in terms of packet-drop tolerance.
Remark 1: In the proposed allocation dynamics (2): 1) In contrast to [1]- [7], we do not require the weight matrix to be stochastic, but only to be symmetric. Therefore, there is no need for weight compensation strategies [11], [12] after packet drops or any change in the network. 2) The algorithm converges under uniform connectivity, in contrast to all-time connectivity requirement, e.g., in [6]- [8] or ADMM-based solutions [1]- [5]. Therefore, although the network may lose its connectivity over some time periods, due to a high rate of packet drops or switching over sparse topologies, uniform connectivity over every B ∈ Z ≥0 steps is sufficient for convergence. This remark motivates the application over lossy networks, as discussed next.

IV. PACKET DROPS AND SPARSE CONNECTIVITY
In this section, we focus on networks with unreliable links. This can represent various scenarios, for instance, when nodes are activated from sleep mode at a random times as is common in devices with energy harvesting capabilities [33]. In general, data transmission over wireless networks is subject to random packet dropouts which motivates us to consider a topology with random links. Given a network topology G we model the packet drops over unreliable links at time k by removing those links from the graph structure G(k). Simply speaking, given m packet drops over distinct links at time k, m links are removed from the network G(k). Then, to satisfy Assumption 2 for convergence, the remaining reliable network needs to hold uniform connectivity over every B time iterations for a B ∈ Z ≥0 .
Assuming common knowledge, both nodes i, j are aware of the delivery or loss of the messages or packets over the bi-directional link (i, j) [11], [13]. This is to (i) keep the networking balanced following Assumption 2 and (ii) satisfy the all-time feasibility in the proof of Theorem 1. For this purpose, in case the message from i to j is lost at iteration k, node i does not incorporate possibly received message g l (∂f j (x j (k)) from node j in its data-processing and updating state x i (k + 1) via (2). In other words, the mutual messages are either both dropped or both used in Algorithm ??. This consideration makes the probability of packet drop different from the probability of link removal in our calculations; for packet drop rate p d (or packet delivery rate 1−p d ) over the links from i to j or j to i, the equivalent probability of link removal in our analysis follows as implying the probability that either of the messages or both are lost.
Recall that the notion of uniform connectivity implies that the union network over every finite number of time-steps B is connected, i.e., G B = k+B k G(k) is connected. This is much more relaxed than the all-time connectivity requirement in many literature [1]- [8]. Intuitively, for example with B = 2, one can assume existence of B = 2 links between every two nodes i, j over the union network G B = k+B k G(k). Assume p l as the probability of link removal over connected graph G. Recalling the definition of the union graph, the link between i, j over G B (k) is lost if the link over both G(k) and G(k + 1) are removed as unreliable links. Therefore, the probability that any link is unreliable over the union network G B (k) is p 2 l for B = 2. One can extend this to uniform connectivity over any B iterations, i.e., the probability of link removal over This is the intuition behind the following theorem.
Theorem 2: Assume a connected network topology G with bond-percolation threshold p c . There exists B ∈ Z ≥0 such that G B = ∪ k+B k G(k) remains uniformly connected with probability 1 under any drop rate For p d < 1 − √ 1 − p c the network G(k) remains connected at iteration k with probability 1.
Proof: First, recall that for packet drop rate p d the probability of link removal is p l = 2p d − p 2 d from (9). For percolation threshold p c , find B * ∈ Z ≥0 as the minimum value satisfying p 1+B * l < p c . Note that, for p l < 1, function p 1+B * l is monotonically increasing on p l and decreasing on B * . Then, for any B ≥ B * , the probability that all the links are dropped over B * time-steps is less than the percolation threshold p c . This means that, for B ≥ B * and p c < p l < 1, the network G B remains uniformly connected with probability 1 under link removal probability p l = 2p d − p 2 d . This gives the admissible range of the packet drop rate 1 − √ 1 − p c < p d < 1. Corollary 1: Assume a dynamic sparse network which is not connected but uniformly-connected over B 0 > 0 time iterations. Given the bond-percolation threshold p c associated with G B0 and drop rate 1 d . Then, the union network G B under the same packet drop rate remains uniformly connected for any B ≥ B 0 B * .
Remark 2: In the case of heterogeneous and time-varying drop rates p ij (k) at different links (i, j), one can consider p d = max{p ij (k)} in Theorem 2 as a conservative solution to find minimum B * value.

V. SIMULATION
For the simulation we consider a network G of n = 20 nodes based on the ER model shown in Fig. 1(TopLeft). The linking probability between every two nodes is considered as p = 0.3. The ER theory states that for p > 1 n−1 , the network is connected [21], i.e., the connectivity transition occurs at We use MATLAB randperm function to randomly assign these rates over successive periods of every 200 steps. Sample network topologies (after removal of unreliable links) associated with the given probabilities p l are shown in Fig. 1. For the ER graph in Fig. 1(a) (with p l = 0), we have N = 5.6 (as average node degree) and, from Table I, we have p c = 0.177. Note that all considered p l values are over this threshold. From Theorem 2, we have respective values B * = [3,5,7,11,23], which implies uniform-connectivity over B ≥ 23 steps and, thus, any sufficiently small η satisfying Theorem 1 ensures convergence of the allocation algorithm, as described next.
To verify, we apply Algorithm ?? over this dynamic network to solve the following allocation problem: with random parameters a i , l i , c i , d i and adding penalty terms max{x i − M i , 0} 2 + max{m i − x i , 0} 2 to address the box constraints m i = 2, M i = 7. In the proposed dynamics (2), we consider two example strongly sign-preserving nonlinear functions g n (z) = z + z 3 and logarithmic quantizer g l (z) with ρ = 1 256 . We consider random symmetric link weights W ij in the range (0, 10] (non-stochastic). For the states bounded by the given box constraints, we have κ n = 1 and K n = 147 and u = 0.05. For the logarithmic quantization we have κ l = 1 − ρ 2 = 0.998 and K l = 1 + ρ 2 = 1.002. For the given network G B we have λ2 λ 2 n = 0.019. This gives η = 0.0025 as the bound on the step rate for convergence. This gives a sufficient bound to ensure convergence and, for faster decay rates, in this simulation we choose η = 0.05. Fig. 2 shows the evolution of the residual cost F and states x i in this example.

VI. DISCUSSIONS AND CONCLUDING REMARKS
This paper provides a robust approach for distributed resource allocation over networks with unreliable links that resemble communication channels subject to packet drops. By relaxing (i) the all-time network connectivity requirement to uniform connectivity and (ii) the dynamic weightstochastic condition to weight-balanced links, the proposed allocation algorithm is proved to converge under different packet drop rates, but over a longer time horizon. This approach finds application in mobile multi-agent networks and wireless communication networks with the inevitable high rate of packet losses. The proposed algorithm has many other advantages over the existing allocation solutions. For example, it can address nonlinearities on the agents' dynamics. This nonlinear model may resemble (i) physics of the system and inherent constraints in application, e.g., quantized information exchange [6], [9], clipping, or actuator saturation, and (ii) purposely designed dynamics to suppress impulsive noise or improve the convergence time [31]. The solution is not limited to the quadratic cost models, e.g., in CPU scheduling and economic dispatch, but it can handle general non-quadratic cost models, e.g., due to additive barrier functions [2] and penalty terms [26], [27]. As a future research direction, we are extending these results to address possible time-delays in data exchange over the links.
Another interesting preventive approach is survivable network design via Q-edge-connected graphs which is robust to link removal. This problem aims to design the network such that it remains connected after removing any subset of size (up to) Q links, or it preserves a prescribed routing criterion (up to) a certain disruption cost [34], [35]. By such a design, dropping up to Q packets over the network, a route/path of package delivery between every two nodes is guaranteed over time, ensuring convergence of our allocation algorithm. Recall that existing survivable design algorithms ensure connectivity at every time-instant and extension to more relaxed uniform connectivity over time (as described in Assumption 2) is another promising future research direction.