Search

Increasing the deployment of Renewable Energy Resources (RES) , along with innovations in Information and Communication Technologies (ICT), would allow prosumers to engage in the energy market and trade their excess energy with each other and with the main grid. To ensure an efficient and safe operation of energy trading, the Peer-to-Peer (P2P) energy trading approach has emerged as a viable paradigm to provide the necessary flexibility and coordinate the energy sharing between a pair of prosumers. The P2P approach is based on the concept of decentralized energy trading between prosumers (i.e., production capabilities or energy consumers). However, security protection and real-time transaction issues in the P2P market present serious challenges. In this paper, we propose a decentralized P2P energy trading approach for the energy market with high penetration of RE. First, the P2P energy market platform proposed coordinating the energy trading between energy providers and consumers to maximize their social welfare. A distributed algorithm is applied to solve the market-clearing problem based on the Alternating Direction Method of Multipliers (ADMM). In this way, the computational complexity can be reduced. Furthermore, a P2P Manager (P2PM) utility is introduced as an entity to solve the synchronization problem between peers during the market clearing. Finally, through a real-time application using Hardware-In-the-Loop (HIL), the effectiveness of the proposed P2PM is verified in terms of synchronizing the market participants and improving the power transaction.

The subject of this talk is quantum distributed computing, i.e., distributed computing where the processors of the network can exchange quantum messages. In the first part of the talk I survey recent results [Taisuke Izumi and François Le Gall, 2019; Taisuke Izumi et al., 2020; François Le Gall and Frédéric Magniez, 2018; François Le Gall et al., 2019; Xudong Wu and Penghui Yao, 2022] and some older results [Michael Ben-Or and Avinatan Hassidim, 2005; Seiichiro Tani et al., 2012] that show the potential of quantum distributed algorithms. In the second part I present our recent work [Xavier Coiteux-Roy et al., 2023] showing the limitations of quantum distributed algorithms for approximate graph coloring. Finally, I mention interesting and important open questions in quantum distributed computing.

We study the SUPPORTED model of distributed computing introduced by Schmid and Suomela [Schmid and Suomela, 2013], which generalizes the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by the subnetwork to which they apply. recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to obtain improved distributed algorithms, overcoming locality-based time lower bounds. Our main contribution is to expand the class of problems to which the SUPPORTED model applies, by handling also multiple recurring instances of the same problem that differ from each other by some problem specific input, and not only the subnetwork to which they apply. We illustrate this by considering two extended problem classes. The first class, denoted PCS, concerns problems where client nodes of the network need to be served, and each recurring instance applies to some Partial Client Set. The second class, denoted PFO, concerns situations where each recurrent instance of the problem includes a partially fixed output, which needs to be completed to a full consistent solution. Specifically, we propose some natural recurrent variants of the dominating set problem and the coloring problem that are of interest particularly in the distributed setting. For these problems, we show that information about the topology can be used to overcome locality-based lower bounds. We also categorize the round complexity of Locally Checkable Labellings in the SUPPORTED model for the simple case of paths. Finally we present some interesting open problems and some partial results towards resolving them.

The researches about a mobile entity (called agent) on dynamic networks have attracted a lot of attention in recent years. Exploration which requires an agent to visit all the nodes in the network is one of the most fundamental problems. While the exploration of dynamic networks with complete information or with no information about network changes has been studied, an agent with partial information about the network changes has not been considered yet despite its practical importance. In this paper, we consider the exploration of dynamic networks by a single agent with partial information about network changes. To the best of our knowledge, this is the very first work to investigate the exploration problem with such partial information. As a first step in this researchdirection, we focus on 1-interval connected rings as dynamic networks in this paper. We assume that the single agent has partial information called the (H, S) view by which it always knows whether or not each of the links within H hops is available in each of the next S time steps. In this setting, we show that H + S n and S dn/2e (n is the size of the network) are necessary and sufficient conditions to explore 1-interval connected rings. Moreover, we investigate the upper and lower bounds of the exploration time. It is proven that the exploration time is O(n2) for dn/2e S < 2H0 ???? 1,O(n2/H + nH) for S max(dn/2e, 2H0 ???? 1), O(n2/H + n log H) for S n ???? 1, and W(n2/H) forany S where H0 = min(H, bn/2c).

By sharing common assets such as the power grid, prosumers are closely interrelated by their actions and interests. Game theory provides powerful tools for increased coordination among the prosumers to optimize the energy resources. However, depending on the prosumer profiles and the market rules, the individual bills may notably differ and prove to be unfair. In this work, we analyze the outcomes of three relevant game-theoretical billing methods, which are innovatively transposed to the day-ahead scheduling of energy exchange within a liberalized residential community dominated by distributed energy resources. The first two approaches rely on a (static) daily billing scheme, while the third considers a multi-temporal (continuous) billing. The Nash equilibria are computed using distributed algorithms, hence ensuring individual decision-making and avoiding third-party dependencies. The cost distributions are assessed using both a qualitative and a quantitative comparison based on various prosumer profiles in a modern smart grid. It is shown that, depending on the billing option, either the contribution towards the entity (i.e., the ability to improve the global solution) or the individual empowerment (i.e., the ability to bargain) can be preferentially incentivized.

