Collaborative Coded Computation Offloading: An All-pay Auction Approach

The increasing sensing capabilities of Internet of Things (IoT) devices such as smart meters and smartphones, coupled with reliable wireless communication technologies, have enabled the development of crowdsensing applications, which leverage large-scale data for analysis. The IoT devices upload the data collected by the on-board sensors to the cloud server for analysis. Through deep learning techniques, the cloud server aims to build accurate decision-making models for smart city applications, such as estimation of road conditions [1], air quality monitoring [2] and tracking of medical conditions [3].

However, as the number of IoT devices increases rapidly, the cloud server may not be able to handle the ever-expanding datasets individually. Edge computing [4] has become a promising approach that extends cloud computing services to the edge of the networks. Specifically, by leveraging on the computational capabilities, e.g., Central Processing Unit (CPU) power, of the edge devices, e.g., base stations, the cloud server can offload its computation tasks to the edge devices. Instead of offloading the entire computation to a single edge device, the cloud server can divide the large datasets into smaller sets and distribute them to the edge devices for processing. This alleviates the bottleneck and single point of failure problems. Upon completing the allocated computation subtasks, the edge devices return the computed results to the cloud server for aggregation to reconstruct the final result.

To perform the distributed computation tasks efficiently, coded distributed computing [5] is being increasingly used to mitigate the straggler effects caused by factors such as imbalanced work allocation, contention of shared resources and network congestion [6, 7].

In this paper, we consider that a cloud server, i.e., master, aims to build a prediction model in which the training process involves a large number of matrix multiplication computations. Matrix multiplication is an important operation underlying many data analytics applications, e.g., machine learning, scientific computing and graph processing [8]. Due to a lack of computational capabilities and storage resources, the resource-constrained master employs edge devices, i.e., workers, to facilitate the distributed computation task. First, the master uses polynomial codes [8] to determine the algebraic structure of the encoded submatrices and distributes them to the workers. Then, the workers perform local computations based on their allocated datasets, and return the computed results to the master. The master reconstructs the final result by using fast polynomial interpolation algorithms such as the Reed-Solomon decoding algorithm [9].

However, there is no incentive for the workers to participate in or to complete their allocated distributed computation tasks. To design an appropriate incentive mechanism, it is important to consider the unique aspect of the coded distributed computing framework. Specifically, even though workers are allocated a subset of the entire dataset for computations, some of the workers may perform computations without any compensation if their computed results are not used. As such, we propose an all-pay auction to improve worker participation. In traditional auctions such as first-price and second-price auctions, only the winners of the auctions pay. In contrast, in all-pay auctions, regardless of whether the bidders win or lose, they are required to pay. In this all-pay auction, the bids of the workers are represented by the CPU power, i.e., the number of CPU cycles, allocated by the workers to complete the computation tasks. In other words, the larger the CPU power allocated, the higher the bid of the worker.

There are two advantages of an all-pay auction [10]. Firstly, it reduces the probability of non-completion of allocated tasks. This differs from traditional auctions in which the winners of the auctions can still choose not to complete their tasks and give up the reward that is promised by the auctioneer. As a result, the auctioneer needs to conduct another round of auction to meet its objectives. Secondly, it reduces the coordination cost between the auctioneer and the bidders. Specifically, in traditional auctions, the participants need to bid then contribute whereas in all-pay auctions, the bids of the participants are directly determined by their contributions. In other words, the participants do not need to bid explicitly in all-pay auctions.

We consider a master-worker setup in a heterogeneous distributed computing network. The system model consists of a master, e.g., cloud server and a set $\mathcal{I}=\{1,\ldots,i,\ldots,I\}$ of $I$ workers, e.g., edge devices such as base stations, which have different computational capabilities. In crowdsensing, for example, the ubiquity of the IoT devices as well as their on-board sensing and processing capabilities are leveraged to collect data for many innovative crowdsensing applications, e.g., weather prediction, location-based recommendation and forensic analysis. Given the large amount of sensor data collected from different IoT devices, the master aims to perform training of the machine learning algorithm to complete a user-defined task. As the number of IoT devices that contribute to the crowdsensing task increases, so does the size of the dataset that the master needs to handle. However, the master may not have sufficient resources, i.e., computation power to handle the growing dataset. Instead, it may utilize the resources of the workers to collaboratively complete the distributed computation tasks.

