5 May 2022 in IEEE/ACM Transactions on Networking
Miners in a blockchain system are suffering from ever-increasing storage costs, which in general have not been properly compensated by the users’ transaction fees. This reduces the incentives for the miners’ participation and may jeopardize the blockchain security. To mitigate this blockchain insufficient fee issue, we propose a Fee and Waiting Tax (FWT) mechanism, which explicitly considers the two types of negative externalities in the system. Specifically, we model the interactions between the protocol designer, users, and miners as a three-stage Stackelberg game. By characterizing the equilibrium of the game, we find that miners neglecting the negative externality in transaction selection cause they are willing to accept insufficient-fee transactions. This leads to the insufficient storage fee issue in the existing protocol (i.e., deployed in Bitcoin and Ethereum). Moreover, our proposed optimal FWT mechanism can motivate users to pay sufficient transaction fees to cover the storage costs and achieve the unconstrained social optimum. Numerical results show that the optimal FWT mechanism guarantees sufficient transaction fees and achieves an average social welfare improvement of 51.43% or more over the existing protocol. Furthermore, the optimal FWT mechanism reduces the average waiting time of low-fee transactions and all transactions by 68.49% and 61.56%, respectively.
1 December 2019 in Performance Evaluation
10 October 2022 in IEEE Journal on Selected Areas in Communications
Directed Acyclic Graph (DAG) is a popular approach to achieve scalability of blockchain networks. Due to its high efficiency in data communication and great scalability, DAG has been widely adopted in many applications such as Internet of Things (IoT) and Decentralized Finance (DeFi). DAG-based blockchain, nevertheless, faces the key challenge of transaction inclusion collision due to the high concurrency and the network delay. Particularly, the transaction inclusion collision in DAG-based blockchain leads to the revenue and throughput dilemmas, which would greatly degrade the system performance. In this paper, we propose “TIPS”, the Transaction Inclusion Protocol with Signaling, which broadcasts a signal indicating the transactions in the block. We show that with the prompt broadcast of a signal, TIPS substantially reduces the transaction collision and thus resolves these dilemmas. Moreover, we show that TIPS can defend against both the denial-of-service and the delay-of-service attacks. We also conduct intensive experiments to demonstrate the superior performance of the proposed protocol.
27 February 2023 in Proceedings of the ACM on Measurement and Analysis of Computing Systems
Gacha game is a special opaque selling approach, where the seller is selling gacha pulls to the buyer. Each gacha pull provides a certain probability for the buyer to win the gacha game reward. The gacha game has been enthusiastically embraced in numerous online video games and has a wide range of potential applications.In this work, we model the complex interaction between the seller and the buyer as a Stackelberg game, where the sequential decision of the buyer is modeled as a Markov Decision Process (MDP). We define the whale property in the context of gacha games. Then, we show that this is the necessary condition to achieve optimal revenue. Moreover, we provide the revenue-optimal gacha game design and show that it is equivalent to the single-item single-bidder Myerson auction.We further explore two popular multi-item gacha games, namely, the sequential multi-item gacha game and the banner-based multi-item gacha game. We also discuss the subsidies in the gacha game and demonstrate how subsidies may encourage the buyer to engage in grinding behavior. Finally, we provide a case study on blockchain systems as gacha games.
9 February 2024 in IEEE/ACM Transactions on Networking
Multi-user delay-constrained scheduling is a crucial challenge in various real-world applications, such as wireless communication, live streaming, and cloud computing. The scheduler must make real-time decisions to guarantee both delay and resource constraints simultaneously, without prior information on system dynamics that can be time-varying and challenging to estimate. Additionally, many practical scenarios suffer from partial observability issues due to sensing noise or hidden correlation. To address these challenges, we propose a deep reinforcement learning (DRL) algorithm called Recurrent Softmax Delayed Deep Double Deterministic Policy Gradient ( $\mathtt{RSD4}$ ) (https://github.com/hupihe/RSD4), which is a data-driven method based on a Partially Observed Markov Decision Process (POMDP) formulation. $\mathtt{RSD4}$ guarantees resource and delay constraints by Lagrangian dual and delay-sensitive queues, respectively. It also efficiently handles partial observability with a memory mechanism enabled by the recurrent neural network (RNN). Moreover, it introduces user-level decomposition and node-level merging to support large-scale multihop scenarios. Extensive experiments on simulated and real-world datasets demonstrate that $\mathtt{RSD4}$ is robust to system dynamics and partially observable environments and achieves superior performance over existing methods.
17 May 2021 in IEEE Journal on Selected Areas in Communications
A distributed machine learning platform needs to recruit many heterogeneous worker nodes to finish computation simultaneously. As a result, the overall performance may be degraded due to straggling workers. By introducing redundancy into computation, coded machine learning can effectively improve the runtime performance by recovering the final computation result through the first k (out of the total n) workers who finish computation. While existing studies focus on designing efficient coding schemes, the issue of designing proper incentives to encourage worker participation is still under-explored. This paper studies the platform's optimal incentive mechanism for motivating proper workers' participation in coded machine learning, despite the multi-dimensional incomplete information about heterogeneous workers' computation performances and costs. A key contribution of this work is to summarize workers' multi-dimensional heterogeneity as a one-dimensional metric, which guides the platform's efficient selection of workers under incomplete information with a linear computation complexity. Although the exact overall runtime is intractable, we characterize the platform's (asymptotically) optimal load assignment to heterogeneous workers in coded machine learning. When the platform has incomplete information about workers' costs, it is optimal to assign loads only based on workers' computation performances; when the platform further lacks workers' computation performance information, it is optimal to design the loads to be cost-dependent and performance-dependent.