Aerial networks, utilizing Unmanned Aerial Vehicles (UAVs) have recently gained significant attention as they will play a key role in shaping the future of wireless networks including beyond 5G and 6G. This thesis addresses challenges in utilizing UAVs for wireless communication networks, focusing on two deployment scenarios: UAV-only networks and integrated aerial-terrestrial networks (IATN) with both UAVs and base stations (BSs). The first deployment scenario is applicable in situations like natural disasters, where UAV deployment is well-suited for establishing temporary infrastructure. In such cases, optimizing resource utilization is important. Further, in such scenarios, there could be a limited availability of information. Therefore, we study the resource sharing problem in a UAVs-based network under uncertainty. Specifically, the UAVs cooperate in serving the users while pooling their spectrum and energy resources in the absence of prior knowledge about different system characteristics such as the amount of available power at the other UAVs. Regarding solutions, centralized management requires comprehensive global network information accessible to a central controller for optimization. These methods, however, suffer from excessive overhead and computational cost. Therefore, we utilize Bayesian Coalition Formation Game (BCFG) to address the resource sharing problem in a cooperative UAV network with uncertainty. The second scenario involves leveraging UAVs to complement terrestrial networks, enhancing connectivity through unique features like enhanced line-of-sight, mobility, and flexibility. Consequently, efficient cooperation between aerial and terrestrial networks holds the potential to introduce an additional dimension for enhancing the user experience and optimizing network resource utilization as users can utilize both LoS and non-LoS channels, different altitudes, and types of BSs. Therefore, we present a framework to optimize the deployment of aerial n

This report documents the program and the outcomes of Dagstuhl Seminar 23112 "Unifying Formal Methods for Trustworthy Distributed Systems". Distributed systems are challenging to develop and reason about. Unsurprisingly, there have been many efforts in formally specifying, modeling, and verifying distributed systems. A bird’s eye view of this vast body of work reveals two primary sensibilities. The first is that of semi-automated or interactive deductive verification targeting structured programs and implementations, and focusing on simplifying the user’s task of providing inductive invariants. The second is that of fully-automated model checking, targeting more abstract models of distributed systems, and focusing on extending the boundaries of decidability for the parameterized model checking problem. Regrettably, solution frameworks and results in deductive verification and parameterized model checking have largely evolved in isolation while targeting the same overall goal. This seminar aimed at enabling conversations and solutions cutting across the deductive verification and model checking communities, leveraging the complementary strengths of these approaches. In particular, we explored layered and compositional approaches for modeling and verification of industrial-scale distributed systems that lend themselves well to separation of verification tasks, and thereby the use of diverse proof methodologies.

Renewable energy sources (RES) are increasingly being developed and used to address the energy crisis and protect the environment. However, the large-scale integration of wind and solar energy into the power grid is still challenging and limits the adoption of these new energy sources. Microgrids (MGs) are small-scale power generation and distribution systems that can effectively integrate renewable energy, electric loads, and energy storage systems (ESS). By using MGs, it is possible to consume renewable energy locally and reduce energy losses from long-distance transmission. This paper proposes a deep reinforcement learning (DRL)-based energy management system (EMS) called DRL-MG to process and schedule energy purchase requests from customers in real-time. Specifically, the aim of this paper is to enhance the quality of service (QoS) for customers and reduce their electricity costs by proposing an approach that utilizes a Deep Q-learning Network (DQN) model. The experimental results indicate that the proposed method outperforms commonly used real-time scheduling methods significantly.

We address the generalized Nash equilibrium seeking problem for a population of agents playing aggregative games with affine coupling constraints. We focus on semi-decentralized communication architectures, where there is a central coordinator able to gather and broadcast signals of aggregative nature to the agents. By exploiting the framework of monotone operator theory and operator splitting, we first critically review the most relevant available algorithms and then design two novel schemes: 1) a single-layer, fixed-step algorithm with convergence guarantee for general (noncocoercive, nonstrictly) monotone aggregative games and 2) a single-layer proximal-type algorithm for a class of monotone aggregative games with linearly coupled cost functions. We also design novel accelerated variants of the algorithms via (alternating) inertial and over-relaxation steps. Finally, we show via numerical simulations that the proposed algorithms outperform those in the literature in terms of convergence speed., Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public., Team Sergio Grammatico, Team Bart De Schutter

In this article, we propose a bilateral peer-to-peer (P2P) energy trading scheme under single-contract and multi-contract market setups, both as an assignment game, a special class of coalitional games. The proposed market formulation allows for efficient computation of a market equilibrium while keeping the desired economic properties offered by the coalitional games. Furthermore, our market model allows buyers to have heterogeneous preferences (product differentiation) over the energy sellers, which can be economic, social, or environmental. To address the problem of scalability in coalitional games, we design a novel distributed negotiation mechanism that utilizes the geometric structure of the equilibrium solution to improve the convergence speed. Our algorithm enables market participants (prosumers) to reach a consensus on a set of 'stable' and 'fair' bilateral contracts which encourages prosumer participation. The negotiation process is executed with virtually minimal information requirements on a time-varying communication network that in turn preserves privacy. We use operator-theoretic tools to rigorously prove its convergence. Numerical simulations illustrate the benefits of our negotiation protocol and show that the average execution time of a negotiation step is much faster than the benchmark., Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public., Team Sergio Grammatico, Team Bart De Schutter