One of the main challenges in performing distributed computation tasks is the straggler effects. Coding techniques such as polynomial codes [8] can be used to mitigate straggler effects by reducing the recovery threshold, i.e., the number of workers that need to submit their results for the master to reconstruct the final result. In order to perform distributed coded matrix multiplication computations, i.e., $\mathbf{C}=\mathbf{A}^{\top}\mathbf{B}$ where $\mathbf{A}$ and $\mathbf{B}$ are input matrices, $\mathbf{A}\in\mathbb{F}_{q}^{s\times r}$ and $\mathbf{B}\in\mathbb{F}_{q}^{s\times t}$ for integers $s$, $r$, and $t$ and a sufficiently large finite field $\mathbb{F}_{q}$, there are four important steps:

1. 1.

   Task Allocation: Given that all workers are able to store up to $\frac{1}{m}$ fraction of matrix $\mathbf{A}$ and $\frac{1}{n}$ fraction of matrix $\mathbf{B}$, the master divides the input matrices into submatrices $\mathbf{\tilde{A}}_{i}=f_{i}(\mathbf{A})$ and $\mathbf{\tilde{B}}_{i}=g_{i}(\mathbf{B})$, $\forall i\in\mathcal{I}$, where $\mathbf{\tilde{A}}_{i}\in\mathbb{F}_{q}^{s\times\frac{r}{m}}$ and $\mathbf{\tilde{B}}_{i}\in\mathbb{F}_{q}^{t\times\frac{r}{n}}$ respectively. Specifically, $\mathbf{f}$ and $\mathbf{g}$ represent the vectors of functions such that $\mathbf{f}=(f_{1},\ldots,f_{i},\ldots,f_{I})$ and $\mathbf{g}=(g_{1},\ldots,g_{i},\ldots,g_{I})$, respectively. Then, the master distributes the submatrices to the workers over the wireless channels for computations.

2. 2.

   Local Computation: Each worker $i$ is allocated submatrices $\mathbf{\tilde{A}}_{i}$ and $\mathbf{\tilde{B}}_{i}$ by the master. Based on the allocated submatrices, the workers perform matrix multiplication, i.e., $\mathbf{\tilde{A}}_{i}^{\top}\mathbf{\tilde{B}}_{i}$, $\forall i\in\mathcal{I}$.

3. 3.

   Wireless Transmission: Upon completion of the local computations, the workers transmit the computed results, i.e., $\mathbf{\tilde{C}}_{i}=\mathbf{\tilde{A}}_{i}^{\top}\mathbf{\tilde{B}}_{i}$ to the master over the wireless communication channels.

4. 4.

   Reconstruction of Final Result: By using polynomial codes, the master is able to reconstruct the final result upon receiving $K$ out of $I$ computed results by using decoding functions. In other words, the master does not need to wait for all $I$ workers to complete the computation task. Note that although there is no constraint on the decoding functions to be used with polynomial codes, a low-complexity decoding function ensures the efficiency of the overall matrix multiplication computations.

In our system model, we consider the computations for distributed matrix multiplication. However, there are other types of distributed computation problems, e.g., stochastic gradient descent, convolution and Fourier transform. The matrix multiplication may also involve more than two matrices. Our system model can be easily extended to solve the matrix multiplication of more than two matrices and different computation problems.

By using polynomial codes [8], the optimum recovery threshold that can be achieved where each worker is able to store up to $\frac{1}{m}$ of matrix $\mathbf{A}$ and $\frac{1}{n}$ of matrix $\mathbf{B}$ is defined as:

However, there is no incentive for the workers to be one of the $K$ workers to complete their local computations and return their computed results to the master. The workers may not want to participate in the distributed computation tasks or perform to the best of their abilities. For example, the workers may not allocate large CPU power for the coded distributed tasks, resulting in longer time needed to complete the computation tasks. In order to incentivize the workers to allocate more CPU power to complete the allocated computation tasks, we adopt an all-pay auction approach to determine the rewards to the workers while maximizing the utility of the master.

