Alexandre Reiffers-Masson

Nahum Shimkin

Daniel Sadoc

Eitan Altman

A Backpropagation Approach for Distributed Resource Allocation

Network resource allocation through Network Utility Maximization (NUM) is one of the fundamental problems in the realm of networked systems. In the NUM framework, the network comprises a set of nodes each of which is associated with a utility function, and the goal is to distribute resources across nodes so as to maximize the sum of the nodes utilities. In this paper, we propose a novel backpropagation approach for distributed resource allocation. e internal ow of resources among nodes is governed by the network dynamics, assumed to be captured through a directed acyclic graph (DAG). Control is exercised as an external injection of limited resources at some nodes, where the goal is to determine the optimal amount of resources to be injected at nodes, under the NUM framework. To that aim, we present a novel forward-backward algorithm, inspired by neural network training, wherein ows of resources are transferred during the forward step, and gradients are backpropagated at the backward step. Based on such gradients, the controls are adjusted, considering two variations of the algorithm under synchronous and asynchronous se ings. e proposed algorithms are distributed, in the sense that information in transferred only between neighboring nodes in the network. In addition, they are suitable for continued operation, so that the optimum resource allocation is tracked as conditions gradually change. We formally establish convergence of the proposed algorithms, and numerically compare the speed of convergence under the asynchronous se ing against its synchronous counterpart. Together, our results advance the state-of-the-art in the realm of NUM under nonlinear constraints, indicating how to leverage a backpropagation approach for that ma er.

INTRODUCTION

Network resource allocation is one of the fundamental problems in the realm of networked systems. In essence, the problem consists in determining how to distribute limited resources across nodes in a network, so as to maximize a given utility function. In particular, under the Network Utility Maximization (NUM) framework [START_REF] Neely | Stochastic network optimization with application to communication and queueing systems[END_REF][START_REF] Stai | User optimal throughput-delay trade-o in multihop networks under num framework[END_REF], each node is associated to a utility, and the goal is to maximize the sum of utilities. e generality of the framework allows it to capture a broad range of scenarios, ranging from physical networks, such as supply-chains, up to virtual networks, such as virtual markets.

In this paper, we propose a novel backpropagation approach for distributed resource allocation. e internal ow of resources among nodes is governed by network dynamics, assumed to be captured through a directed acyclic graph (DAG). Control is exercised as an external injection of 1:2 Alexandre Rei ers-Masson, Nahum Shimkin, Daniel Sadoc Menasche and Eitan Altman limited resources at some nodes. e goal is to determine the optimal amount of resources to be injected at each node. e total ow of resources received by a node yields a corresponding utility. Similarly, the external injection of resources at any node yields a cost. Utilities (resp. costs) are assumed to be concave (resp. convex) increasing, and are allowed to be nonlinear. e function which dictates the amount of ow received by a node that is forwarded to its neighbors, referred to as the interaction function, is also assumed to be concave and increasing, and possibly nonlinear. Each node is associated to its own interaction function. As ow dynamics are constrained by nonlinear interaction functions, the NUM problems considered in this work are subject to nonlinear constraints.

We pose the following questions:

• How to allocate limited resources to networked nodes so as to solve a NUM problem under nonlinear constraints? • How do synchronous solutions compare against their asynchronous counterparts?

For the optimal resource allocation, we design a novel forward-backward algorithm, inspired by neural network training, wherein ows of resources are transferred during the forward step, and gradients are backpropagated at the backward step. Based on such gradients, the controls are adjusted. We consider two variations of the algorithm under synchronous and asynchronous se ings. Backpropagation is one of the pillars of arti cial intelligence, and one of our insights consists in leveraging backpropagation for resource allocation purposes, showing its applicability in addressing NUM problems.

e proposed algorithms are distributed, in the sense that nodes only need to exchange local information with their neighbors. In addition, our algorithms are suitable for continued operation. Indeed, they allow for the optimum resource allocation to be tracked as conditions gradually change.

We formally establish convergence of the proposed algorithms, and numerically compare the speed of convergence of the asynchronous se ing against its synchronous counterpart. Together, our results advance the state-of-the-art in the realm of NUM under nonlinear constraints, indicating how to leverage a backpropagation approach for that ma er.

Summary of contributions. e main contributions of this paper are given below:

• Nonlinear resource allocation problem formulation: We formulate a NUM resource allocation problem under nonlinear constraints. e problem consists of maximizing the sum of utilities of nodes in a network where the utilities are a function of the received ows. We assume that the ow constraints are concave but possibly nonlinear, and show the convergence of the proposed backpropagation approach towards a NUM solution.

• Design of e cient algorithms: We provide two e cient algorithms which converge to the solution of the rst-order optimality conditions of our optimization problem. e rst algorithm is based on the observation that the rst-order condition can be solved using a forward-backward approach. e second algorithm is an extension of the rst one, by allowing asynchronous communications. Finally, as mentioned above, both algorithms are distributed in the sense that nodes only need to exchange local information with their neighbors. We illustrate the performance of our algorithms through a numerical study.

Outline. In the following section we report related work. en, we introduce the proposed model (Section 3), followed by synchronous and asynchronous solutions in Section 4. Numerical evaluation is reported in Section 5 and Section 6 concludes.

A Backpropagation Approach for Distributed Resource Allocation 1:3

RELATED WORK

Next, we report related work on main themes of the paper, namely classical and state-of-the-art network optimization methods (Sections 2.1 and 2.2) and strategies to handle nonlinear constraints under NUM (Section 2.3).

Primal-dual and saddle point algorithms

Our optimization problem belongs to the class of nonlinear network optimization problems [START_REF] Bertsekas | Network optimization: continuous and discrete models[END_REF].

Most of the recent research on the design of e cient algorithms for convex objective functions accounts for linear ow constraints. Next, we brie y overview some of those related e orts.

