-
Near-optimal Differentially Private Client Selection in Federated Settings
Authors:
Syed Eqbal Alam,
Dhirendra Shukla,
Shrisha Rao
Abstract:
We develop an iterative differentially private algorithm for client selection in federated settings. We consider a federated network wherein clients coordinate with a central server to complete a task; however, the clients decide whether to participate or not at a time step based on their preferences -- local computation and probabilistic intent. The algorithm does not require client-to-client inf…
▽ More
We develop an iterative differentially private algorithm for client selection in federated settings. We consider a federated network wherein clients coordinate with a central server to complete a task; however, the clients decide whether to participate or not at a time step based on their preferences -- local computation and probabilistic intent. The algorithm does not require client-to-client information exchange. The developed algorithm provides near-optimal values to the clients over long-term average participation with a certain differential privacy guarantee. Finally, we present the experimental results to check the algorithm's efficacy.
△ Less
Submitted 13 October, 2023;
originally announced October 2023.
-
A Communication-efficient Local Differentially Private Algorithm in Federated Optimization
Authors:
Syed Eqbal Alam,
Dhirendra Shukla,
Shrisha Rao
Abstract:
Federated optimization, wherein several agents in a network collaborate with a central server to achieve optimal social cost over the network with no requirement for exchanging information among agents, has attracted significant interest from the research community. In this context, agents demand resources based on their local computation. Due to the exchange of optimization parameters such as sta…
▽ More
Federated optimization, wherein several agents in a network collaborate with a central server to achieve optimal social cost over the network with no requirement for exchanging information among agents, has attracted significant interest from the research community. In this context, agents demand resources based on their local computation. Due to the exchange of optimization parameters such as states, constraints, or objective functions with a central server, an adversary may infer sensitive information of agents. We develop a differentially-private additive-increase and multiplicative-decrease algorithm to allocate multiple divisible shared heterogeneous resources to agents in a network. The developed algorithm provides a differential privacy guarantee to each agent in the network. The algorithm does not require inter-agent communication, and the agents do not need to share their cost function or their derivatives with other agents or a central server; however, they share their allocation states with a central server that keeps track of the aggregate consumption of resources. The algorithm incurs very little communication overhead; for m heterogeneous resources in the system, the asymptotic upper bound on the communication complexity is O(m) bits at a time step. Furthermore, if the algorithm converges in K time steps, then the upper bound communication complexity will be O(mK) bits. The algorithm can find applications in several areas, including smart cities, smart energy systems, resource management in the sixth generation (6G) wireless networks with privacy guarantees, etc. We present experimental results to check the efficacy of the algorithm. Furthermore, we present empirical analyses for the trade-off between privacy and algorithm efficiency.
△ Less
Submitted 19 October, 2023; v1 submitted 3 April, 2023;
originally announced April 2023.
-
Optimal Regulation of Prosumers and Consumers in Smart Energy Communities
Authors:
Syed Eqbal Alam,
Dhirendra Shukla
Abstract:
In smart energy communities, households of a particular geographical location make a cooperative group to achieve the community's social welfare. Prosumers are the users that both consume and produce energy. In this paper, we develop stochastic and distributed algorithms to regulate the number of consumers and the number of prosumers with heterogeneous energy sources in the smart energy community.…
▽ More
In smart energy communities, households of a particular geographical location make a cooperative group to achieve the community's social welfare. Prosumers are the users that both consume and produce energy. In this paper, we develop stochastic and distributed algorithms to regulate the number of consumers and the number of prosumers with heterogeneous energy sources in the smart energy community. In the community, each prosumer has one of the heterogeneous energy sources such as solar photovoltaic panels or wind turbines installed in their household. The prosumers and consumers decide in a probabilistic way when to be active. They keep their information private and do not need to share it with other prosumers or consumers in the community. Moreover, we consider a central server that keeps track of the total number of active prosumers and consumers and sends feedback signals in the community at each time step; the prosumers and consumers use these signals to calculate their probabilistic intent. We present experimental results to check the efficacy of the algorithms. We observe that the average number of times prosumers and consumers are active reaches the optimal value over time, and the community asymptotically achieves the social optimum value.
△ Less
Submitted 28 December, 2022; v1 submitted 25 June, 2022;
originally announced June 2022.
-
Multi-resource allocation for federated settings: A non-homogeneous Markov chain model
Authors:
Syed Eqbal Alam,
Fabian Wirth,
Jia Yuan Yu
Abstract:
In a federated setting, agents coordinate with a central agent or a server to solve an optimization problem in which agents do not share their information with each other. Wirth and his co-authors, in a recent paper, describe how the basic additive-increase multiplicative-decrease (AIMD) algorithm can be modified in a straightforward manner to solve a class of optimization problems for federated s…
▽ More
In a federated setting, agents coordinate with a central agent or a server to solve an optimization problem in which agents do not share their information with each other. Wirth and his co-authors, in a recent paper, describe how the basic additive-increase multiplicative-decrease (AIMD) algorithm can be modified in a straightforward manner to solve a class of optimization problems for federated settings for a single shared resource with no inter-agent communication. The AIMD algorithm is one of the most successful distributed resource allocation algorithms currently deployed in practice. It is best known as the backbone of the Internet and is also widely explored in other application areas. We extend the single-resource algorithm to multiple heterogeneous shared resources that emerge in smart cities, sharing economy, and many other applications. Our main results show the convergence of the average allocations to the optimal values. We model the system as a non-homogeneous Markov chain with place-dependent probabilities. Furthermore, simulation results are presented to demonstrate the efficacy of the algorithms and to highlight the main features of our analysis.
△ Less
Submitted 24 May, 2021; v1 submitted 26 April, 2021;
originally announced April 2021.
-
Derandomized Distributed Multi-resource Allocation with Little Communication Overhead
Authors:
Syed Eqbal Alam,
Robert Shorten,
Fabian Wirth,
Jia Yuan Yu
Abstract:
We study a class of distributed optimization problems for multiple shared resource allocation in Internet-connected devices. We propose a derandomized version of an existing stochastic additive-increase and multiplicative-decrease (AIMD) algorithm. The proposed solution uses one bit feedback signal for each resource between the system and the Internet-connected devices and does not require inter-d…
▽ More
We study a class of distributed optimization problems for multiple shared resource allocation in Internet-connected devices. We propose a derandomized version of an existing stochastic additive-increase and multiplicative-decrease (AIMD) algorithm. The proposed solution uses one bit feedback signal for each resource between the system and the Internet-connected devices and does not require inter-device communication. Additionally, the Internet-connected devices do not compromise their privacy and the solution does not dependent on the number of participating devices. In the system, each Internet-connected device has private cost functions which are strictly convex, twice continuously differentiable and increasing. We show empirically that the long-term average allocations of multiple shared resources converge to optimal allocations and the system achieves minimum social cost. Furthermore, we show that the proposed derandomized AIMD algorithm converges faster than the stochastic AIMD algorithm and both the approaches provide approximately same solutions.
△ Less
Submitted 21 December, 2018;
originally announced December 2018.
-
Distributed Algorithms for Internet-of-Things-enabled Prosumer Markets: A Control Theoretic Perspective
Authors:
Syed Eqbal Alam,
Robert Shorten,
Fabian Wirth,
Jia Yuan Yu
Abstract:
Internet-of-Things (IoT) enables the development of sharing economy applications. In many sharing economy scenarios, agents both produce as well as consume a resource; we call them prosumers. A community of prosumers agrees to sell excess resource to another community in a prosumer market. In this chapter, we propose a control theoretic approach to regulate the number of prosumers in a prosumer co…
▽ More
Internet-of-Things (IoT) enables the development of sharing economy applications. In many sharing economy scenarios, agents both produce as well as consume a resource; we call them prosumers. A community of prosumers agrees to sell excess resource to another community in a prosumer market. In this chapter, we propose a control theoretic approach to regulate the number of prosumers in a prosumer community, where each prosumer has a cost function that is coupled through its time-averaged production and consumption of the resource. Furthermore, each prosumer runs its distributed algorithm and takes only binary decisions in a probabilistic way, whether to produce one unit of the resource or not and to consume one unit of the resource or not. In the proposed approach, prosumers do not explicitly exchange information with each other due to privacy reasons, but little exchange of information is required for feedback signals, broadcast by a central agency. In the proposed approach, prosumers achieve the optimal values asymptotically. Furthermore, the proposed approach is suitable to implement in an IoT context with minimal demands on infrastructure. We describe two use cases; community-based car sharing and collaborative energy storage for prosumer markets. We also present simulation results to check the efficacy of the algorithms.
△ Less
Submitted 25 March, 2019; v1 submitted 18 December, 2018;
originally announced December 2018.
-
Distributed Multi-resource Allocation with Little Communication Overhead
Authors:
Syed Eqbal Alam,
Robert Shorten,
Fabian Wirth,
Jia Yuan Yu
Abstract:
We propose a distributed algorithm to solve a special distributed multi-resource allocation problem with no direct inter-agent communication. We do so by extending a recently introduced additive-increase multiplicative-decrease (AIMD) algorithm, which only uses very little communication between the system and agents. Namely, a control unit broadcasts a one-bit signal to agents whenever one of the…
▽ More
We propose a distributed algorithm to solve a special distributed multi-resource allocation problem with no direct inter-agent communication. We do so by extending a recently introduced additive-increase multiplicative-decrease (AIMD) algorithm, which only uses very little communication between the system and agents. Namely, a control unit broadcasts a one-bit signal to agents whenever one of the allocated resources exceeds capacity. Agents then respond to this signal in a probabilistic manner. In the proposed algorithm, each agent is unaware of the resource allocation of other agents. We also propose a version of the AIMD algorithm for multiple binary resources (e.g., parking spaces). Binary resources are indivisible unit-demand resources, and each agent either allocated one unit of the resource or none. In empirical results, we observe that in both cases, the average allocations converge over time to optimal allocations.
△ Less
Submitted 6 November, 2017;
originally announced November 2017.