Speaker:Xiaojuan Ma

Adaptive Fund Allocation for Game-based Verifiable Computation Outsourcing

Hiring a trusted third party (TTP) with a small probability to re-execute outsourced tasks is an efficient way for a client to ensure the correctness of the results returned by an untrusted cloud server. A deposit from the server is required before the execution and will be taken away as a penalty if the server is caught misbehaving; the emerging blockchain system has made this mechanism easier to implement. The allocation of the client's total budget and the server's deposit among a set of tasks highly affects the probability of hiring a TTP, the latency for confirming the results and the wage earned by the server. In this thesis, we develop algorithms that efficiently allocate the fund (budget and deposit) to meet different requirements (low latency, high wage, high profit-deposit ratio, etc.). To be specific, we propose: (1) an optimal fund allocation algorithm for the fixed budget and fixed deposit scenario; (2) an adaptive approximate algorithm (AA) with an error bound; (3) an algorithm based on binary search and AA to decide a proper deposit given a target profit-deposit ratio; and (4) accurate (dynamic programming based) and approximate (reinforcement learning-based) algorithms for the more general scenario when the budget is not fixed and the client has a hybrid goal (involving both budget and latency).

Committee: Wensheng Zhang (major professor), Ying Cai, and Carl Chang

Join on WebEx: https://iastate.webex.com/iastate/j.php?MTID=m04f894e03019630b3ba819436…