A variety of approaches have been considered under linear ow constraints, including distributed interior point methods [START_REF] Li | Distributed optimal consensus over resource allocation network and its application to dynamical economic dispatch[END_REF] or distributed primal-dual algorithms [START_REF] Ozdaglar | Incentives and pricing in communication networks[END_REF][START_REF] Wei | A distributed newton method for network utility maximization-part ii: Convergence[END_REF]. To the best of our knowledge, one of the rst works to design a distributed algorithm for NUM with convex ow constraints is [START_REF] Parag | Value-aware resource allocation for service guarantees in networks[END_REF]. e authors use Lagrange multipliers and propose a distributed price allocation algorithm which converges to the optimal solution of the network problem. Nonetheless, the ow constraints in [START_REF] Parag | Value-aware resource allocation for service guarantees in networks[END_REF] are di erent from ours, motivating a new solution. Indeed, the speci cs of our constraints allow us to design novel synchronous and asynchronous algorithms.

Similarly, in [START_REF] Bedi | Asynchronous decentralized stochastic optimization in heterogeneous networks[END_REF][START_REF] Bedi | Asynchronous saddle point method: Interference management through pricing[END_REF] the authors also suggest a decentralized asynchronous iterative algorithm to solve a NUM instance with nonlinear stochastic constraints. e authors leverage a Lagrange relaxation of the problem to derive an asynchronous saddle point iterative algorithm, which converges to the optimal solution. e algorithms proposed in the sequel also belong to the class of saddle point iterative algorithm. Nonetheless, the considered constraints do not provide an explicit characterization of the interaction between the actions of the di erent agents. erefore, in our se ing the computation of the gradients motivates the proposed backpropagation approach.

2.2

The push-pull method for network optimization and distributed learning A push-pull gradient method has been recently considered to solve the optimal ow allocation problem in a distributed fashion [START_REF] Pu | Push-pull gradient methods for distributed optimization in networks[END_REF][START_REF] Ying | Supervised learning under distributed features[END_REF]. Under the push-pull method, each node keeps in memory the current estimate of its optimal decision variable as well as an estimate of the gradient of the agents objective function. en, each agent transfers information about the gradients to its neighbors, i.e., such information is pushed downstream, whereas information about decisions is pulled from the neighbors, i.e., it is pulled upstream.

Push-pull methods have been considered for distributed machine learning applications [START_REF] Ying | Supervised learning under distributed features[END_REF], with the goal of collectively learning average values of elements distributed across the network, through consensus. In this work we are also inspired by push-pull gradient methods, but consider a di erent goal, namely solving a resource allocation problem in a distributed setup. Indeed, we leverage the intuitive resemblance between push-pull gradient methods and backpropagation to propose a novel resource allocation mechanism, accounting for nonlinear constraints.

Handling chance-constraints and general nonlinear constraints under NUM

Chance-constraints are another sort of nonlinear constraints that have also been accounted for by the NUM framework [START_REF] Shu | Interference pair-based distributed spectrum allocation in wireless mesh networks with frequency-agile radios[END_REF]. Consider, for instance, chance-constraints indicating that the tail probability of the delay distribution should be bounded by a given threshold. Under chanceconstraints, the feasible set may be non-convex, motivating the restriction to a convex subset where a near-optimal solution exists [START_REF] Shu | Interference pair-based distributed spectrum allocation in wireless mesh networks with frequency-agile radios[END_REF]. e use of surrogate linear constraints have been considered for that ma er, leveraging the Markov [START_REF] Vu | Joint path selection and rate allocation framework for 5g self-backhauled mm-wave networks[END_REF], Chebyshev or Bernstein approximations [START_REF] Zhang | e impact of stochastic noisy feedback on distributed network utility maximization[END_REF].

Distributed algorithms for convex optimization problems with nonlinear convex constraints have also been considered in [START_REF] Shah | Distributed stochastic approximation with local projections[END_REF]. One of the steps in the algorithm proposed in [START_REF] Shah | Distributed stochastic approximation with local projections[END_REF] current allocation of (external and internal) resources to node i u i amount of external resource allocated to node i (x i -u i is the amount of internal resources allocated to node i) i = f i (x i ) amount of resources from node i redistributed to its neighbors w i j fraction of resources from node i shared with node j ( ow from i to j) a projection step. Such a step is non-trivial in the resource allocation problem considered in this work. erefore, we leverage the speci cs of our optimization problem which allow us to design alternative simpler algorithms.

MODEL AND OPTIMALITY CONDITIONS

Next, we introduce the proposed model (Section 3.1) followed by an analysis of its optimality conditions (Section 3.2) and an illustrative example (Section 3.3).

Model

We consider a set of I nodes, also referred to as agents, I := {1, . . . , I }. Agents are connected through a directed acyclic graph (DAG), where relationships are described by an adjacency matrix W. e ij-entry of W, denoted by w i j ∈ [0, 1], measures the fraction of resources/ ow an agent i is sharing with j.

Nodes are divided into internal and leaf nodes. For any node i we have w ii = 0. In addition,

I j=1 w i j = 1, if i is an internal node, 0, otherwise. (1)
Let x i ∈ R + be the amount of resources received by agent i and let i ∈ R + be the amount of resources agent i is redistributing to its neighbors. An agent can receive resources from its neighbors and from an external source. Let u i ∈ R + denote the amount of external resources received by agent i. For each agent i, x i and i are related as follows:

x i = u i + I j=1 w ji j , i = f i (x i ) , (2)
where f i (•) is a continuous increasing concave di erential function. Function f i is referred to as the interaction function, and captures the amount of resources agent i is redistributing to its neighbors. Note that i and x i are concave in u := [u 1 , . . . , u I ] as long as for every i, f i is concave increasing. Our goal is to design a distributed algorithm which nds the optimal amount of external resources u which maximizes a given utility function U (x) := I i=1 U i (x i ) minus a cost C(u) := I i=1 C i (u i ) associated to the allocation of those resources. For every i ∈ I, we assume that U i (•) and -C i (•) are continuous concave and di erentiable functions.

A Backpropagation Approach for Distributed Resource Allocation 1:5

In summary, our algorithm should converge to a local optimum of the following optimization problem:

max u∈[u,u] I I i=1 U i (x i ) - I i=1 C i (u i ) := U (x) -C(u),
subject to x solution of:

x i = u i + I j=1 f j x j w ji , ∀i ∈ {1, . . . , I }, (3)
where u and u are the lower and upper bounds on the amount of external resources that can be allocated to a node.

Optimality conditions

Next, we express the Lagrangian of our optimization problem and the corresponding Karush Kuhn Tucker (KKT) conditions (see [START_REF] Boyd | Convex optimization[END_REF]). e Lagrangian is given by