In this paper, we study the problem of consensus-based distributed optimization, where a network of agents, abstracted as a directed graph, aims to minimize the sum of all agents' cost functions collaboratively. In existing distributed optimization approaches (Push-Pull/AB) for directed graphs, all agents exchange their states with neighbors to achieve the optimal solution with a constant stepsize, which may lead to the disclosure of sensitive and private information. For privacy preservation, we propose a novel state-decomposition based gradient tracking approach (SD-Push-Pull) for distributed optimization over directed networks that preserves differential privacy, which is a strong notion that protects agents' privacy against an adversary with arbitrary auxiliary information. The main idea of the proposed approach is to decompose the gradient state of each agent into two sub-states. Only one substate is exchanged by the agent with its neighbours over time, and the other one is not shared. That is to say, only one substate is visible to an adversary, protecting the sensitive information from being leaked. It is proved that under certain decomposition principles, a bound for the sub-optimality of the proposed algorithm can be derived and the differential privacy is achieved simultaneously. Moreover, the trade-off between differential privacy and the optimization accuracy is also characterized. Finally, a numerical simulation is provided to illustrate the effectiveness of the proposed approach. IEEE

This report documents the program and the outcomes of Dagstuhl Seminar 22492 "Formal Methods and Distributed Computing: Stronger Together", held in December 2022.

This report documents the program and the outcomes of Dagstuhl Seminar 23091, "Algorithmic Foundations of Programmable Matter", a new and emerging field that combines theoretical work on algorithms with a wide spectrum of practical applications that reach all the way from small-scale embedded systems to cyber-physical structures at nano-scale. The aim of this seminar was to bring together researchers from computational geometry, distributed computing, DNA computing, and swarm robotics who have worked on programmable matter to inform one another about the newest developments in each area and to discuss future models, approaches, and directions for new research. Similar to the first two Dagstuhl Seminars on programmable matter (16271 and 18331), we did focus on some basic problems, but also considered new problems that were now within reach to be studied.

We consider the verification of distributed systems composed of an arbitrary number of asynchronous processes. Processes are identical finite-state machines that communicate by reading from and writing to a shared memory. Beyond the standard model with finitely many registers, we tackle round-based shared-memory systems with fresh registers at each round. In the latter model, both the number of processes and the number of registers are unbounded, making verification particularly challenging. The properties studied are generic presence reachability objectives, which subsume classical questions such as safety or synchronization by expressing the presence or absence of processes in some states. In the more general round-based setting, we establish that the parameterized verification of presence reachability properties is PSPACE-complete. Moreover, for the roundless model with finitely many registers, we prove that the complexity drops down to NP-complete and we provide several natural restrictions that make the problem solvable in polynomial time.

Finding strongly connected components (SCCs) and the diameter of a directed network play a key role in a variety of machine learning and control theory problems. In this article, we provide for the first time a scalable distributed solution for these two problems by leveraging dynamical consensus-like protocols to find the SCCs. The proposed solution has a time complexity of O(NDd in-degreemax), where N is the number of vertices in the network,D is the (finite) diameter of the network, and din-degreemax is the maximum in-degree of the network. Additionally, we prove that our algorithm terminates in D+2 iterations, which allows us to retrieve the finite diameter of the network. We perform exhaustive simulations that support the outperformance of our algorithm against the state of the art on several random networks, including Erdős-Rényi, Barabási-Albert, and Watts-Strogatz networks., Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public., Team Sergio Pequito

This paper studies the multi-robot task assignment problem in which a fleet of dispersed robots needs to efficiently transport a set of dynamically appearing packages from their initial locations to corresponding destinations within prescribed time-windows. Each robot can carry multiple packages simultaneously within its capacity. Given a sufficiently large robot fleet, the objective is to minimize the robots' total travel time to transport the packages within their respective time-window constraints. The problem is shown to be NP-hard, and we design two group-based distributed auction algorithms to solve this task assignment problem. Guided by the auction algorithms, robots first distributively calculate feasible package groups that they can serve, and then communicate to find an assignment of package groups. We quantify the potential of the algorithms with respect to the number of employed robots and the capacity of the robots by considering the robots' total travel time to transport all packages. Simulation results show that the designed algorithms are competitive compared with an exact centralized Integer Linear Program representation solved with the commercial solver Gurobi, and superior to popular greedy algorithms and a heuristic distributed task allocation method., Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public., Learning & Autonomous Control

Despite the widespread usage of FIFO queues in distributed applications, designing efficient wait-free implementations of queues remains a challenge. The majority of wait-free queue implementations restrict either the number of dequeuers or the number of enqueuers that can operate on the queue, even when they use strong synchronization primitives, like the Compare&Swap. If we do not limit the number of processes that can perform enqueue and dequeue operations, the best-known upper bound on the worst case step complexity for a wait-free queue is given by [Khanchandani and Wattenhofer, 2018]. In particular, they present an implementation of a multiple dequeuer multiple enqueuer wait-free queue whose worst case step complexity is in O(√n), where n is the number of processes. In this work, we investigate whether it is possible to improve this bound. In particular, we present a wait-free FIFO queue implementation that supports n enqueuers and k dequeuers where the worst case step complexity of an Enqueue operation is in O(log n) and of a Dequeue operation is in O(k log n). Then, we show that if the semantics of the queue can be relaxed, by allowing concurrent Dequeue operations to retrieve the same element, then we can achieve O(log n) worst-case step complexity for both the Enqueue and Dequeue operations.

