Applications of Game Theory in Distributed Systems: An Interview with Dr. Daniel Grosu

Hossein Badri

Interviewer: Hossein Badri,
Ph.D. Candidate, Department of Industrial & Systems Engineering,
Wayne State University, Detroit, MI

Dr. Daniel Grosu is an Associate Professor of Computer Science at Wayne State University. He is the director of the "Parallel & Distributed Computing Lab" where he and his team approach problems in parallel and distributed computing systems from different perspectives. One of the main focuses of Dr. Grosu's team is on applications of game theory in distributed systems. He and his team have published dozens of articles in top-tier peer-reviewed conferences and journals. This interview focuses on his group's research on applications of game theory in distributed systems.

Could you please briefly describe your group's research areas?
We focus on a multidisciplinary research area situated at the border between computer science, game theory and economics. More specically, we approach problems in parallel and distributed computing using techniques from game theory and economics. We focus on developing mechanisms for resource management in parallel and distributed systems, auction-based mechanisms for resource allocation in clouds and edge computing systems, mechanisms for resource allocation in competitive real-time environments, and parallel algorithms for solving non-cooperative games.

These days everybody is familiar with Cloud Computing. But what is Edge Computing?
Edge Computing is a distributed computing paradigm that aims at reducing the response time of mobile applications by allowing them to perform their computation at the edge of the network instead of in cloud data centers. 

What are the advantages of this new distributed computing paradigm?
The main advantage of edge computing is the reduction in the response time of applications, but there are other advantages such as reliability. 

From the game theory perspective, what are the main differences between cloud and edge systems?
In edge systems, we have a more competitive environment for users due to the limited capacity of the edge servers compared to the capacity available from cloud data centers. We expect higher competition to acquire quality services in edge computing environments. 

Going back to the game theory applications, what is the main motivation of using auction-based mechanisms in distributed systems?
One of the major challenges in distributed systems, for example edge computing systems, is to decide how to allocate and price edge/cloud resources so that a given systems objective, such as revenue or social welfare, is optimized. One promising approach is to allocate these resources based on auction models, in which users place bids for using a certain amount of resources. When the auction costs are low, as is the case in the context of cloud/edge computing, auctions are especially efficient over the fixed-price markets since resources are allocated to users having the highest valuation.

Could you please give us an example of a project focused on allocating computing resources using auction-based mechanisms?
One of our projects focused on designing auction-based mechanisms for resource allocation in cloud computing systems. One of the major challenges in offering infrastructure as a service (IaaS) to cloud users is designing efficient mechanisms for Virtual Machine (VM) provisioning, allocation, and pricing. Such mechanisms enable cloud providers to effectively utilize their available resources and obtain higher profits. In our setting, we allow users to request bundles of VM instances. We designed truthful greedy mechanisms for the problem such that the cloud provider provisions VMs based on the requests of the winning users and determines their payments. We showed that the proposed greedy mechanisms are truthful, that is, the users do not have incentives to manipulate the system by lying about their requested bundles of VM instances and their valuations. We also designed an incentive-compatible approximation mechanism for the problem or resource allocation and pricing in clouds. The proposed approximation mechanism drives the system into an equilibrium in which the users do not have incentives to manipulate the system by untruthfully reporting their VM bundle requests and valuations. We showed that the proposed approximation mechanism is a PTAS (Polynomial-Time Approximation Scheme) which is by far the strongest approximation result that can be achieved for this problem, unless P = NP.

Any examples of research projects on edge computing systems?
In one of our projects, we addressed the problem of resource allocation and pricing in a two-level edge computing system. In such a system, servers with different capacities are located in the cloud or at the edge of the network. Mobile users compete for these resources and have heterogeneous demands. We designed an auction-based mechanism that allocates and prices edge/cloud resources. We showed that the proposed mechanism is individually rational and produces envy-free allocations.

What is individual-rationality and envy-freeness in this context?
The individual-rationality property guarantees that users are willing to participate in the mechanism, while envy-freeness guarantees that when the auction is finished, no user would be happier with the outcome of another user.

The research projects you just described consider only one service provider. What if we have multiple providers?
Considering multiple providers is very important. The amount of computing resources required by current and future data-intensive applications is expected to increase dramatically, creating high demands for cloud resources. The cloud providers' available resources may not be sufficient enough to cope with such demands. Therefore, the cloud providers need to reshape their business structures and seek to improve their dynamic resource scaling capabilities. Federated clouds offer a practical platform for addressing this service management issue. In one of our project we investigated the problem of forming federations of clouds. We introduced a cloud federation formation game that considers the cooperation of the cloud providers in offering cloud IaaS services. Based on the proposed federation formation game, we designed a cloud federation formation mechanism that enables cloud providers to dynamically form a cloud federation maximizing their profit.

Do you consider the reliability in the formation of cloud federations?
Absolutely. Reliability is a key element in the formation of cloud federations. If a cloud provider agrees to provide some resources in a federation, but it fails to deliver the promised resources, then the application program could not be executed by that federation. Therefore, selecting highly trusted cloud providers to be part of the cloud federation is necessary in order to avoid this problem. In addition, a cloud provider desires to be a member of a cloud federation to obtain high profit. Therefore, a cloud federation formation mechanism should consider both profit and trust among cloud providers when making cloud federation formation decisions. One of our projects investigated the formation of reliable cloud federations.

What is the objective of the cloud federation formation problem?
Usually, the objective is to maximize the individual profit of the cloud providers participating in the federations. You may also consider other objectives, such as, the overall reputation among the cloud providers. 

What is your research group's plan for future research?
In the future, we plan to continue our multidisciplinary research agenda working on topics at the border between computer science, game theory and economics. We plan to focus on the design of energy-aware auction-based mechanisms for application placement in edge/fog computing systems and on the design of randomized approximation mechanisms for resource allocation in such systems. We also plan to develop and investigate stochastic optimization techniques for solving resource allocation and pricing problems in edge/fog computing systems.