In distributed computing systems, to mitigate the adverse effect of stragglers on the computation time, computation redundancy is used. The redundancy can be added proactively at the beginning, or reactively after some time based on the delay pattern of the workers. While most of the existing work with reactive mitigation strategy only considered task replication, we propose a coded reactive straggler mitigation with an uncoded and a coded phase for distributed matrix-matrix multiplications. Specifically, in the uncoded phase of the proposed strategy, the master distributes the computational job without redundancy among the workers. After a predetermined waiting time, the master cancels the remaining tasks. It then encodes the remaining tasks and distributes them among the workers. In the uncoded phase, in addition to the conventional erasure model, where workers can communicate only once, we consider multi-message communication (MMC) model to exploit the partial works done by workers. The optimum waiting time for the uncoded phase and the optimum code rate for the coded phase are also obtained. Our simulation results demonstrate that the proposed coded reactive mitigation significantly decreases the execution time in comparison with both the proactive mitigation strategy or the existing reactive mitigation strategy.

In distributed computing systems, to mitigate the adverse effect of stragglers on the computation time, computation redundancy is used. The redundancy can be added proactively at the beginning, or reactively after some time based on the delay pattern of the workers. While most of the existing work with reactive mitigation strategy only considered task replication, we propose a coded reactive straggler mitigation with an uncoded and a coded phase for distributed matrix-matrix multiplication. Specifically, in the uncoded phase of the proposed reactive strategy, the master distributes the computational job without redundancy among workers and waits for some time. After the waiting time, the master cancels the remaining tasks. It then encodes the remaining tasks and distributes them among the workers that have already completed their computations. The expected execution time of the proposed method is analytically obtained. Furthermore, the optimal waiting time for the uncoded phase and the optimal code rate for the coded phase are investigated. Our simulation results demonstrate that the proposed coded reactive mitigation strategy significantly decreases the execution time in comparison with the proactive mitigation strategy or repetition-based reactive mitigation strategy.

In this paper, we introduce the DRJLRA algorithm, a load and resource allocation scheme based on deep reinforcement learning (DRL) for a generic multi-master, multi-worker coded distributed computing (CDC) system. Our aim is to minimize the combined delay of communication and computation for a set of matrix-vector multiplication tasks. The proposed DRL-based approach has several unique features that set it apart from existing literature. Firstly, it is applicable to general CDC systems with multiple masters and workers. Additionally, it considers multi-task CDC systems with stochastic task arrivals, takes into account the heterogeneity of workers with random computation and communication delays, and utilizes the state-of-the-art soft actor-critic (SAC) DRL algorithm, making it versatile and efficient in handling complex and dynamic CDC environments. Our results demonstrate that DRJLRA outperforms benchmark schemes significantly. It is thus well-suited for real-world CDC systems with diverse and dynamic workloads.

Distributed computing systems have been widely used in recent years to handle massive computations required by newly emerged machine learning algorithms and signal processing problems. In practice, a distributed computing system often receives multiple tasks each needs to be finished by a specific deadline. This necessitates use of a task scheduler which orders and prioritizes tasks executions. In this work, we consider task scheduling for a homogeneous distributed computing system with multiple matrix-vector multiplication jobs, and try to maximize the number of tasks completed before their deadlines. The main challenges in such a system are random task arrivals and random execution times due to the straggling effect. To address these challenges, we propose two task scheduling algorithms namely “simple greedy” and “farsighted greedy” and compare their performance with the ultimate upper bound, i.e., a genie-aided algorithm that knows the exact arrival and execution times of all tasks. Our simulation results demonstrate that the proposed algorithms can approach the performance of the genie-aided algorithm.

Non-binary kernels are used to improve the length flexibility of polar codes. Given the long decoding latency of the successive-cancellation (SC) decoder, devising fast decoding solutions for non-binary kernels is necessary. In this work, we identify a new node in the decoding tree of polar codes which are constructed by commonly used ternary kernels. We call this t-dimensional SPC (tD-SPC) node and propose a low-complexity decoder for it. Moreover, we adapt a node introduced for binary kernel to be used in the fast SC decoding of the 3×3 kernel polar codes. Simulation results show that implementing the proposed fast decoders can reduce the decoding latency by more than 40% if a performance loss of just 0.5 dB is tolerated.

The successive-cancellation list (SCL) and successive-cancellation flip (SCF) decoding can be used to improve the performance of polar codes, especially for short to moderate length codes. However, their serial decoding nature results in significant decoding latencies. Implementing some operations in parallel can reduce their decoding latencies. This paper presents fast implementations of the SCL and SCF decoders. In particular, we propose fast parallel list decoders for five newly identified types of nodes in the decoding tree of a polar code, which significantly improves the decoding latency. We also present novel fast SCF decoders that decode some special nodes in the decoding tree of a polar code without serially computing bit log-likelihood ratios. Using our proposed fast parallel SCF decoders, we observed an improvement up to 81% with respect to the original SCF decoder. This significant reduction in the decoding latency is observed without sacrificing the bit-error-rate performance of the code.

Ultraviolet (UV) communication enables non-line-of-sight (NLOS) outdoor wireless connectivity and is particularly desirable to relax or eliminate pointing and tracking requirements of infrared links. In comparison to infrared counterparts, UV links are subject to relatively higher path loss as well as intersymbol interference resulting from frequency selective nature of the channel. In this paper, we propose the powerful combination of relay-assisted transmission and multi-carrier architecture based on orthogonal frequency division multiplexing (OFDM). Specifically, we consider a cooperative diversity system with orthogonal cooperation protocol and use DC-biased optical OFDM as the underlying physical layer. We consider both amplify-and-forward (AF) and detect-and-forward (DF) relaying. We investigate the error rate performance of the proposed relay-assisted OFDM UV system under consideration and demonstrate performance gains over point-to-point OFDM UV systems. We further determine optimal power allocation schemes to improve the performance. We also propose a variable-rate UV OFDM system and improve system throughput via bit loading.

Strong molecular and aerosol scattering in ultraviolet (UV) wavelengths enable the non-line-of-sight (NLOS) outdoor wireless connectivity which is attractive in many applications due to covertness and security. In the current literature, atmospheric turbulence effects are typically ignored under the assumption of short link distances and clear weather conditions. In this paper, we investigate the performance of multiple-input multiple-output (MIMO) UV systems over turbulence channels. Specifically, we derive bit error rate (BER) expressions over an NLOS UV channel which is modeled as an overlap of two log-normal LOS links. Our results demonstrate that fading variance is scaled by the number of transmitters and receivers and MIMO deployment with proper configurations results in significant BER improvements. Simulation results are further provided to confirm the analytical findings.