This paper investigates a multi-user wireless powered fog computing (FC) network, where energy-limited wireless sensor devices (WSDs) first harvest energy from a nearby hybrid access point (HAP) and then, compute their tasks locally (i.e., the local computing (LC) mode) or offload the tasks to the HAP (i.e., the FC mode) via a binary offloading policy. An optimization problem is formulated to minimize the transmit power at the HAP by jointly optimizing the time allocation ratio and the computing mode selection vector, under the energy causality constraints and the WSDs computing rate requirements constraints. To efficiently solve the formulated non-convex problem in a distributed manner, an alternating direction method of multipliers (ADMM)-based algorithm is designed. With our presented ADMM-based algorithm, each WSD is able to optimize its computing mode and offloading time with local channel state information (CSI). For comparison, a channel-sorting-based (CSB) centralized algorithm with global CSI is also designed. Simulation results show that the proposed distributed algorithm achieves the comparable performance with the centralized algorithm or by using the exhaustive search one. Moreover, to minimize the transmit power, the WSDs with the better channel quality are inclined to select the LC mode, which is much different from traditional design.

Aerial networks, utilizing Unmanned Aerial Vehicles (UAVs) have recently gained significant attention as they will play a key role in shaping the future of wireless networks including beyond 5G and 6G. This thesis addresses challenges in utilizing UAVs for wireless communication networks, focusing on two deployment scenarios: UAV-only networks and integrated aerial-terrestrial networks (IATN) with both UAVs and base stations (BSs). The first deployment scenario is applicable in situations like natural disasters, where UAV deployment is well-suited for establishing temporary infrastructure. In such cases, optimizing resource utilization is important. Further, in such scenarios, there could be a limited availability of information. Therefore, we study the resource sharing problem in a UAVs-based network under uncertainty. Specifically, the UAVs cooperate in serving the users while pooling their spectrum and energy resources in the absence of prior knowledge about different system characteristics such as the amount of available power at the other UAVs. Regarding solutions, centralized management requires comprehensive global network information accessible to a central controller for optimization. These methods, however, suffer from excessive overhead and computational cost. Therefore, we utilize Bayesian Coalition Formation Game (BCFG) to address the resource sharing problem in a cooperative UAV network with uncertainty. The second scenario involves leveraging UAVs to complement terrestrial networks, enhancing connectivity through unique features like enhanced line-of-sight, mobility, and flexibility. Consequently, efficient cooperation between aerial and terrestrial networks holds the potential to introduce an additional dimension for enhancing the user experience and optimizing network resource utilization as users can utilize both LoS and non-LoS channels, different altitudes, and types of BSs. Therefore, we present a framework to optimize the deployment of aerial n

We address the generalized Nash equilibrium seeking problem in a partial-decision information scenario, where each agent can only exchange information with some neighbors, although its cost function possibly depends on the strategies of all agents. The few existing methods build on projected pseudo-gradient dynamics, and require either double-layer iterations or conservative conditions on the step sizes. To overcome both these flaws and improve efficiency, we design the first fully-distributed single-layer algorithms based on proximal best-response. Our schemes are fixed-step and allow for inexact updates, which is crucial for reducing the computational complexity. Under standard assumptions on the game primitives, we establish convergence to a variational equilibrium (with linear rate for games without coupling constraints) by recasting our algorithms as proximal-point methods, opportunely preconditioned to distribute the computation among the agents. Since our analysis hinges on a restricted monotonicity property, we also provide new general results that significantly extend the domain of applicability of proximal-point methods. Besides, our operator-theoretic approach favors the implementation of provably correct acceleration schemes that can further improve the convergence speed. Finally, the potential of our algorithms is demonstrated numerically, revealing much faster convergence with respect to projected pseudo-gradient methods and validating our theoretical findings., Team Sergio Grammatico, Team DeSchutter

In this article, we consider a sequence of transferable utility coalitional games, where the actual coalitional values are unknown but vary within known bounds. As a solution to the resulting family of games, we formalize the notion of 'robust core.' Our main contribution is to design two distributed algorithms, namely 1) distributed payoff allocation and 2) distributed bargaining, which converge to a consensual payoff distribution in the robust core. We adopt an operator-theoretic perspective to show convergence of both algorithms executed on time-varying communication networks. An energy storage optimization application motivates our framework for 'robust coalitional games.', Accepted Author Manuscript, Team Sergio Grammatico, Team DeSchutter

Finding strongly connected components (SCCs) and the diameter of a directed network play a key role in a variety of machine learning and control theory problems. In this article, we provide for the first time a scalable distributed solution for these two problems by leveraging dynamical consensus-like protocols to find the SCCs. The proposed solution has a time complexity of O(NDdmaxin-degree) , where N is the number of vertices in the network, D is the (finite) diameter of the network, and dmaxin-degree is the maximum in-degree of the network. Additionally, we prove that our algorithm terminates in D+2 iterations, which allows us to retrieve the finite diameter of the network. We perform exhaustive simulations that support the outperformance of our algorithm against the state of the art on several random networks, including Erdős–Rényi, Barabási–Albert, and Watts–Strogatz networks.

This article investigates distributed online convex optimization in the presence of an aggregative variable without any global/central coordinators over a multiagent network. In this problem, each individual agent is only able to access partial information of time-varying global loss functions, thus requiring local information exchanges between neighboring agents. Motivated by many applications in reality, the considered local loss functions depend not only on their own decision variables, but also on an aggregative variable, such as the average of all decision variables. To handle this problem, an online distributed gradient tracking algorithm (O-DGT) is proposed with exact gradient information and it is shown that the dynamic regret is upper bounded by three terms: 1) a sublinear term; 2) a path variation term; and 3) a gradient variation term. Meanwhile, the O-DGT algorithm is also analyzed with stochastic/noisy gradients, showing that the expected dynamic regret has the same upper bound as the exact gradient case. To our best knowledge, this article is the first to study online convex optimization in the presence of an aggregative variable, which enjoys new characteristics in comparison with the conventional scenario without the aggregative variable. Finally, a numerical experiment is provided to corroborate the obtained theoretical results., QC 20230228