L(x, u, λ) = I i=1 U i (x i ) - I i=1 C(u i ) + I i=1 λ i u i + I j=1 f j (x j )w ji -x i , (4)
where λ = [λ i ] 1≤i ≤I are the Lagrange multipliers. Note that we do not take into account the boundary constraints [u, u] I in the Lagrangian. Instead, we incorporate them directly in the gradient ascent update, to be described in the sequel. Di erentiating the above equation with respect to x i we obtain the corresponding rst order condition,

0 = U i (x i ) -λ i + f i (x i ) I j=1 w i j λ j , (5)
where f i (x i ) is the derivative of f i with respect to x i . Di erentiating L(x, u, λ) with respect to u i we obtain 0 = -C i (u i ) + λ i . (6) If (u * , x * ) is a strict local maximizer of (3) and if f i (•) is concave and increasing, U i (•) is concave and C i (•) is convex for every i ∈ {1, . . . , I }, then (u * , x * , λ * ) is a solution of the above local optimality conditions (equations ( 5)-( 6)).

Network models in Economy: network shocks versus network control

Next, we illustrate the applicability of the proposed framework in the realm of a virtual market. To that aim, we consider the general framework introduced in [START_REF] Acemoglu | Networks, shocks, and systemic risk[END_REF] to analyze the role of network interactions in the macroeconomic performance of a given Economy. Consider an Economy comprised of I agents, where x i ∈ R is the state of agent i ∈ {1, • • • , I }. e joint state of all agents is denoted by x = [x i ] 1≤i ≤I . In [START_REF] Acemoglu | Networks, shocks, and systemic risk[END_REF] the authors seek for a solution of the following xed point problem

x i = f I j=1 w i j x j + u i (7)
for all i ∈ {1, . . . , I }, where the interaction function f is a continuous and increasing function. e weights w i j capture the intensity of the interaction between i and j, with w i j ∈ [0, 1] and j w i j = 1. Finally, the utility function in [START_REF] Acemoglu | Networks, shocks, and systemic risk[END_REF] is assumed to be of the form U (x) = ( I i=1 h(x i )), and is referred to as the macro state of the Economy.

λ i =U i (x i ) + f i (x i ) I j=1 w i j λ j u i = u l i + η(λ i -C i (u i ))
N + (i) Clearly, the above economic model is a special instance of the problem formulation considered in our work. Nonetheless, in [START_REF] Acemoglu | Networks, shocks, and systemic risk[END_REF] the term u i is assumed to be an agent-level shock, capturing stochastic disturbances to an agent state. e authors assume that these external shocks are independently and identically distributed. In what follows, in contrast, we consider a controllable external input of resources, that is our main object of study.

x i = u i + I j=1 f j (x j )w ji N -(i) (λ j , k), ∀j ∈ N + (i) (λ i , k) (f j (x j ), k), ∀j ∈ N + (i) (f i (x i ), k)

DISTRIBUTED ALGORITHMS

In this section, we design two algorithms and prove their convergence towards an optimal solution of the optimization problem introduced in the previous section. Both algorithms rely on distributed computation of the Lagrange multipliers, following a gradient ascent approach inspired by the concept of backpropagation.

e rst algorithm is synchronous, and the second extends it by introducing multiple timescales that allow nodes to perform asynchronous computation.

Distributed gradient algorithm for convex flow constraints

For every node i ∈ I, we de ne the sets of upstream and downstream neighbors, N + (i) = {j ∈ I | w ji > 0} and N -(i) = {j ∈ I | w i j > 0}, respectively. e main idea behind the algorithm design consists in leveraging the fact that to compute λ * i (resp. x i ) node i only needs to retrieve

λ * j , ∀j ∈ N -(i) (resp. f j (x j ), ∀j ∈ N + (i))
. is idea is similar in spirit to backpropagation in neural networks, where gradients are computed one layer at a time, iterating backward from the last layer.

e la er corresponds to leaf nodes in our networks, i.e., nodes i such that N -(i) = ∅. Indeed, the proposed algorithm extends backpropagation to a DAG topology, generalizing the typical multilayer topology considered for machine learning applications. e proposed algorithm is described below: Backpropagation Algorithm for Distributed Resource Allocation Initialization: Set the step-size η ∈ (0, 1) and initialize u i (0) = u 0 i for all i ∈ I. Updates: At each iteration k = 1, 2, . . .:

(1) Forward step: computation of x i (k). Each node i ∈ I computes x i through the following update rule:

x i (k) = u i (k) + j ∈N + (i) f j (x j (k))w ji . (8)
, Vol. A Backpropagation Approach for Distributed Resource Allocation 1:7

(2) Backward step: computation of λ i (k). Each node i ∈ {1, . . . , I } computes λ i (k) by using x i (k) and the following update rule:

λ i (k) = U i (x i (k)) + f i (x i (k)) j ∈N -(i)
w i j λ j (k).

(3) Gradient ascent step. Each node i ∈ I computes u i (k + 1) as follows:

u i (k + 1) = u i (k) + η(-C i (u i (k)) + λ i (k)) u u , (9)
where

[•] u u is the projection operator, [x] u u := min{max{x, u}, u}.
It follows from ( 5)-( 6) that the proposed algorithm converges to a local optimum. Note that the above algorithm is distributed in the sense that a node only needs to receive information from its direct neighbors N -(i) and N + (i) to update x i , λ i and u i . Moreover, the algorithm can be implemented in an event driven framework. However, its main drawback concerns the speed of convergence, which depends on the computation power of the slowest nodes. A node i has to wait all nodes j ∈ N + (i) to compute x i (k). Similarly a node i has to wait all nodes j ∈ N -(i) to compute λ j (k). Such observation motivates an asynchronous solution as described in the sequel.

Distributed asynchronous version

Next, we design an asynchronous algorithm for the considered NUM problem. To that aim, we introduce three time scales. Let Y k ⊂ {1, . . . , I } be the random subset of activated nodes at time k. Let ν (i, k) be the number of updates at node i by time k. en, ν(i, k)

:= k k =0 I{i ∈ Y k },
where I{c} is an indicator variable, which equals 1 if condition c is satis ed, and 0 otherwise. e three step-sizes {a(k)}, {b(k)}, {b(k)} ∈ (0, 1) corresponding to three time scales are such that:

