## 3 The Design of _HeaLow_ and Implementation
### Offloading Decision Process in Availability Checker
#### 3.4.2 The Case When a Device Processes the Device's Workload  
In _HeLow_, a device prefers to process the device's workload by itself than to request one of neighbors to process the data. However, the device may not be able to finish the processing by the workload's deadline for various reasons, such as low computing power. In such situations, the device should offload the workload to a neighbor device and request the neighbor to process the workload. _HeLow_ makes best effort to finish the processing by the deadline. If it cannot, it offloads or removes the workload. Thus, before starting the processing, the device should be able to predict whether the device can finish the processing by the deadline or not.  
When a new workload is created, the device decides whether the workload is inserted into the work queue or offloaded to another neighbor. At this moment, suppose that there are \(x\) workloads in the work queue. In this situation, the device checks whether the device is able to finish processing the new workload by the deadline or not, based on Inequality (1) when the device is the \(i\)-th device. In Inequality (1), \(ft\_bw_{x}^{i}\) means the time to finish processing \(x\)-th buffered workload in \(i\)-th device's work queue, and \(dl\_wl_{new}^{i}\) indicates the deadline time of the new workload, \(wl_{new}^{i}\). As we explained before, \(ns\_wl_{new}^{i}\log ns\_wl_{new}^{i}\) is the amount of computation for processing \(wl_{new}^{i}\).  
\[ft\_bw_{x}^{i}+\frac{ns\_wl_{new}^{i}\log ns\_wl_{new}^{i}}{r_{proc}^{i}} \leq dl\_wl_{new}^{i}. \tag{1}\]  
However, in practical situations, the operation of processing buffered workloads can be delayed unexpectedly, as shown in Figure 2. If such unexpected events occur so that the device cannot finish processing the new workload by the deadline, the workload should be offloaded to another  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Notation/Variable (Unit)** & **Description** \\ \hline \(wl_{n}^{i}\) & \(i\)-th device’s \(n\)-th workload \\ \(pw_{t}\) & The processed workload of \(wl_{n}^{i}\) \\ \(dl\_wl_{n}^{i}\) & The deadline time of \(wl_{n}^{i}\) \\ \(ns\_wl_{n}^{i}\) & The number of samples in \(wl_{n}^{i}\) \\ \(ft\_bw_{x}^{i}\) & The finish time of processing \(x\)-th buffered workload in \(i\)-th device’s work queue \\ \(buf_{t}^{i}\) & The amount of buffered workload at time \(t\) (KB) \\ \(si\_wl_{n}^{i}\) & The data size of \(wl_{n}^{i}\) (KB) \\ \(si\_pw_{n}^{i}\) & The data size of \(pw_{n}\) (KB) \\ \(r_{tran}^{i}\) & The transmission rate of \(i\)-th device (KB/s) \\ \(r_{proc}^{i}\) & The processing rate of \(i\)-th device (The number of samples per second) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Notations and variables used for _HeLow_.  
neighbor, \(j\), and the processing result of the workload should be returned to the device by the deadline. Thus, in addition to Inequality (1), another condition, Inequality (2), should also be considered.  
\[ft\_bw_{x}^{i}+\frac{si\_wli_{new}^{i}}{r_{trans}^{i}}+\frac{ns\_wli_{new}^{i}\log ns \_wli_{new}^{i}}{r_{proc}^{j}}+\frac{si\_pwi_{new}^{i}}{r_{trans}^{i}}\leq dl\_ wli_{new}^{i}. \tag{2}\]  
In Inequality (2), \(pwi_{new}^{i}\) is the processed workload of \(wl_{new}^{i}\), and \(si\_pwi_{new}^{i}\) means the size of \(pwi_{new}^{i}\). We named this approach _buffer length management_ in _HeaLow_.  
If Inequalities (1) and (2) are valid, the device finally puts the new workload into the work queue to process the workload by itself, and then the number of buffered workloads becomes \(x+1\). After that, the time to finish processing all the buffered workloads is reset as follows:  
\[ft\_bw_{x+1}^{i}=ft\_bw_{x}^{i}+\frac{ns\_wli_{new}^{i}\log ns\_wli_{new}^{i}} {r_{proc}^{i}}. \tag{3}\]  
If either Inequality (1) or Inequality (2) is not valid, the device offloads the workload to one of neighbors.