In this paper, we investigate distributed convex optimization with both inequality and equality constraints, where the objective function can be a general nonsmooth convex function and all the constraints can be both sparsely and densely coupling. By strategically integrating ideas from primal-dual, proximal, and virtual-queue optimization methods, we develop a novel distributed algorithm, referred to as IPLUX, to address the problem over a connected, undirected graph. We show that IPLUX achieves an $O(1/k)$ rate of convergence in terms of optimality and feasibility, which is stronger than the convergence results of the alternative methods and eliminates the standard assumption on the compactness of the feasible region. Finally, IPLUX exhibits faster convergence and higher efficiency than several state-of-the-art methods in the simulation., QC 20230508

In this paper we study the distributed average consensus problem in multi-agent systems with dynamically-changing directed communication links that are subject to quantized information flow. We present and analyze a distributed averaging algorithm which operates exclusively with quantized values (i.e., the information stored, processed and exchanged between neighboring agents is subject to deterministic uniform quantization) and relies on event-driven updates (e.g., to reduce energy con-sumption, communication bandwidth, network congestion, and/or processor usage). We characterize the properties of the proposed distributed algorithm over dynamic directed communication topologies subject to some connectivity conditions and we show that its execution allows each agent to reach, in finite time, a fixed state that is equal (within one quantization level) to the average of the initial states. The main idea of the proposed algorithm is that each agent (i) models its initial state as two quantized fractions which have numerators equal to the agent's initial state and denominators equal to one, and (ii) transmits one fraction randomly while it keeps the other stored. Then, every time an agent receives one or more fractions, it averages their numerators with the numerator of the fraction it stored, and then transmits them to randomly selected out-neighbors. Finally, we provide examples to illustrate the operation, performance, and potential advantages of the proposed algorithm. We compare against various quantized average consensus algorithms and show that our algorithm's convergence speed is among the fastest in the current literature., QC 20221111

In this article, we propose a distributed negotiation framework that allows a set of cooperative agents to find a common ground with their neighbors while attempting to modify their initial opinion by the least possible amount. Based on such a framework, we develop a distributed agreement approach where the effort spent in the local agreement reflects the relevance of the agents in a weighted consensus process. In particular, we assume that players whose ideas happen to satisfactory mediate the standpoint of their interlocutors will end-up being more influential in the overall decision-making process. We conclude the article by applying the proposed methodology in the context of distributed data aggregation scenarios, as a way to mitigate the effect of outliers (e.g., faulty sensors)., QC 20220916

This paper presents an overview on the recent advances in the research of security of cyber-physical systems. We place particular emphases on consensus problems for multi-agent systems in hostile environments and their analyses on the resiliency against two types of attacks. First, we discuss a class of data injection attacks by focusing on the approach based on mean subsequence reduced (MSR) algorithms and their variants. Agents equipped with such algorithms will ignore their neighbors taking extreme state values. Characterizations on the properties necessary for network topologies and moreover a number of extensions with enhanced resiliency will be established. As the second class of attacks, the effects of denial-of-service (DoS) attacks will be examined in the context of multi-agent consensus. By employing a DoS model based on the energy constraints of the attacker, we will observe that robustness against such attacks may depend on system properties such as dynamics of the individual agents and network structures. Applications of the algorithms will be further discussed for clock synchronization in wireless sensor networks and control of a group of mobile robots., QC 20220718

This paper investigates solving convex composite optimization on an undirected network, where each node, privately endowed with a smooth component function and a nonsmooth one, is required to minimize the sum of all the component functions throughout the network. To address such a problem, a general Approximate Method of Multipliers (AMM) is developed, which attempts to approximate the Method of Multipliers by virtue of a surrogate function with numerous options. We then design the possibly nonseparable, time-varying surrogate function in various ways, leading to different distributed realizations of AMM. We demonstrate that AMM generalizes more than ten state-of-the-art distributed optimization algorithms, and certain specific designs of its surrogate function result in a variety of new algorithms to the literature. Furthermore, we show that AMM is able to achieve an $O(1/k)$ rate of convergence to optimality, and the convergence rate becomes linear when the problem is locally restricted strongly convex and smooth. Such convergence rates provide new or stronger convergence results to many prior methods that can be viewed as specializations of AMM., QC 20230508

In this paper, we analyze the problem of optimally allocating resources in a distributed and privacy-preserving manner. We propose a novel distributed optimal resource allocation algorithm with privacy-preserving guarantees, which operates over a directed communication network. Our algorithm converges in finite time and allows each node to process and transmit quantized messages. Our algorithm utilizes a distributed quantized average consensus strategy combined with a privacy-preserving mechanism. We show that the algorithm converges in finite-time, and we prove that, under specific conditions on the network topology, nodes are able to preserve the privacy of their initial state. Finally, to illustrate the results, we consider an example where test kits need to be optimally allocated proportionally to the number of infections in a region. It is shown that the proposed privacy-preserving resource allocation algorithm performs well with an appropriate convergence rate under privacy guarantees. Copyright, QC 20230309

In this paper we study the problem of signal detection in Gaussian noise in a distributed setting where the local machines in the star topology can communicate a single bit of information. We derive a lower bound on the Euclidian norm that the signal needs to have in order to be detectable. Moreover, we exhibit optimal distributed testing strategies that attain the lower bound., Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public., Statistics