(1) ∞ k =1 a(k) = ∞ k =1 b(k) = ∞ k=1 c(k) = ∞, (2) ∞ k =1 a 2 (k) + b 2 (k) + c 2 (k) < ∞, (3) lim k →∞ b(k ) a(k) = 0 and lim k→∞ c(k ) b(k ) = 0.
It what follows, we describe the update at a given node i.

Distributed Asynchronous Gradient Algorithm (Local iteration of node i)

Initialization: Set x i (0) = x 0 i , λ i (0) = λ 0 i and u i (0) = u 0 i .
(1) Pull step:

If node i ∈ Y k , node i
• requests the outputs from its neighbors N + (i) and N -(i),

• receives f j (x j (k -τ i j (k))) from all j ∈ N + (i), and λ j (k -τ i j (k)) from all i ∈ N -(i).

1:8

Alexandre Rei ers-Masson, Nahum Shimkin, Daniel Sadoc Menasche and Eitan Altman

(2) Update step: Node i performs the following updates:

x i (k + 1) =x i (k) + a(ν (i, k))I{i ∈ Y k } u i (k) + j ∈N + (i) f j (x j (k -τ i j (k)))w ji -x i (k) , (10)
λ i (k + 1) =λ i (k) + b(ν (i, k))I{i ∈ Y k } U i (x i (k)) -λ i (k) + f i (x i (k)) j ∈N -(i) w i j λ j (k -τ i j (k)) , (11)
u i (k + 1) = u i (k) + c(ν (i, k))I{i ∈ Y k } λ i (k) -C i (u i (k)) u u . (12)
e proposed distributed asynchronous algorithm is a three time scale stochastic approximation. (1) Fast Time Scale: given by ( 10), it eventually converges to (2). e elements updated through slower time scales, given by ( 11) and ( 12), are taken as static under this standpoint; (2) Middle Time Scale: given by ( 11), it tracks the Lagrange multiplier λ i for all i ∈ I, and eventually converges to [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF]. It relies on a solution of (10) for a xed u; (3) Slow Time Scale: the gradient ascent given by ( 9) to track ( 6) is performed on the slow time scale, relying on estimates of λ i for all i ∈ I.

Convergence analysis of the asynchronous algorithm: the ODE approach

Next, we establish the convergence of the asynchronous algorithm towards a local maximum. To that aim, we rely on the ordinary di erential equation (ODE) approach. We begin by establishing the ODEs corresponding to the stochastic approximation. en, we show that the ODEs converge to a solution satisfying the KKT conditions presented in Section 3.2. Finally, we indicate that mild assumptions required for the stochastic approximation to track the ODEs, established in [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF], are satis ed, which concludes the argument.

Establishing the ODEs.

We consider the following singularly perturbed ordinary di erential equations, 15) is a projected dynamical system (see Chapter 4 in [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF]).

x i = u i + j ∈N + (i) w ji f j (x j ) -x i , (13)
λ i = ϵ 1 U i (x i ) -λ i + f i (x i ) j ∈N -(i) w i j λ j , (14)
u i = ϵ 2 (C i (u i ) -λ i -i (u)), ( 15
) ∀i ∈ {1, . . . , I }, with 0 < ϵ 1 ↓ 0, 0 < ϵ 2 ↓ 0, ϵ 2 ϵ 1 ↓ 0 and where v(u) = [ i (u)] 1≤i ≤I is the minimum adjustment needed to keep u in [u, u] I , noting that (
Next, we establish convergence of the above ODEs under the fast, medium and slow time scales, respectively.

Convergence of

ODEs. e fast timescale updates correspond to the following ODEs,

x i = u i + j ∈N + (i) w ji f j (x j ) -x i , λ i = 0, u i = 0, ∀i ∈ {1, . . . , I }. (16)
, Vol. 1, No. 1, Article 1. Publication date: January 2016.

A Backpropagation Approach for Distributed Resource Allocation 1:9

As we consider a DAG topology, for any given u the solution of ( 16) has a unique globally stable equilibrium, denoted by x * i (u), which is the solution of:

0 = u i + j ∈N + (i) w ji f j (x * j (u)) -x * i (u), ∀i ∈ I.
Updates at the middle time scale correspond to the following ODEs,

0 = u i + j ∈N + (i) w ji f j (x * j (u)) -x * i (u), (17)
λ i = U i (x * i (u)) -λ i + f i (x * i (u)) j ∈N -(i) w i j λ j , (18)
u i = 0, ( 19
)
∀i ∈ {1, . . . , I }. e convergence of ( 18) also follows from the assumption that the considered network has a DAG topology, and the fact that x i (t) has already converged to x * i (u), for any given u. en,

λ i (t) converges to λ i (x * i (u)), which is a solution of 0 = U i (x * i (u)) -λ i + f i (x * i (u)) j ∈N -(i) w i j λ j (x * j (u)).
e convergence of the slow time scale follows from the fact that L(x * (u), u, λ(x * (u)))) is a Lyapunov function corresponding to the gradient ascent [START_REF] Stai | User optimal throughput-delay trade-o in multihop networks under num framework[END_REF].

Stochastic approximation tracks

ODEs. Next, we indicate the mild assumptions over Y n and τ i (•) that ensure that if the above ODEs converge to a globally stable point then the corresponding stochastic approximation scheme also converges to the same point. e assumptions can be found in Chapter 7 of [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF], and are summarized as follows.

Assumption over {Y n }. Assume that {Y n } is an irreducible Markov chain, independent of {x(k)} ∞ k =1 , {λ(k)} ∞ k =1 , {u(k)} ∞ k =1 . Such assumption implies that lim inf n→+∞ ν (i,n) n
> 0, which in turn means that all nodes perform iterations comparably o en.

Assumption over {τ i j (k)}: e simplest assumption is to assume that the delays are bounded (i.e. τ i j (k) ∈ [0, τ ] for i, j). A more general one is to assume that

τ i j (k ) k
→ 0 a.s. ∀i, j. Alternative assumptions are presented in p.84 of [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF].

In the following section, we numerically illustrate the convergence of the asynchronous algorithm under the above assumptions.

NUMERICAL EVALUATION

In this section, we numerically evaluate the e ciency of the two proposed algorithms. Our goals are to 1) evaluate the convergence speed of the algorithms and, in particular, 2) contrast the synchronous and asynchronous solutions. To that aim, we consider a toy example which is admi edly simple but already serves to illustrate the above points.

