Skip to main content
Thesis defences

PhD Oral Exam - Syed Eqbal Alam, Concordia Institute for Information Systems Engineering

Communication-efficient Distributed Multi-resource Allocation


Date & time
Tuesday, October 5, 2021 (all day)
Cost

This event is free

Organization

School of Graduate Studies

Contact

Dolly Grewal

Where

Online

When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.

Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.

Abstract

Distributed resource allocation arises in many application domains such as smart cities, intelligent transportation systems, sharing economy, cloud computing, edge-computing, power systems, etc. In several scenarios, the agents such as Internet of Things (IoT) devices may require multiple shared resources to achieve social optimum values; furthermore, they may have heterogeneous resource demands. Such distributed resource allocation problems are challenging to solve, especially when the agents are constrained through communication infrastructure, computational capabilities, or do not wish to communicate with other agents in the network due to privacy reasons.

In the available distributed solutions for multiple resources, best to my knowledge, agents exchange their information with at least one neighboring agent that may incur communication overhead or compromise agents' privacy. We develop several solutions to solve such problems for multiple divisible and multiple indivisible resources wherein no inter-agent communication required. Moreover, we assume that each agent has private cost functions coupled with multiple resources; these functions are strictly convex, twice continuously differentiable, and increasing in each variable. Our first contribution is the stochastic distributed algorithm that solves multi-resource allocation problems with no direct agent-to-agent communication for divisible resources; moreover, it achieves social-optimum values. In the algorithms, each agent decides its resource demands locally, and an agent is unaware of the resource allocations of other agents. We solve the divisible multi-resource allocation problem by extending the additive-increase multiplicative-decrease (AIMD) algorithm for single resource allocation by Wirth and co-authors. In the algorithm, the agents keep increasing the demands for a resource linearly until they receive a one-bit signal from a central agency. The central agency broadcasts the signal whenever one of the allocated resources reaches its capacity. Agents then respond to this signal in a probabilistic manner to decrease the resource demand. By doing so, the social optimum is achieved in long-term averages. Our second contribution is the stochastic algorithm for multiple indivisible (unit-demand) resources, inspired by classical stochastic approximation techniques. Each agent's consumption is modeled as a Bernoulli random variable in the solution, and no inter-agent communication is required. Moreover, we provide fundamental guarantees of convergence. Additionally, we present an example illustrating the performance of the algorithm.

Our third contribution is a derandomized AIMD algorithm to solve a class of distributed optimization problems for multiple divisible shared resources. The algorithm is a derandomized version of the stochastic additive-increase and multiplicative-decrease (AIMD) algorithm. The developed solution uses a one-bit feedback signal for each resource between the system and the agents, and it does not require inter-agent communication. 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 derandomized AIMD algorithm converges faster than the stochastic AIMD algorithm, and both approaches provide approximately the same solutions.

Our fourth contribution is that we study the development of Internet-of-Things (IoT) enabled 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 resources to another community in a prosumer market. We propose a stochastic algorithm to regulate the number of prosumers in a prosumer community; each prosumer has a cost function coupled through its time-averaged production and consumption of the resource.

Furthermore, each prosumer runs its distributed algorithm and takes (binary) decisions in a probabilistic way, whether to produce one unit of the resource or not and to consume one resource unit or not. In the developed approach, prosumers do not explicitly exchange information with each other due to privacy reasons but little with a central agency. Additionally, prosumers achieve the optimal values asymptotically.

Back to top

© Concordia University