The Conjugate Gradient (CG) method is an iterative solver targeting linear systems of equations Ax=b where A is a symmetric and positive definite matrix. CG convergence properties improve when preconditioning is applied to reduce the condition number of matrix A. While many different options can be found in the literature, the Factorized Sparse Approximate Inverse (FSAI) preconditioner constitutes a highly parallel option based on approximating A-1. This paper proposes the Communication-aware Factorized Sparse Approximate Inverse preconditioner (FSAIE-Comm), a method to generate extensions of the FSAI sparse pattern that are not only cache friendly, but also avoid increasing communication costs in distributed memory systems. We also propose a filtering strategy to reduce inter-process imbalance. We evaluate FSAIE-Comm on a heterogeneous set of 39 matrices achieving an average solution time decrease of 17.98%, 26.44% and 16.74% on three different architectures, respectively, Intel Skylake, Fujitsu A64FX and AMD Zen 2 with respect to FSAI. In addition, we consider a set of 8 large matrices running on up to 32,768 CPU cores, and we achieve an average solution time decrease of 12.59%., Marc Casas is supported by Grant RYC-2017-23269 funded by MCIN/AEI/ 10.13039/501100011033 and by “ESF Investing in your future”. This work has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 955606. This work has been supported by the Computación de Altas Prestaciones VIII (BSC-HPC8) project. It has also been partially supported by the EXCELLERAT project funded by the European Commission’s ICT activity of the H2020 Programme under grant agreement number: 823691 and by the Spanish Ministry of Science and Innovation (Nucleate, Project PID2020-117001GB-I00)., Peer Reviewed, Postprint (author's final draft)

We present a distributed Nash equilibrium seeking method based on the Bregman forward-backward splitting, which allows us to have a mirror mapping instead of the standard projection as the backward operator. Our main technical contribution is to show convergence to a Nash equilibrium when the game has cocoercive pseudogradient mapping. Furthermore, when the feasible sets of the agents are simplices, a suitable choice of a Legendre function results in an exponentiated pseudogradient method, which, in our numerical experience, performs out the standard projected pseudogradient and dual averaging methods., Team Sergio Grammatico, Team Bart De Schutter

In this article, we consider a sequence of transferable utility coalitional games, where the actual coalitional values are unknown but vary within known bounds. As a solution to the resulting family of games, we formalize the notion of 'robust core.' Our main contribution is to design two distributed algorithms, namely 1) distributed payoff allocation and 2) distributed bargaining, which converge to a consensual payoff distribution in the robust core. We adopt an operator-theoretic perspective to show convergence of both algorithms executed on time-varying communication networks. An energy storage optimization application motivates our framework for 'robust coalitional games.', Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public., Team Sergio Grammatico, Team Bart De Schutter

We address the generalized Nash equilibrium seeking problem in a partial-decision information scenario, where each agent can only exchange information with some neighbors, although its cost function possibly depends on the strategies of all agents. The few existing methods build on projected pseudo-gradient dynamics, and require either double-layer iterations or conservative conditions on the step sizes. To overcome both these flaws and improve efficiency, we design the first fully-distributed single-layer algorithms based on proximal best-response. Our schemes are fixed-step and allow for inexact updates, which is crucial for reducing the computational complexity. Under standard assumptions on the game primitives, we establish convergence to a variational equilibrium (with linear rate for games without coupling constraints) by recasting our algorithms as proximal-point methods, opportunely preconditioned to distribute the computation among the agents. Since our analysis hinges on a restricted monotonicity property, we also provide new general results that significantly extend the domain of applicability of proximal-point methods. Besides, our operator-theoretic approach favors the implementation of provably correct acceleration schemes that can further improve the convergence speed. Finally, the potential of our algorithms is demonstrated numerically, revealing much faster convergence with respect to projected pseudo-gradient methods and validating our theoretical findings., Team Sergio Grammatico, Team Bart De Schutter

In this paper, we study the minimum dominating set (MDS) problem and the minimum total dominating set (MTDS) problem. We propose a new idea to compute approximate MDS and MTDS. This new approach can be implemented in a distributed model or parallel model. We also show how to use this new approach in other related problems such as set cover problem and k-distance dominating set problem.

In a recent line of work, Butti and Dalmau have shown that a fixed-template Constraint Satisfaction Problem is solvable by a certain natural linear programming relaxation (equivalent to the basic linear programming relaxation) if and only if it is solvable on a certain distributed network, and this happens if and only if its set of Yes instances is closed under Weisfeiler-Leman equivalence. We generalize this result to the much broader framework of fixed-template Promise Valued Constraint Satisfaction Problems. Moreover, we show that two commonly used linear programming relaxations are no longer equivalent in this broader framework.

Online algorithms make decisions based on past inputs, with the goal of being competitive against an algorithm that sees also future inputs. In this work, we introduce time-local online algorithms; these are online algorithms in which the output at any given time is a function of only T latest inputs. Our main observation is that time-local online algorithms are closely connected to local distributed graph algorithms: distributed algorithms make decisions based on the local information in the spatial dimension, while time-local online algorithms make decisions based on the local information in the temporal dimension. We formalize this connection, and show how we can directly use the tools developed to study distributed approximability of graph optimization problems to prove upper and lower bounds on the competitive ratio achieved with time-local online algorithms. Moreover, we show how to use computational techniques to synthesize optimal time-local algorithms.

