Edge computing is emerging as a new paradigm to allow processing data near the edge of the network, where the data is typically generated and collected. This enables critical computations at the tactical edge in applications such as Internet of Battlefield Things (IoBT), in which an increasing number of devices (sensors, cameras, health monitoring devices, etc.) collect data that needs to be processed through computationally intensive algorithms with stringent reliability, security and latency constraints. Our key tool is the theory of coded computation, which advocates mixing data in computationally intensive tasks by employing erasure codes and offloading these tasks to other devices for computation. Coded computation is recently gaining interest, thanks to its higher reliability, smaller delay, and lower communication costs. In this paper, we develop a private and rateless adaptive coded computation (PRAC) algorithm by taking into account (i) the privacy requirements of IoBT applications and devices, and (ii) the heterogeneous and time-varying resources of edge devices. We show that PRAC outperforms known secure coded computing methods when resources are heterogeneous. We provide theoretical guarantees on the performance of PRAC and its comparison to baselines. Moreover, we confirm our theoretical results through simulations.
We consider the setting of a master server who possesses confidential data (genomic, medical data, etc.) and wants to run linear regression on this data, as part of a machine learning algorithm for example. The master wants to distribute these computations to untrusted workers who have volunteered or are incentivized to help with this task. However, the data must be kept private (in an information theoretic sense) and not revealed to the individual workers. The workers may be busy and will take a random time to finish the task assigned to them. We are interested in reducing the aggregate delay experienced by the master. A known solution is to use a linear secret sharing scheme to divide the data into secret shares on which the workers can compute. However, classical codes can provide straggler mitigation assuming a worst-case scenario of a fixed number of stragglers. We introduce a new family of codes called Staircase codes that allow flexibility in the number of stragglers up to a given maximum, and universally achieve the information theoretic limit on the download cost by the Master, leading to latency reduction. Under the shifted exponential model, we find upper and lower bounds on the Master's mean waiting time. We derive the distribution of the Master's waiting time, and its mean, for systems with up to two stragglers. We show that Staircase codes always outperform classical secret sharing codes. For instance, Staircase codes can lead to up to $59%$ reduction in delay compared to classical secret sharing codes. We validate our results with extensive implementation on Amazon EC2 clusters.
Blockchain offers the ability to create distributed databases that can be trusted, even if some actors on the network may be malicious. We consider the problem of reducing the read overhead of a ledger built using blockchains as part of the IDASH 2018 competition. In this scenario, we have multiple nodes granted to access a server. The goal is to store the activity logs of the nodes accessing the server in a secure fashion, using a blockchain-based ledger. To increase search speed, we propose splitting the ledger into groups based on expected search terms, and storing each group on a separate blockchain. By doing so, a search for all records of a specific type is transformed from a linear search on all records, to a linear search on a small subset of records. In our solution, this increases search efficiency by a factor of 8, at the cost of increasing storage overhead by a factor of 4. The system can be adjusted based on what types of searches are expected to reduce this overhead.