In this section, we present the design of an all-pay auction that incentivizes the workers to allocate more CPU power for the allocated computation subtasks. In this auction, the master is the auctioneer whereas the workers are the bidders. The bid of a worker is represented by the CPU power that it allocates for its computation subtasks. In this all-pay auction, all $I$ workers, i.e., bidders, pay their bids regardless of whether they win or lose the auction.

Each worker $i$ knows its own valuation, $v_{i}$ but does not know the valuation of any other worker, $i^{\prime}\neq i$. This establishes a one-dimensional incomplete information setting. In addition, if each worker has a different unit cost of computational energy which is only known to itself, we consider the two-dimensional incomplete information setting. The dimension of private information can be reduced following the procedure in [12]. In this work, we consider a one-dimensional incomplete information setting where the unit cost of computational energy is the same for all workers but the workers’ valuations are heterogeneous and private.

Given the utility of worker $i$, $\alpha_{i}$ in Equation (4), the objective of worker $i$ to maximize its expected utility, $u_{i}$, is defined as follows:

where $p_{i}^{k}$ is the winning probability of reward $M_{k}$ by worker $i$.

Although the worker does not know exactly the valuations of other workers, it knows the distribution of the other workers’ valuations based on past interactions, which is a common knowledge to all workers and the master. In our model, we consider that all the workers’ valuations are drawn from the same distribution, which constitutes a symmetric Bayesian game where the prior is the distribution of the workers’ valuations.

The subscript $i^{\prime}$ represents the index of other workers other than worker $i$. Specifically, $\mathbf{z}_{i^{\prime}}^{*}=(z_{1}^{*},z_{2}^{*},\ldots,z_{i-1}^{*},z_{i+1}^{*},\ldots,z_{I}^{*})$ represents the equilibrium CPU power allocations of all other workers other than CPU power allocation of worker $i$. At Bayesian Nash equilibrium, given the belief of worker $i$, $\forall i\in\mathcal{I}$ about the valuations and that the CPU powers allocated by other workers, $i^{\prime}$ where $i\neq i^{\prime}$ are at equilibrium, $\mathbf{z}^{*}_{i^{\prime}}$, worker $i$ aims to maximize its expected utility.

Since the equilibrium CPU power allocation of worker $i$, which is represented by $z_{i}^{*}$, is a strictly monotonically increasing function of its valuation $v_{i}^{*}$, we express the equilibrium strategy of worker $i$ as a function represented by $\beta(\cdot)$, i.e., $z_{i}^{*}=\beta_{i}(v_{i})$. Given the strict monotonicity, the inverse function also exists where $v_{i}(\cdot)=\beta_{i}^{-1}(\cdot)$ and it is an increasing function. Due to the incomplete information setting, the objective of worker $i$ to maximize its expected utility in Equation (5) can be expressed as follows:

where the cost of worker $i$ is represented by the function $c(\cdot)=\theta\kappa a(\beta(v_{i}))^{2}$.

Since the workers are symmetric, i.e., the valuations of workers are drawn from the same distribution, the symmetric equilibrium strategy for each worker $i$, $\forall i\in\mathcal{I}$ can be derived. We first assume that there are $I$ rewards, where $M_{1}\geq M_{2}\geq\cdots\geq M_{K}>M_{K+1}=M_{K+2}=\cdots=M_{I}=0$. The valuations of the workers, $v_{1},\ldots,v_{i},\ldots,v_{I}$ are ranked and represented by its order statistics, which are expressed as $v_{1:I}\geq v_{2:I}\geq\cdots\geq v_{I:I}$. In particular, $v_{k:I}$ represents the $k$-th highest valuation among the $I$ valuations which are drawn from the common distribution $F(v)$. Given the order statistics of the workers’ valuations, $\forall i\in\mathcal{I}$, the corresponding cumulative distribution function and probability density function are represented by $F_{k:I}$ and $f_{k:I}$ respectively. Similarly, when dealing with the valuations of all workers, other than that of worker $i$, the order statistic is represented by $v_{k:I-1}$, which represents the $k$-th highest valuation among the $I-1$ valuations. The corresponding cumulative distribution function and probability density function are represented by $F_{k:I-1}$ and $f_{k:I-1}$ respectively.

