Degree Type


Date of Award


Degree Name

Master of Science


Computer Science


Computer Science

First Advisor

Wensheng Zhang


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).


Copyright Owner

Xiaojuan Ma



File Format


File Size

60 pages

Available for download on Tuesday, December 07, 2021