We consider the parameterized verification problem for distributed algorithms where the goal is to develop techniques to prove the correctness of a given algorithm regardless of the number of participating processes. Motivated by an asynchronous binary consensus algorithm [James Aspnes, 2002], we consider round-based distributed algorithms communicating with shared memory. A particular challenge in these systems is that 1) the number of processes is unbounded, and, more importantly, 2) there is a fresh set of registers at each round. A verification algorithm thus needs to manage both sources of infinity. In this setting, we prove that the safety verification problem, which consists in deciding whether all possible executions avoid a given error state, is PSPACE-complete. For negative instances of the safety verification problem, we also provide exponential lower and upper bounds on the minimal number of processes needed for an error execution and on the minimal round on which the error state can be covered.

Networked systems of autonomous agents, and applications thereof, often rely on the control primitive of average consensus, where the agents are to compute the average of private initial values. To provide reliable services that are easy to deploy, average consensus should continue to operate when the network is subject to frequent and unpredictable change, and should mobilize few computational resources, so that deterministic, low powered, and anonymous agents can partake in the network. In this stringent adversarial context, we investigate the implementation of average consensus by distributed algorithms over networks with bidirectional, but potentially short-lived, communication links. Inspired by convex recurrence rules for multi-agent systems, and the Metropolis average consensus rule in particular, we design a deterministic distributed algorithm that achieves asymptotic average consensus, which we show to operate in polynomial time in a synchronous temporal model. The algorithm is easy to implement, has low space and computational complexity, and is fully distributed, requiring neither symmetry-breaking devices like unique identifiers, nor global control or knowledge of the network. In the fully decentralized model that we adopt, to our knowledge, no other distributed average consensus algorithm has a better temporal complexity. Our approach distinguishes itself from classical convex recurrence rules in that the agent’s values may sometimes leave their previous convex hull. As a consequence, our convergence bound requires a subtle analysis, despite the syntactic simplicity of our algorithm.

Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems closely related to subgraph detection, mainly focusing on induced subgraph detection. The main line of this work presents lower bounds and parameterized algorithms w.r.t structural parameters of the input graph: - On general graphs, we give unconditional lower bounds for induced detection of cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions from centralized parameterized complexity, we prove lower bounds in CONGEST for detecting patterns with a 4-clique, and for induced path detection conditional on the hardness of triangle detection in the congested clique. - On graphs of bounded degeneracy, we show that induced paths can be detected fast in CONGEST using techniques from parameterized algorithms, while detecting cycles and patterns of treewidth 2 is hard. - On graphs of bounded vertex cover number, we show that induced subgraph detection is easy in CONGEST for any pattern graph. More specifically, we adapt a centralized parameterized algorithm for a more general maximum common induced subgraph detection problem to the distributed setting. In addition to these induced subgraph detection results, we study various related problems in the CONGEST and congested clique models, including for multicolored versions of subgraph-detection-like problems.

Distributed computing is increasingly spreading, in advanced technological applications as well as in our daily life. Failures in distributed algorithms can have important human and financial consequences, so that is is crucial to develop rigorous techniques to verify their correctness. Model checking is a model-based approach to formal verification, dating back the 80’s. It has been successfully applied first to hardware, and later to software verification. Distributed computing raises new challenges for the model checking community, and calls for the development of new verification techniques and tools. In particular, the parameterized verification paradigm is nowadays blooming to help proving automatically the correctness of distributed algorithms. In this invited talk, we present recent parameterized verification developments to automatically prove properties of some classical distributed algorithms.

We study online linear regression problems in a distributed setting, where the data is spread over a network. In each round, each network node proposes a linear predictor, with the objective of fitting the network-wide data. It then updates its predictor for the next round according to the received local feedback and information received from neighboring nodes. The predictions made at a given node are assessed through the notion of regret, defined as the difference between their cumulative network-wide square errors and those of the best off-line network-wide linear predictor. Various scenarios are investigated, depending on the nature of the local feedback (full information or bandit feedback), on the set of available predictors (the decision set), and the way data is generated (by an oblivious or adaptive adversary). We propose simple and natural distributed regression algorithms, involving, at each node and in each round, a local gradient descent step and a communication and averaging step where nodes aim at aligning their predictors to those of their neighbors. We establish regret upper bounds typically in O(T-3/4) when the decision set is unbounded and in O(root T) in case of bounded decision set., QC 20210408

This paper investigates a multi-user wireless powered fog computing (FC) network, where energy-limited wireless sensor devices (WSDs) first harvest energy from a nearby hybrid access point (HAP) and then, compute their tasks locally (i.e., the local computing (LC) mode) or offload the tasks to the HAP (i.e., the FC mode) via a binary offloading policy. An optimization problem is formulated to minimize the transmit power at the HAP by jointly optimizing the time allocation ratio and the computing mode selection vector, under the energy causality constraints and the WSDs computing rate requirements constraints. To efficiently solve the formulated non-convex problem in a distributed manner, an alternating direction method of multipliers (ADMM)-based algorithm is designed. With our presented ADMM-based algorithm, each WSD is able to optimize its computing mode and offloading time with local channel state information (CSI). For comparison, a channel-sorting-based (CSB) centralized algorithm with global CSI is also designed. Simulation results show that the proposed distributed algorithm achieves the comparable performance with the centralized algorithm or by using the exhaustive search one. Moreover, to minimize the transmit power, the WSDs with the better channel quality are inclined to select the LC mode, which is much different from traditional design. IEEE