Given that other workers $i^{\prime}$, where $i^{\prime}\neq i$, follow a symmetric, increasing and differentiable equilibrium strategy $\beta(\cdot)$, worker $i$ will never choose to allocate a CPU power greater than the equilibrium strategy given the highest valuation. In other words, worker $i$ will never allocate $z_{i}>\beta(\bar{v})$. Besides, the optimal strategy of the worker with lowest valuation $\underline{v}$ is not to allocate any CPU power. On one hand, when the number of rewards offered is smaller than the number of workers, i.e., $K<I$, the worker with lowest valuation $\underline{v}$ will not win any reward. On the other hand, when the number of rewards offered is larger than or equal the number of workers, i.e., $K\geq I$, the worker with lowest valuation $\underline{v}$ will win a reward without allocating any CPU power. Hence, $u_{i}({\underline{v}})=0$. With this, the expected utility of worker $i$ with valuation $v_{i}$ and CPU power allocation $z_{i}=\beta(v_{i})$ is expressed as follows:

since $M_{k+1}=\cdots=M_{I-1}=M_{I}=0$, $F_{0:I-1}(z_{i})\equiv 0$ and $F_{I:I-1}(z_{i})\equiv 1$.

By differentiating Equation (7) with respect to the variable $w_{i}$ and equating the result to zero, we obtain the following:

When maximized, the marginal value of the reward is equivalent to the marginal cost of the CPU power. Since we have the differentiated function $c^{\prime}(\cdot)$, the function $c(\cdot)$ can be found by using the integral of Equation (8). At equilibrium, when the expected utility of worker $i$, $\forall i\in\mathcal{I}$, is maximized, we have the following:

Thus the equilibrium strategy for worker $i$ with valuation $v_{i}$, $\forall i\in\mathcal{I}$, is expressed as:

Given the equilibrium strategy of worker $i$, $\forall i\in\mathcal{I}$, the master aims to maximize its expected utility, $\pi$. By using the polynomial codes, the master is able to reconstruct the final result by using the computed results from $K$ workers. Since the master spends the fixed reward $\sigma$ completely, the maximization problem in Equation (2) is equivalent to maximizing the allocation of CPU power, which is expressed as follows:

Since the equilibrium strategy of worker $i$, $\forall i\in\mathcal{I}$, is affected by the reward structure, the master needs to determine the structure of the rewards such that it maximizes the CPU power allocation of the workers, thereby maximizing its own utility, $\pi$.

Given that the master spends the total amount of the reward, $\sigma$, the design of the optimal reward sequence is important to maximize the CPU power allocation of the workers since the equilibrium strategies of the workers depend on the differences between consecutive rewards.

The master needs to first decide whether to allocate the total amount of reward, $\sigma$ to only one winner, i.e., winner-take-all reward structure, or to split the reward into several smaller rewards.

Since the winner-take-all reward structure is not optimal, the master is better off offering multiple rewards. Given that $K$ rewards are offered, the master can consider several reward sequences such as (i) homogeneous reward sequence, (ii) arithmetic reward sequence and (iii) geometric reward sequence. Specifically, the reward sequence is expressed as follows:

• •

  Homogeneous reward sequence: $M_{k}=M_{k+1}$,

• •

  Arithmetic reward sequence: $M_{k}-M_{k+1}=\gamma$, $\gamma>0$,

• •

  Geometric reward sequence: $M_{k+1}=\eta M_{k}$, $0\leq\eta\leq 1$,

where $\gamma$ and $\eta$ are constants.

In the next section, we show the effects of different reward structures on the allocation of CPU powers by the workers.

In this section, we evaluate the all-pay auction mechanism. Table I summarizes the simulation parameters. With normalization, we consider the total amount of reward $\sigma$ to be $1$, i.e., $\sigma=\sum_{k=1}^{K}M_{k}=1$. We also set $m=n=2$ (see “Task Allocation” step in Section II).

In this paper, we proposed an all-pay auction to incentivize workers to participate in the coded distributed computation tasks. Firstly, we use polynomial codes to determine the number of rewards to be offered in the all-pay auction. Then, the master determines the reward structure to maximize its utility given the strategies of the workers. For our future work, we can consider workers with valuations chosen from different probability distributions.