We illustrate the application of our two algorithms under the network depicted in Figure 2(a). Motivated by proportional fairness, we let U i (x i ) = α i log(x i + 1), with α i ∼ Unif(0.5, 10) for every i ∈ I. We consider quadratic costs, C 1 (u i ) = 1 2 u 2 i , and square-root transfer functions f i (x) = √ x, for every i ∈ I.

Under the asynchronous algorithm, Y k ⊂ {1, . . . , I } comprises 4 nodes selected uniformly at random among the 12 nodes. Except for the rst 10 iterations, δ i j (n) is sampled uniformly at random from the set {n -10, . . . , n} for every i j. We also let η = 0.1, a(k) = 0.1/( k/100 + 1 ) 2/3 , (a) Network DAG q q q q q q q q qqqqqqqqq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 1 2 10 0 10 1 10 2 10 3 10 4

Iterations u q Asynch. Scheme Synch. Scheme (b) Node 2 q q q q q q q q qqqqq qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.4 b(k) = 0.1/( k/100 + 1 ) and c(k) = 0.1/( k/100 + 1 log( k/100 + 1 ) + 1). To simplify presentation, we assume that the clocks of all node are in sync, i.e., ν (i, k) = ν (j, k). Table 2 indicates that both algorithms converge to the same solution, whereas Figure 2 suggests that convergence occurs at di erent speeds. e synchronous algorithm converges in 100 iterations, whereas the asynchronous algorithm does so a er 2,000 iterations. e outputs of the two algorithms are nearly the same a er 10,000 iterations. Note that although in this simple example the convergence of the synchronous algorithm occurs rst, the computational cost per iteration of the synchronous algorithm is at least twice of its asynchronous counterpart. Indeed, less than half of the nodes are performing computation at each iteration of the asynchronous algorithm. In addition, as pointed in Section 4 the asynchronous algorithm is particularly suited for scenarios in which certain nodes may fail or linger inactive for a while. In those cases, the asynchronous algorithm will still allow other nodes to continuously evolve, whereas the synchronous algorithm convergence is u erly bounded by the speed of the slowest node.

, Vol. 1 ,

 1 No. 1, Article 1. Publication date: January 2016.

1 : 6 Alexandre

 16 Rei ers-Masson, Nahum Shimkin, Daniel Sadoc Menasche and Eitan Altman

Fig. 1 .

 1 Fig. 1. Block diagram of the synchronous resource allocation distributed algorithm, at the level of node i. Upstream neighbors (N + (i)) transfer flows at the forward step, and downstream neighbors (N -(i)) backpropagate gradients at the backward step. The current time slot, k, is included in all messages.

11 Fig. 2 .

 112 Fig. 2. Network topology and amount of external resources sent to nodes 2 and 11.

Table 1 .

 1 Alexandre Rei ers-Masson, Nahum Shimkin, Daniel Sadoc Menasche and Eitan Altman Table of notation

	consists of

Table 2 .

 2 Final outputs: amount of external resource sent to each node a er 10,000 iterations

	Node Id Initial Value	Final Value
			Synchronous Asynchronous
	1	0.1434797	3.763868	3.792356
	2	0.3456672	2.521142	2.516035
	3	0.9293197	2.107925	2.097251
	4	0.7872189	2.717501	2.723434
	5	0.6156241	2.738282	2.768356
	6	0.9371252	1.602584	1.611982
	7	0.8965552	2.383430	2.393628
	8	0.4284343	1.358760	1.329985
	9	0.3854771	0.9696633	0.9795704
	10	0.3968619	1.5792735	1.5888138
	11	0.5107909	1.1303434	1.1327786
	12	0.7000209	1.1976334	1.2010990

, Vol. 1, No. 1, Article 1. Publication date: January 2016.

A Backpropagation Approach for Distributed Resource Allocation 1:11

CONCLUSION

Inspired by backpropagation for neural network training, we have designed and analyzed a backpropagation approach for resource allocation under the NUM framework. In the proposed synchronous algorithm, gradients are computed at leaves and backpropagated upstream. en, we have extended the idea to an asynchronous se ing, also establishing convergence properties. e two algorithms are distributed and suitable for continued operation. In this short paper, we focused on a DAG topology, but the asynchronous algorithm naturally extends to general topologies. In particular, as long as ( 2) is a contraction map, the asynchronous algorithm will converge to local optima of (3).

Our work is a rst step in the use of backpropagation for resource allocation purposes, and opens up a number of di erent avenues for future research. Among those, we envision a formal analysis of the convergence rate of the algorithms, including conditions under which the asynchronous algorithm is faster than its synchronous counterpart, e.g., when accounting for node failures and repair times. We also envision extensions to account for Byzantine nodes that do not follow the proposed algorithms. en, a key challenge consists in determining to what extent an adapted version of the algorithms can remain robust against such misbehaving nodes.


Laurent Garnier
email: laurent.garnier@cea.fr

Daniel Chatroux

Sébastien Carcouet

Julien Dauchy

Figure 1 -Aims of the ESPRIT project Comparison between standard and innovative solutions to exchange energy between high energy storage systems

Electrification of always more powerful systems is usually correlated to higher needs in reliability, service continuity and energy exchanges between sources. In the field of energy storage systems, these needs are often addressed by parallelization of batteries, which are automatically disconnected in case of fault. The service continuity is thus simply ensured. If the disconnection of two batteries in parallel is an instantaneous process well controlled, the connection is a longer process more complicated, which requires adapted power electronics solutions. Based on an existing case of application and thanks to simulations, we propose in this paper to compare different solutions to exchange energy between two lithium ion battery systems.

Presentation of the application

The "Easily diStributed Personal Rapid Transit" (ESPRIT) H2020 project aims to develop a purpose-built, light weight, L category electric vehicle that can be stacked together to gain space. Thanks to pioneering coupling systems, up to 8 ESPRIT vehicles can be nested together in a road train, seven being towed, for an efficient redistribution of fleets and a smartlybalanced and cost efficient transport system. During redistribution or parking, energy can be exchanged between vehicles to maximize and secure the state of charge of the first vehicles which will be taken first by a user.

Problem presentation

