In this paper, we derive team and person-by-person optimality conditions for distributed differential decision systems with different or decentralized information structures. The necessary conditions of optimality are given in terms of Hamiltonian sy
stem of equations consisting of a coupled backward and forward differential equations and a Hamiltonian projected onto the subspace generated by the decentralized information structures. Under certain global convexity conditions it is shown that the optimality conitions are also sufficient.
Classical approaches for asymptotic convergence to the global average in a distributed fashion typically assume timely and reliable exchange of information between neighboring components of a given multi-component system. These assumptions are not ne
cessarily valid in practical settings due to varying delays that might affect transmissions at different times, as well as possible changes in the underlying interconnection topology (e.g., due to component mobility). In this work, we propose protocols to overcome these limitations. We first consider a fixed interconnection topology (captured by a - possibly directed - graph) and propose a discrete-time protocol that can reach asymptotic average consensus in a distributed fashion, despite the presence of arbitrary (but bounded) delays in the communication links. The protocol requires that each component has knowledge of the number of its outgoing links (i.e., the number of components to which it sends information). We subsequently extend the protocol to also handle changes in the underlying interconnection topology and describe a variety of rather loose conditions under which the modified protocol allows the components to reach asymptotic average consensus. The proposed algorithms are illustrated via examples.
Consensus strategies find a variety of applications in distributed coordination and decision making in multi-agent systems. In particular, average consensus plays a key role in a number of applications and is closely associated with two classes of di
graphs, weight-balanced (for continuous-time systems) and bistochastic (for discrete-time systems). A weighted digraph is called balanced if, for each node, the sum of the weights of the edges outgoing from that node is equal to the sum of the weights of the edges incoming to that node. In addition, a weight-balanced digraph is bistochastic if all weights are nonnegative and, for each node, the sum of weights of edges incoming to that node and the sum of the weights of edges out-going from that node is unity; this implies that the corresponding weight matrix is column and row stochastic (i.e., doubly stochastic). We propose two distributed algorithms: one solves the weight-balance problem and the other solves the bistochastic matrix formation problem for a distributed system whose components (nodes) can exchange information via interconnection links (edges) that form an arbitrary, possibly directed, strongly connected communication topology (digraph). Both distributed algorithms achieve their goals asymptotically and operate iteratively by having each node adapt the (nonnegative) weights on its outgoing edges based on the weights of its incoming links (i.e., based on purely local information). We also provide examples to illustrate the operation, performance, and potential advantages of the proposed algorithms.
In this paper we consider lossless source coding for a class of sources specified by the total variational distance ball centred at a fixed nominal probability distribution. The objective is to find a minimax average length source code, where the min
imizers are the codeword lengths -- real numbers for arithmetic or Shannon codes -- while the maximizers are the source distributions from the total variational distance ball. Firstly, we examine the maximization of the average codeword length by converting it into an equivalent optimization problem, and we give the optimal codeword lenghts via a waterfilling solution. Secondly, we show that the equivalent optimization problem can be solved via an optimal partition of the source alphabet, and re-normalization and merging of the fixed nominal probabilities. For the computation of the optimal codeword lengths we also develop a fast algorithm with a computational complexity of order ${cal O}(n)$.
This paper presents lossless prefix codes optimized with respect to a pay-off criterion consisting of a convex combination of maximum codeword length and average codeword length. The optimal codeword lengths obtained are based on a new coding algorit
hm which transforms the initial source probability vector into a new probability vector according to a merging rule. The coding algorithm is equivalent to a partition of the source alphabet into disjoint sets on which a new transformed probability vector is defined as a function of the initial source probability vector and a scalar parameter. The pay-off criterion considered encompasses a trade-off between maximum and average codeword length; it is related to a pay-off criterion consisting of a convex combination of average codeword length and average of an exponential function of the codeword length, and to an average codeword length pay-off criterion subject to a limited length constraint. A special case of the first related pay-off is connected to coding problems involving source probability uncertainty and codeword overflow probability, while the second related pay-off compliments limited length Huffman coding algorithms.
In this paper, we consider multiple channels and wireless nodes with multiple transceivers. Each node assigns one transmitter at each available channel. For each assigned transmitter the node decides the power level and data rate of transmission in a
distributed fashion, such that certain Quality of Service (QoS) demands for the wireless node are satisfied. More specifically, we investigate the case in which the average SINR over all channels for each communication pair is kept above a certain threshold. A joint distributed power and rate control algorithm for each transmitter is proposed that dynamically adjusts the data rate to meet a target SINR at each channel, and to update the power levels allowing for variable desired SINRs. The algorithm is fully distributed and requires only local interference measurements. The performance of the proposed algorithm is shown through illustrative examples.