The issue of dynamic assignment of users to servers is studied widely but the proposed system substantiates the solution for this problem. The system - Dynamic Assignment of users to servers in social networking use community analysis algorithm (CAA) to resolve the extra load that the servers. The proposed system hascapability to keep inter-server communication below required level in distributed environment (Online social network). The assessment of potential servers is made first and then proper assignment is done. CAA calculate communication degree (CD) for each user. On the basis of this CD parameter different communities are formed. This CD will help to relation between communication data. Along with previously mentioned features theproposed system will also provide user data management feature which will keep currently activated users who are linked with same event in one virtual group. In this way the proposed system will bound to give the results which will handle the overload of different distributed servers and also manage user data efficiently in system which will give more convenience to the users as well as to the system.

The issue of dynamic assignment of users to servers is studied widely but the proposed system substantiates the solution for this problem. The system - Dynamic Assignment of users to servers in social networking use community analysis algorithm (CAA) to resolve the extra load that the servers. The proposed system hascapability to keep inter-server communication below required level in distributed environment (Online social network). The assessment of potential servers is made first and then proper assignment is done. CAA calculate communication degree (CD) for each user. On the basis of this CD parameter different communities are formed. This CD will help to relation between communication data. Along with previously mentioned features theproposed system will also provide user data management feature which will keep currently activated users who are linked with same event in one virtual group. In this way the proposed system will bound to give the results which will handle the overload of different distributed servers and also manage user data efficiently in system which will give more convenience to the users as well as to the system.

The issue of dynamic assignment of users to servers is studied widely but the proposed system substantiates the solution for this problem. The system - Dynamic Assignment of users to servers in social networking use community analysis algorithm (CAA) to resolve the extra load that the servers. The proposed system hascapability to keep inter-server communication below required level in distributed environment (Online social network). The assessment of potential servers is made first and then proper assignment is done. CAA calculate communication degree (CD) for each user. On the basis of this CD parameter different communities are formed. This CD will help to relation between communication data. Along with previously mentioned features theproposed system will also provide user data management feature which will keep currently activated users who are linked with same event in one virtual group. In this way the proposed system will bound to give the results which will handle the overload of different distributed servers and also manage user data efficiently in system which will give more convenience to the users as well as to the system.

The issue of dynamic assignment of users to servers is studied widely but the proposed system substantiates the solution for this problem. The system - Dynamic Assignment of users to servers in social networking use community analysis algorithm (CAA) to resolve the extra load that the servers. The proposed system hascapability to keep inter-server communication below required level in distributed environment (Online social network). The assessment of potential servers is made first and then proper assignment is done. CAA calculate communication degree (CD) for each user. On the basis of this CD parameter different communities are formed. This CD will help to relation between communication data. Along with previously mentioned features theproposed system will also provide user data management feature which will keep currently activated users who are linked with same event in one virtual group. In this way the proposed system will bound to give the results which will handle the overload of different distributed servers and also manage user data efficiently in system which will give more convenience to the users as well as to the system.

The issue of dynamic assignment of users to servers is studied widely but the proposed system substantiates the solution for this problem. The system - Dynamic Assignment of users to servers in social networking use community analysis algorithm (CAA) to resolve the extra load that the servers. The proposed system hascapability to keep inter-server communication below required level in distributed environment (Online social network). The assessment of potential servers is made first and then proper assignment is done. CAA calculate communication degree (CD) for each user. On the basis of this CD parameter different communities are formed. This CD will help to relation between communication data. Along with previously mentioned features theproposed system will also provide user data management feature which will keep currently activated users who are linked with same event in one virtual group. In this way the proposed system will bound to give the results which will handle the overload of different distributed servers and also manage user data efficiently in system which will give more convenience to the users as well as to the system.

The issue of dynamic assignment of users to servers is studied widely but the proposed system substantiates the solution for this problem. The system - Dynamic Assignment of users to servers in social networking use community analysis algorithm (CAA) to resolve the extra load that the servers. The proposed system hascapability to keep inter-server communication below required level in distributed environment (Online social network). The assessment of potential servers is made first and then proper assignment is done. CAA calculate communication degree (CD) for each user. On the basis of this CD parameter different communities are formed. This CD will help to relation between communication data. Along with previously mentioned features theproposed system will also provide user data management feature which will keep currently activated users who are linked with same event in one virtual group. In this way the proposed system will bound to give the results which will handle the overload of different distributed servers and also manage user data efficiently in system which will give more convenience to the users as well as to the system.

This dissertation contributes toward design, convergence analysis and improving the performance of the current state of knowledge on central and distributed solutions for in-network optimization algorithms. We investigate how mathematical tools can be utilized to develop and analyze distributed optimization algorithms that respect the restrictions inherent to communication and address computational concerns in smart network operation. The results of this dissertation will facilitate the realization and adoption of optimal in-network solutions in many important applications, such as machine learning, smart grids, robotics, sensor coordination and distributed data regression in different sectors. We develop our results by studying the performance of consensus-based algorithm as a common approach to solve the optimization problems in the decentralized way. We first examine the robustness of a dynamic average consensus algorithm to communication delay over strongly connected and weight-balanced (SCWB) digraphs. For such algorithm, in both its continuous-time and discrete-time implementations, we characterize the admissible communication delay range and study the effect of the delay on the rate of convergence and the tracking error bound. Next, we investigate comprehensive study of a long observed phenomenon of increase in the stability margin and so the rate of convergence of a class of linear systems due to time delay. Using our result, we propose an accelerated algorithm for dynamic and static average consensus problem by using outdated feedback. Such algorithm enables agents over the network to achieve faster agreement on a certain quantity. Our study on optimization algorithm design includes proposing a distributed solution for a constrained convex optimization problem over a network of clustered agents each consists of a set of sub-agents. Our proposed distributed algorithm is a novel continuous-time algorithm that is linked to the augmented Lagrangian approach. We