Inside each electric vehicle presented just above, we have a battery system and a power exchange solution to balance energy between vehicles. The objective is to maximize and secure as far as possible the state of charge of the first vehicle of the road train because it will be the first one to leave the charging station. We can thus optimize the availability of a charged vehicle for the user.

The main specifications of the energy storage system and power exchange converter are:

• Li-ion chemistry: LiFePO4

• Unity cells format: 2.3Ah 26650, power cell The main question we will address in this paper is: Regarding the main criteria, balancing duration, losses and efficiency, volume and weight, cost and simplicity, behavior in case of short-circuit, what is the best power electric solution to exchange energy between LiFePO4 Li-ion batteries?

Battery model

To perform these comparisons a battery model, which includes the parameters capacity, internal resistance and voltage versus state of charge (SOC) is used:

Comparisons of five different power conversion solutions

In this part, after having detailed what happened in case of connection between two batteries in parallel without any adapted power electronics system, we will compare fifth solutions. The main objectives of these different solutions are firstly to compensate a difference of voltage between two sources and secondly to control the current flowing between these two sources.

To perform the comparisons, we use the following case of study:

• Battery 1 with an initial state of charge (SOC) of 5%

• Battery 2 with an initial state of charge (SOC) of 95%

• The balancing sequence is ended when the difference of SOC is less than 10%

Behavior of the system without any control of energy

Each battery system is protected against short-circuits and overloads with dedicated fuses.

For example, we can use for our application a fuse OHEV040 (40A) from Littlefuse, specified with a resistance of about 2mΩ and a melting energy of 1495 A 2 s. The length of the cable between the two battery systems is estimated at 2 m, with thus a resistance of about also 2mΩ.

The internal resistance of each battery is 192 mΩ. With all these assumptions the equivalent circuit is the following:

With initial states of charge of 95% and 5%, the starting exchange current is higher than 100A. With these simple simulations we can easily understand that the current is here only limited by the internal resistances of the two battery systems, which are much higher than the wiring resistances. Without any external control of the current, the fuse melts very quickly in less than 1s. To bear such currents, we could oversize the fuses to allow the exchange of currents. But the high current levels (up to 10C) generate thermal losses inside battery systems and has an impact on battery life time.

In this reference simulation we can calculate balancing time and energy losses:

-Balancing time : 2600 s -Energy exchanged : 5147kJ (1429Wh) -Losses inside the two battery systems : 160 kJ -Losses inside cabling : 1794J

First control solution: full power bidirectional DC/DC boost converters

The first solution proposed to exchange energy is a solution with two bidirectional converters which can be used in boost (direct) or buck (reverse) modes. For instance, a solution to exchange energy between Battery 1 and Battery 2, if the voltage level of Battery 1 is higher than voltage level of Battery 2, is to close K12, to open K11 and to use K21, K22 in buck configuration mode. Unfortunately, the two converters can't be used to protect the system against short circuits on the high voltage bus. Because of the diodes D12 or D22 the currents flowing through the converter can't be interrupted. With an estimated efficiency of 97.5% (2% of losses in the converter and 0.5% in the switch K12), we can calculate balancing time and energy losses:

Second control solution: full power bidirectional DC/DC buck converters

In the configuration with two bidirectional buck converters, each converter could be either used either in buck mode (direct) or in boost mode (reverse) . A solution to exchange energy between Battery 1 and Battery 2, if the voltage level of Batt1 is higher than voltage level of Batt2, is to close K22, open K21 and to use the switch K11, K12 in buck configuration mode. In contrast of the previous solution, the two converters can be used to protect the system against short circuits on the high voltage DC bus. With an estimated efficiency of 97,5% (2% of losses in the converter and 0,5% in the switch K12), we can calculate balancing time and energy losses, which are the same as in the previous case. In this configuration the idea is to design a small power converter, sized only for the voltage difference between the battery packs. The power is much lower. A bidirectional isolated power converter is used. It allows a voltage conversion on each battery pack. With a correct regulation, the current exchanged between Battery 1 and Battery 2 can be easily controlled. The drawback is that this system, without any other modification, can't be protected against short circuit.

Third control solution: "low power" isolated bidirectional converters

The losses inside the two converters are very low, in comparison of the energy exchanged. The main losses are located into the two batteries. At the beginning of the exchange, only the converter 2 is used to create a voltage difference and then limit the current. During this phase the switches K11, K12, K13, K14 stay closed and are used in synchronous mode to minimize the losses. At the end of this phase, when the voltage difference is too low to obtain the right level of current, the converter 1 is used to create a higher voltage difference. It allows to continue to push the current in Battery 2. The peak power transmitted by converters is about 500W, whereas the mean power is less than 100W (see figure 11) With an estimated efficiency of about 95% (5% of losses in the converters and 10mΩ to take into account of the closed switches in synchronous modes), we can calculate balancing time and energy losses:

-Balancing time : 1455 s -Energy exchanged : 5150 kJ (1430 Wh) -Losses inside two batteries systems : 143 kJ -Losses inside converters : 7,2 kJ We can remark that the losses inside converters are very low in comparison with the previous solutions. This can be explained by the optimized power of the solution and by the very low resistance of power MOSFET in synchronous mode. In this configuration each battery is divided into two parts. A first part with n modules in series (n=11 in our case) and a second one with only one module associated with one converter. Like in solution 3, converters are sized to compensate only the differences of voltage between batteries and not for the all voltages. But the main problem of this solution is the need of a specific module with also a specific software algorithm for SOC calculations and balancing. This solution will not be more detailed in this paper.

Fourth control solution: "low power" regulated modules

Fifth control solution: linear regulators

In this configuration, we use the flat curve (voltage versus SOC) of Lithium-ion Iron Phosphate batteries and we try to evaluate if there is an interest to use simple bidirectional transistors in linear mode to limit the current with a relay in parallel.

In this last configuration we can calculate balancing time and energy losses:

-Balancing time : 2900 s -Energy exchanged: 5177kJ (1438Wh) -Losses inside two battery systems : 96 kJ -Losses inside converters : 66kJ

The main drawback of this solution is the balancing time which is higher than with converters solutions. That can be explained, by the impossibility to create an artificial voltage difference between battery 1 and battery 2, to accelerate the energy exchange. However this solution has many advantages. It seems to be the simplest one, it presents a high efficiency and it allows to limit the current in case of short circuit. The sizing of limitation device must be precisely studied, especially regarding transient thermal considerations.

