Computationally efficient & Economically efficient Agent-based Fog Computing

Professor Benjamin Kwang Mong Sim is a pioneer and a leading researcher in Agent-based Fog Computing and intelligent resource management in fog and edge

Earliest work: Aside from being the first to coin the terms "Agent-based Fog Computing" , "Fog Commerce", "intelligent fog", and "intelligent edge", Professor Sim is the first to develop a family of computationally efficient and economically efficient agent-based techniques for bolstering resource discovery, resource selection, and resource pricing in fog computing.

Mathematical rigor: Computational complexity analyses validate that Sim's algorithms for bolstering resource discovery, resource selection, and resource pricing in fog computing have either logarithmic complexity or linear complexity. Extensive game-theoretic analyses in two journal papers in Dynamic Games and Applications and Computational Economics validate that the Sim bargaining mechanism for pricing fog computing resources is 1) incentive-compatible (i.e., it provides incentives that motivate all agents in a fog resource market to behave in a manner consistent with the optimal solution), 2) strongly group strategyproof  (i.e., it is strongly resistant to collusion), and 3) shill resistant (i.e., it is not susceptible to identity faking for illicit trading). Additionally, game-theoretic analysis in another journal paper validates that the Sim bargaining solution for pricing fog computing resources posses the same set of desirable properties as the famous bargaining solution developed by Nobel Laureate John Nash. 

Significance: Since fog nodes are light-weight resources (i.e., they are small-scale computer systems), computational efficiency is a critical property of fog resource allocation algorithms. Given the ease to collude for manipulating resource prices and to fake identities in Internet environments,  the Sim bargaining mechanism, being both strongly group strategyproof and shill resistant, is indispensable for resource pricing in fog computing. The Sim bargaining mechanism is highly desirable because being  incentive-compatible, it motivates fog agents to behave in a manner consistent with the optimal solution.

Interdisciplinarity: Agent-based fog computing is an interdisciplinary research spanning the areas of fog computing, computational complexity, multiagent systems, bargaining theory, and mechanism design,  culminating in the publication of the research results in this project in both 1) journals in the field of computer science such as IEEE Transactions on Services Computing, IEEE Transactions on Computational Social Systems, and IEEE Letters of the Computer Society and 2) journals in the field of game theory and economics such as Dynamic Games and Applications and Computational Economics

Technical Contributions

1. Economically-efficient and Computationally-efficient Fog Price Bargaining: Professor Sim is the first to introduce bargaining as an economic mechanism for pricing fog computing resources and he is the first to devise a bargaining theory and NUMEROUS NOVEL bargaining mechanisms that are specific to fog resource pricing.

1)     Pareto optimality (PAR) (i.e., the solution is best for all agents)

2)     Symmetry (SYM) (i.e., the solution is fair to all agents)

3)     Scale invariance (INV) (i.e., different scales and different methods can be used to measure agents’ level of satisfaction without affecting the solution)

4)     Independence of irrelevant alternatives (IIA) (i.e., reducing the search space by eliminating irrelevant alternatives does not affect the solution).

By showing that the Sim Bargaining Solution has exactly the same set of highly desirable properties as the Nash Bargaining Solution, the Sim’s Fog Bargaining Theory provides the guiding principles for fog computing designers to implement economically-efficient fog resource pricing mechanisms.

2. Computationally-efficient and Scalable Fog Resource Discovery: Professor Sim is the first to develop computationally-efficient and scalable agent-based techniques for bolstering resource discovery in fog computing. 

1)    Computational efficiency: Mathematical evidence validates that the KM-gossip algorithm is computationally efficient since it has logarithmic time complexity and the number of cycles needed to propagate each resource request to all nodes in a fog network is logarithmic in the number of nodes in the network.

2)     Scalability: The KM-gossip algorithm is scalable because with growing numbers of fog nodes and IoT devices, more broker agents can be added to facilitate larger-scale information dissemination.

3)     Cooperative and parallel information dissemination: The KM-gossip algorithm is designed to enable many different broker agents to work together by relying on each other to disseminate resource request to different sets of fog nodes. At each information dissemination cycle, multiple broker agents carry out parallel dissemination of each resource request by simultaneously propagating each resource request to different groups of fog nodes.

4)     Generalization: The KM-gossip algorithm is a generalization of the gossip algorithm. In the KM-gossip algorithm, at every information dissemination cycle, each agent disseminates information to a group of M agents. If M equals one, the KM-gossip algorithm reduces to the gossip algorithm. In the gossip algorithm, at every information dissemination cycle, each agent disseminates information to one agent.

5)     Low overhead: Empirical results show that the family of KM-gossip algorithms generates significantly much lower overhead than closely related algorithms.

3. Computationally-efficient Fog Resource Selection: Professor Sim devised a reasoning technique for bolstering fog resource selection by enabling agents to reason about the similarities between user requirements and resource profiles. He provided mathematical proofs to validate that his similarity reasoning technique is computationally efficient because it has linear time complexity.

4. Survey and Tutorial: Professor Sim is the first to contribute an IEEE Transactions survey-tutorial paper on intelligent resource management in fog computing and edge computing. In his survey-tutorial paper, he provides readers with the foundational knowledge for devising intelligent fog and intelligent edge agents by 1) explicating the key difference between fog computing and edge computing, and between fog computing and cloud computing, 2) explaining why developing agents for fog resource management is more challenging than developing cloud agents, 3) suggesting the desirable properties of fog agents, and 4) providing clear and detailed expositions of the state-of-the-art agent-based techniques for intelligent resource management in fogs and edges.

Publications

1. K. M. Sim. A Strongly Group Strategyproof and Shill Resistant Bargaining Mechanism for Fog Resource PricingDynamic Games and Applications (2024), Springer. https://doi.org/10.1007/s13235-023-00550-7  Click here for a view-only version of this paper provided by Springer Nature SharedIT link.  

2. K. M. Sim.  An Incentive-Compatible and Computationally Efficient Fog Bargaining Mechanism. Computational Economics Volume 62, issue 4, December (2023), pages 1883 - 1918. https://doi.org/10.1007/s10614-022-10324-9   Click here for a view-only version of this paper provided by Springer Nature SharedIT link

3. K. M. Sim. Cooperative and Parallel Fog Discovery and Pareto Optimal Fog Commerce Bargaining. IEEE Transactions on Computational Social Systems, Vol.15, No. 2, pp.1157 - 1174, March-April, 2022. Click here to download preprint.

4.  K. M. Sim. Intelligent Resource Management in Intercloud, Fog, and Edge: Tutorial and New DirectionsIEEE Transactions on Services Computing. Early access. DOI:10.1109/TSC.2020.2975168. Click here to download preprint.

5. K. M. Sim. Agent-based Fog Computing: Gossiping, Reasoning, and Bargaining. IEEE Letters of the Computer Society. Volume: 1 , Issue: 2 , Jul.-Dec. 2018, pages 21-24. DOI: 10.1109/LOCS.2018.2886828. Click here to download preprint.

6. K. M. Sim. A Computationally Efficient Bargaining Mechanism for Fog Commerce. IEEE Letters of the Computer Society. Volume: 2 , Issue: 1 , Jan.-Mar. 2019, pages 5-8. DOI: 10.1109/LOCS.2019.2906156. Click here to download preprint.