| 1. |
- Charalambous, Themistoklis, et al.
(författare)
-
Distributed Offline Load Balancing in MapReduce Networks
- 2013
-
Ingår i: 2013 IEEE 52ND ANNUAL CONFERENCE ON DECISION AND CONTROL (CDC). - : IEEE conference proceedings. ; , s. 835-840
-
Konferensbidrag (refereegranskat)abstract
- In this paper we address the problem of balancing the processing load of MapReduce tasks running on heterogeneous clusters, i.e., clusters with different capacities and update cycles. We present a fully decentralized algorithm, based on ratio consensus, where each mapper decides the amount of workload data to handle for a single user job using only job specific local information, i.e., information that can be collected from directly connected neighboring mappers, regarding their current workload and capacity. In contrast to other algorithms in the literature, the proposed algorithm can be deployed in heterogeneous networks and can operate asynchronously in both directed and undirected communication topologies. The performance of the proposed algorithm is demonstrated via simulation experiments on large-scale strongly connected topologies.
|
|
| 2. |
- Ghadimi, Euhanna, 1982-
(författare)
-
Accelerating Convergence of Large-scale Optimization Algorithms
- 2015
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Several recent engineering applications in multi-agent systems, communication networks, and machine learning deal with decision problems that can be formulated as optimization problems. For many of these problems, new constraints limit the usefulness of traditional optimization algorithms. In some cases, the problem size is much larger than what can be conveniently dealt with using standard solvers. In other cases, the problems have to be solved in a distributed manner by several decision-makers with limited computational and communication resources. By exploiting problem structure, however, it is possible to design computationally efficient algorithms that satisfy the implementation requirements of these emerging applications.In this thesis, we study a variety of techniques for improving the convergence times of optimization algorithms for large-scale systems. In the first part of the thesis, we focus on multi-step first-order methods. These methods add memory to the classical gradient method and account for past iterates when computing the next one. The result is a computationally lightweight acceleration technique that can yield significant improvements over gradient descent. In particular, we focus on the Heavy-ball method introduced by Polyak. Previous studies have quantified the performance improvements over the gradient through a local convergence analysis of twice continuously differentiable objective functions. However, the convergence properties of the method on more general convex cost functions has not been known. The first contribution of this thesis is a global convergence analysis of the Heavy- ball method for a variety of convex problems whose objective functions are strongly convex and have Lipschitz continuous gradient. The second contribution is to tailor the Heavy- ball method to network optimization problems. In such problems, a collection of decision- makers collaborate to find the decision vector that minimizes the total system cost. We derive the optimal step-sizes for the Heavy-ball method in this scenario, and show how the optimal convergence times depend on the individual cost functions and the structure of the underlying interaction graph. We present three engineering applications where our algorithm significantly outperform the tailor-made state-of-the-art algorithms.In the second part of the thesis, we consider the Alternating Direction Method of Multipliers (ADMM), an alternative powerful method for solving structured optimization problems. The method has recently attracted a large interest from several engineering communities. Despite its popularity, its optimal parameters have been unknown. The third contribution of this thesis is to derive optimal parameters for the ADMM algorithm when applied to quadratic programming problems. Our derivations quantify how the Hessian of the cost functions and constraint matrices affect the convergence times. By exploiting this information, we develop a preconditioning technique that allows to accelerate the performance even further. Numerical studies of model-predictive control problems illustrate significant performance benefits of a well-tuned ADMM algorithm. The fourth and final contribution of the thesis is to extend our results on optimal scaling and parameter tuning of the ADMM method to a distributed setting. We derive optimal algorithm parameters and suggest heuristic methods that can be executed by individual agents using local information. The resulting algorithm is applied to distributed averaging problem and shown to yield substantial performance improvements over the state-of-the-art algorithms.
|
|
| 3. |
- Aminian, Behdad, et al.
(författare)
-
GISOO : A virtual testbed for wireless cyber-physical systems
- 2013
-
Ingår i: Industrial Electronics Society, IECON 2013 - 39th Annual Conference of the IEEE. - : IEEE. - 9781479902248 ; , s. 5588-5593
-
Konferensbidrag (refereegranskat)abstract
- The increasing demand for wireless cyber-physical systems requires correct design, implementation and validation of computation, communication and control methods. Traditional simulation tools, which focus on either computation, communication or control, are insufficient when the three aspects interact. Efforts to extend the traditional tools to cover multiple domains, e.g., from simulating only control aspects to simulating both control and communication, often rely on simplistic models of a small subset of possible communication solutions. We introduce GISOO, a virtual testbed for simulation of wireless cyber-physical systems that integrates two state-of-the art simulators, Simulink and COOJA. GISOO enables users to evaluate actual embedded code for the wireless nodes in realistic cyber-physical experiments, observing the effects of both the control and communication components. In this way, a wide range of communication solutions can be evaluated without developing abstract models of their control-relevant aspects, and changes made to the networking code in simulations is guaranteed to be translated into production code without errors. A double-tank laboratory experimental setup controlled over a multi-hop relay wireless network is used to validate GISOO and demonstrate its features.
|
|
| 4. |
- Berglund, Erik, et al.
(författare)
-
Distributed Newton Method Over Graphs : Can Sharing of Second-Order Information Eliminate the Condition Number Dependence?
- 2021
-
Ingår i: IEEE Signal Processing Letters. - : Institute of Electrical and Electronics Engineers (IEEE). - 1070-9908 .- 1558-2361. ; 28, s. 1180-1184
-
Tidskriftsartikel (refereegranskat)abstract
- One of the main advantages of second-order methods in a centralized setting is that they are insensitive to the condition number of the objective function's Hessian. For applications such as regression analysis, this means that less pre-processing of the data is required for the algorithm to work well, as the ill-conditioning caused by highly correlated variables will not be as problematic. Similar condition number independence has not yet been established for distributed methods. In this paper, we analyze the performance of a simple distributed second-order algorithm on quadratic problems and show that its convergence depends only logarithmically on the condition number. Our empirical results indicate that the use of second-order information can yield large efficiency improvements over first-order methods, both in terms of iterations and communications, when the condition number is of the same order of magnitude as the problem dimension.
|
|
| 5. |
- Björkbom, M., et al.
(författare)
-
Networked PID control : Tuning and outage compensation
- 2010
-
Ingår i: IECON 2010 - 36th Annual Conference on IEEE Industrial Electronics Society. - : IEEE. - 9781424452262 ; , s. 168-173
-
Konferensbidrag (refereegranskat)abstract
- This paper deals with architecture and algorithm design of networked control systems (NCSs) to cope with network outages. A Networked PID controller and an internal model control based tuning scheme is proposed, using the jitter margin to ensure stability despite dropped packets. For longer periods of disconnection, an outage heuristic is proposed. The control design and outage heuristic need only the step response of the process and is as such simple to apply in practice. The effect of these outages on the stability and performance of the closed-loop control system are evaluated, and compared with alternative schemes via extensive simulations. The simple Networked PID with the outage heuristic is shown to perform well, compared to other techniques proposed in the NCS literature.
|
|
| 6. |
- Charalambous, Themistoklis, 1981, et al.
(författare)
-
Totally asynchronous distributed estimation of eigenvector centrality in digraphs with application to the PageRank problem
- 2016
-
Ingår i: 2016 IEEE 55th Conference on Decision and Control, CDC 2016. - : Institute of Electrical and Electronics Engineers (IEEE). - 0743-1546. - 9781509018376 ; , s. 25-30
-
Konferensbidrag (refereegranskat)abstract
- We propose a distributed coordination mechanism which enables nodes in a directed graph to accurately estimate their eigenvector centrality (eigencentrality) even if they update their values at times determined by their own clocks. The clocks need neither be synchronized nor have the same speed. The main idea is to let nodes adjust the weights on outgoing links to compensate for their update speed: the higher the update frequency, the smaller the link weights. Our mechanism is used to develop a distributed algorithm for computing the PageRank vector, commonly used to assign importance to web pages and rank search results. Although several distributed approaches in the literature can deal with asynchronism, they cannot handle the different update speeds that occur when servers have heterogeneous computational capabilities. When existing algorithms are executed using heterogeneous update speeds, they compute incorrect PageRank values. The advantages of our algorithm over existing approaches are verified through illustrative examples.
|
|
| 7. |
- Ghadimi, Euhanna, et al.
(författare)
-
A metric for opportunistic routing in duty cycled wireless sensor networks
- 2012
-
Ingår i: Sensor, Mesh and Ad Hoc Communications and Networks (SECON), 2012 9th Annual IEEE Communications Society Conference on. - : IEEE. - 2155-5486 .- 2155-5494. - 9781467319058 ; , s. 335-343
-
Konferensbidrag (refereegranskat)abstract
- Opportunistic routing is widely known to have substantially better performance than traditional unicast routing in wireless networks with lossy links. However, wireless sensor networks are heavily duty-cycled, i.e. they frequently enter deep sleep states to ensure long network life-time. This renders existing opportunistic routing schemes impractical, as they assume that nodes are always awake and can overhear other transmissions. In this paper, we introduce a novel opportunistic routing metric that takes duty cycling into account. By analytical performance modeling and simulations, we show that our routing scheme results in significantly reduced delay and improved energy efficiency compared to traditional unicast routing. The method is based on a new metric, EDC, that reflects the expected number of duty cycled wakeups that are required to successfully deliver a packet from source to destination. We devise distributed algorithms that find the EDC-optimal forwarding, i.e. the optimal subset of neighbors that each node should permit to forward its packets. We compare the performance of the new routing with ETX-optimal single path routing in both simulations and testbed-based experiments.
|
|
| 8. |
- Ghadimi, Euhanna, et al.
(författare)
-
Optimal parameter selection for the alternating direction method of multipliers (ADMM) : quadratic problems
- 2015
-
Ingår i: IEEE Transactions on Automatic Control. - : IEEE Press. - 0018-9286 .- 1558-2523. ; 60:3, s. 644-658
-
Tidskriftsartikel (refereegranskat)abstract
- The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm parameters that minimize the convergence factor of the ADMM iterates in the context of l2-regularized minimization and constrained quadratic programming. Numerical examples show that our parameter selection rules significantly outperform existing alternatives in the literature.
|
|
| 9. |
- Ghadimi, Euhanna, et al.
(författare)
-
The ADMM algorithm for distributed averaging : convergence rates and optimal parameter selection
- 2014
-
Ingår i: CONFERENCE RECORD OF THE 2014 FORTY-EIGHTH ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS & COMPUTERS. - : IEEE conference proceedings. ; , s. 783-787
-
Konferensbidrag (refereegranskat)abstract
- We derive the optimal step-size and overrelaxationparameter that minimizes the convergence time oftwo ADMM-based algorithms for distributed averaging. Ourstudy shows that the convergence times for given step-size andover-relaxation parameters depend on the spectral propertiesof the normalized Laplacian of the underlying communicationgraph. Motivated by this, we optimize the edge-weights of thecommunication graph to improve the convergence speed evenfurther. The performance of the ADMM algorithms with ourparameter selection are compared with alternatives from theliterature in extensive numerical simulations on random graphs.
|
|
| 10. |
- Gonga, António, et al.
(författare)
-
Revisiting multi-channel communication to mitigate interference and link dynamics in wireless sensor networks
- 2012
-
Ingår i: Proceedings - IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2012. - : IEEE Computer Society. - 9780769547077 ; , s. 186-193
-
Konferensbidrag (refereegranskat)abstract
- Multichannel communication has been proposed as alternative to adaptive (single-channel) routing protocols for mitigating the impact of interference and link dynamics in wireless sensor networks. While several studies have advocated features of both techniques (not without running up against contradicting arguments) a comprehensive study that aligns these results is still lacking. This paper aims at filling this gap. We present an experimental test bed setup used to perform extensive measurements for both single-channel and multichannel communication. We first analyze single-channel and multichannel communication over a single-hop in terms of packet reception ratio, maximum burst loss, temporal correlation of losses, and loss correlations across channels. Results show that multichannel communication with channel hopping significantly reduces link burstiness and packet loss correlation. For multi-hop networks, multi-channel communication and adaptive routing show similar end-to-end reliability in dense topologies, while multichannel communication can outperform adaptive routing in sparse networks with bursty links.
|
|
