Degree Type

Thesis

Date of Award

2021

Degree Name

Master of Science

Department

Computer Science

Major

Computer Science

First Advisor

Wensheng Zhang

Abstract

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

DOI

https://doi.org/10.31274/etd-20210609-116

Copyright Owner

Xiaojuan Ma

Language

en

File Format

application/pdf

File Size

60 pages

Available for download on Tuesday, December 07, 2021

Share

COinS