Impact of battery technology and usage on the preferred solution

The battery technology and the usage have an impact on the preferred solution because the sizing of the balancing device is directly linked with the following criteria: -Specification of balancing time (usage) -Usage of the battery (micro-cycles or cycles) which impact the voltage variation -Battery technology which impacts directly the curve voltage in function of SOC and thus the maximum power of the balancing device

Conclusion

In this paper, we compared different solutions to exchange energy between high voltage iron phosphate Li-ion (LiFePO4) battery packs. Two of them seem very interesting for our application (see table figure 15). The solution 3 "Low power isolated bidirectional converter" presents a very high efficiency and is certainly the most compact one. The only important drawback is its impossibility to protect the system against short circuits by limiting the current. The solution 5 "Linear regulator" is certainly the simplest one, and presents an efficiency higher than standard solutions with buck or boost converters for iron phosphate Lithium-ion batteries. It allows to protect the system against short circuits. However the transient thermal aspects must be studied carefully in order to obtain a performant solution.

Figure 2 -

 2 Figure 2 -main electrical architecture

Figure 3 -

 3 Figure 3 -Charge discharge battery cycle

Figure 4 -

 4 Figure 4 -reference simulations with two batteries in parallel

Figure 7 -

 7 Figure 7 -waveforms solution 1

-

  Figure 6 -solution 1

Figure 8

 8 Figure 8 -solution 2

Figure

  Figure 9 -solution 3

Figure 12 -solution 4 Figure 10 -

 410 Figure 12 -solution 4

Figure 14 -Figure

 14 Figure 14 -Simulation of current exchange with solution 5


Laurent Garnier
email: laurent.garnier@cea.f

Daniel Chatroux

Julien Dauchy

Comparison of power electronics solutions to exchange energy between high voltage batteries

Keywords: Li-Ion battery, power exchange converters, energy storage Balancing duration (s)

Electrification of always more powerful systems is usually correlated to higher needs in reliability, service continuity and energy exchanges between sources. In the field of energy storage systems, these needs are often addressed by parallelization of batteries, which are automatically disconnected in case of fault. The service continuity is thus simply ensured. If the disconnection of two batteries in parallel is an instantaneous process well controlled, the connection is a longer process more complicated, which requires adapted power electronics solutions. Based on a concrete case of application and thanks to simulations, we propose in this paper to compare different solutions to exchange energy between two lithium ion battery systems. This question has been addressed in the framework of a H2020 European project named ESPRIT "Easily Distributed Personal Rapid Transit". In the first part of the paper we will present the project and more precisely the societal benefits, the main objectives and the first important results. The second part of the paper will deal with the comparison of power electronics solutions designed to exchange energy between batteries.

Aims of ESPRIT project

The "Easily diStributed Personal Rapid Transit" (ESPRIT) H2020 project aims to develop a purpose-built, light weight, L category electric vehicle that can be stacked together to gain space. Thanks to pioneering coupling systems, up to 8 ESPRIT vehicles can be nested together in a road train, seven being towed, for an efficient redistribution of fleets and a smartly-balanced and cost efficient transport system. During redistribution or parking, energy can be exchanged between vehicles to maximize and secure the state of charge of the first vehicles which will be taken first by a user.

Societal benefits

It is anticipated that this concept will encourage citizens to use conventional public transport and carsharing solutions rather than their private vehicles leading to seamless intermodal transport, reduced congestion and significant reduction of noise and air pollution. As the key to the ESPRIT transport system is the ability to redistribute 8 vehicles at a time by a single operator, the project expects to demonstrate through simulation that it is possible to achieve a continuous 90% availability rate of vehicles across all stations (in last kilometre and one-way carsharing mode) using less manpower compared to current systems which have 50% of stations empty several times a day.

Power electronics problem presentation

Inside each electric vehicle presented just above, we have a battery system and a power exchange solution to balance energy between vehicles. The objective is to maximize and secure as far as possible the state of charge of the first vehicle of the road train because it will be the first one to leave the charging station. We can thus optimize the availability of a charged vehicle for the user.

The main specifications of the energy storage system and power exchange converter are:

• Li-ion chemistry: LiFePO4

• Unity cells format: 2.3Ah 26650, power cell The main question we will address in this paper is:

Regarding the main criteria, balancing duration, losses and efficiency, volume and weight, cost and simplicity, behavior in case of short-circuit, what is the best power electric solution to exchange energy between LiFePO4 Li-ion batteries?

Battery model

To perform these comparisons a battery model, which includes the parameters capacity, internal resistance and voltage versus state of charge (SOC) is used:

Comparisons of four different power conversion solutions

In this part, after having detailed what happened in case of connection between two batteries in parallel without any adapted power electronics system, we will compare four solutions. The main objectives of these different solutions are firstly to compensate a difference of voltage between two sources and secondly to control the current flowing between these two sources.

To perform the comparisons, we use the following case of study:

• Battery 1 with an initial state of charge (SOC) of 5%

• Battery 2 with an initial state of charge (SOC) of 95%

• The balancing sequence is ended when the difference of SOC is less than 10%

Behavior of the system without any control of energy

Each battery system is protected against short-circuits and overloads with dedicated fuses. For example, we can use for our application a fuse OHEV040 (40A) from Littlefuse, specified with a resistance of about 2mΩ and a melting energy of 1495 A2s. The length of the cable between the two battery systems is estimated at 2 m, with thus a resistance of about also 2mΩ. The internal resistance of each battery is 192 mΩ. With all these assumptions the equivalent circuit is the following:

With initial states of charge of 95% and 5%, the starting exchange current is higher than 100A. With these simple simulations we can easily understand that the current is here only limited by the internal resistances of the two battery systems, which are much higher than the wiring resistances. Without any external control of the current, the fuse melts very quickly in less than 1s. To bear such currents, we could oversize the fuses to allow the exchange of currents. But the high current levels (up to 10C) generate thermal losses inside battery systems and has an impact on battery life time.

In this reference simulation we can calculate balancing time and energy losses:

-Balancing time : 2600 s -Energy exchanged : 5147kJ (1429Wh) -Losses inside the two battery systems : 160 kJ -Losses inside cabling : 1794J

First control solution: full power bidirectional DC/DC boost converters

The first solution proposed to exchange energy is a solution with two bidirectional converters which can be used in boost (direct) or buck (reverse) modes. For instance, a solution to exchange energy between Battery 1 and Battery 2, if the voltage level of Battery 1 is higher than voltage level of Battery 2, is to close K12, to open K11 and to use K21, K22 in buck configuration mode. Unfortunately, the two converters can't be used to protect the system against short circuits on the high voltage bus. Because of the diodes D12 or D22 the currents flowing through the converter can't be interrupted. With an estimated efficiency of 97.5% (2% of losses in the converter and 0.5% in the switch K12), we can calculate balancing time and energy losses:

Second control solution: full power bidirectional DC/DC buck converters

In the configuration with two bidirectional buck converters, each converter could be either used either in buck mode (direct) or in boost mode (reverse) . A solution to exchange energy between Battery 1 and Battery 2, if the voltage level of Batt1 is higher than voltage level of Batt2, is to close K22, open K21 and to use the switch K11, K12 in buck configuration mode. In contrast of the previous solution, the two converters can be used to protect the system against short circuits on the high voltage DC bus. With an estimated efficiency of 97,5% (2% of losses in the converter and 0,5% in the switch K12), we can calculate balancing time and energy losses, which are the same as in the previous case. In this configuration the idea is to design a small power converter, sized only for the voltage difference between the battery packs. The power is much lower. A bidirectional isolated power converter is used. It allows a voltage conversion on each battery pack. With a correct regulation, the current exchanged between Battery 1 and Battery 2 can be easily controlled. The drawback is that this system, without any other modification, can't be protected against short circuit.

Third control solution: "low power" isolated bidirectional converters

The losses inside the two converters are very low, in comparison of the energy exchanged. The main losses are located into the two batteries. At the beginning of the exchange, only the converter 2 is used to create a voltage difference and then limit the current. During this phase the switches K11, K12, K13, K14 stay closed and are used in synchronous mode to minimize the losses. At the end of this phase, when the voltage difference is too low to obtain the right level of current, the converter 1 is used to create a higher voltage difference. It allows to continue to push the current in Battery 2.

The peak power transmitted by converters is about 500W, whereas the mean power is less than 100W (see figure 11)

With an estimated efficiency of about 95% (5% of losses in the converters and 10mΩ to take into account of the closed switches in synchronous modes), we can calculate balancing time and energy losses: We can remark that the losses inside converters are very low in comparison with the previous solutions. This can be explained by the optimized power of the solution and by the very low resistance of power MOSFET in synchronous mode. In this configuration each battery is divided into two parts. A first part with n modules in series (n=11 in our case) and a second one with only one module associated with one converter. Like in solution 3, converters are sized to compensate only the differences of voltage between batteries and not for the all voltages. But the main problem of this solution is the need of a specific module with also a specific software algorithm for SOC calculations and balancing. This solution will not be more detailed in this paper.

Fifth control solution: linear regulators

In this configuration, we use the flat curve (voltage versus SOC) of Lithium-ion Iron Phosphate batteries and we try to evaluate if there is an interest to use simple bidirectional transistors in linear mode to limit the current. A relay is added in parallel to optimize the serial resistance when the switch is completely closed. In this last configuration we can calculate balancing time and energy losses:

-Balancing time : 2900 s -Energy exchanged: 5177kJ (1438Wh) -Losses inside two battery systems : 96 kJ -Losses inside converters : 66kJ

The main drawback of this solution is the balancing time which is higher than with converters solutions. That can be explained, by the impossibility to create an artificial voltage difference between battery 1 and battery 2, to accelerate the energy exchange. However this solution has many advantages. It seems to be the simplest one, it presents a high efficiency and it allows to limit the current in case of short circuit. The sizing of limitation device must be precisely studied, especially regarding transient thermal considerations.

Results of the comparisons

*NE=non estimated

The two preferred solutions are the solutions 3 and 5, which seems much more efficient than the others. The solution 3 will be implemented in the next months. A two stages topology with a first isolated fixed ratio converter and a second bidirectional buck-boost converter will be evaluated.

Impact of battery technology and usage on the preferred solution

The battery technology and the usage have an impact on the preferred solution because the sizing of the balancing device is directly linked with the following criteria:

-Specification of balancing time (usage) -Usage of the battery (micro-cycles or cycles) which impact the voltage variation -Battery technology which impacts directly the curve voltage in function of SOC and thus the maximum power of the balancing device

Conclusion

In this paper, we compared different solutions to exchange energy between high voltage iron phosphate Liion (LiFePO4) battery packs. Two of them seem very interesting for our application (see table figure 15). The solution 3 "Low power isolated bidirectional converter" presents a very high efficiency and is certainly the most compact one. The only important drawback is its impossibility to protect the system against short circuits by limiting the current. The solution 5 "Linear regulator" is certainly the simplest one, and presents an efficiency higher than standard solutions with buck or boost converters for iron phosphate Lithium-ion batteries. It allows to protect the system against short circuits. However the transient thermal aspects must be studied carefully in order to obtain a performant solution.

Figure 1 -

 1 Figure 1 -Aims of the ESPRIT project

Figure 2 -

 2 Figure 2 -main electrical architecture

Figure 3 -

 3 Figure 3 -Charge discharge battery cycle

Figure 5 -

 5 Figure 5 -waveforms without limitation device

Figure 7 -

 7 Figure 7 -waveforms solution 1

-

  Figure 6 -solution 1

Figure 8 -solution 2

 2 Figure 8 -solution 2

Figure

  Figure 9 -solution 3

-

  Balancing time : 1455 s -Energy exchanged : 5150 kJ (1430 Wh) -Losses inside two batteries systems : 143 kJ -Losses inside converters : 7,2 kJ

Figure 10 -waveforms solution 3 Figure 11 -power in converters 2 . 2 . 5

 311225 Figure 10 -waveforms solution 3

Figure 14 -

 14 Figure 14 -Simulation of current exchange with solution 5

Authors

M. Laurent Garnier is a power electronic expert. After eighteen years in industry in R&D for specific power converters, he joined the CEA in 2010. He is working since seven years in the department "Electricity and Hydrogen for Transport" on batteries management systems, fuel cell systems and power electronics devices like chargers, DC/DC converters or inverters. During this period he has participated to 13 patents.