We consider the setting of a Master server, M, who possesses confidential data (e.g., personal, genomic or medical data) and wants to run intensive computations on it, 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 and not revealed to the individual workers. Some of the workers may be stragglers, e.g., slow or busy, and will take a random time to finish the task assigned to them. We are interested in reducing the delays experienced by the Master. We focus on linear computations as an essential operation in many iterative algorithms such as principal component analysis, support vector machines and other gradient-descent based algorithms. A classical solution is to use a linear secret sharing scheme, such as Shamir’s scheme, to divide the data into secret shares on which the workers can perform linear computations. However, classical codes can provide straggler mitigation assuming a worst-case scenario of a fixed number of stragglers. We propose a solution based on new secure codes, called Staircase codes, introduced previously by two of the authors. Staircase codes 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. For systems with any number of stragglers, we derive an expression that can give the exact distribution, and the mean, of the waiting time of the Master. We show that Staircase codes always outperform classical secret sharing codes.

@article{rawad, title = {Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes}, author = {Bitar, Rawad and Parag, Parimal and Rouayheb, Salim El}, url = {https://cni.iisc.ac.in/assets/publications/Minimizing-Latency-for-Secure-Coded-Computing........pdf}, doi = {10.1109/TCOMM.2020.2988506}, year = {2020}, date = {2020-04-17}, journal = {IEEE Transactions on Communications}, pages = {1}, keywords = {Journal}, pubstate = {published}, tppubtype = {article} }

The performance of large-scale distributed compute systems is adversely impacted by stragglers when the execution time of a job is uncertain. To manage stragglers, we consider a multi-fork approach for job scheduling, where additional parallel servers are added at forking instants. In terms of the forking instants and the number of additional servers, we compute the job completion time and the cost of server utilization when the task processing times are assumed to have a shifted exponential distribution. We use this study to provide insights into the scheduling design of the forking instants and the associated number of additional servers to be started. Numerical results demonstrate orders of magnitude improvement in cost in the regime of low completion times as compared to the prior works.

@article{Ajay, title = {Optimal Server Selection for Straggler Mitigation}, author = {Badita, Ajay and Parag, Parimal and Aggarwal, Vaneet}, url = {https://cni.iisc.ac.in/assets/publications/Optimal-Server-Selection-for-Straggler-Mitigation.pdf}, doi = {10.1109/TNET.2020.2973224}, year = {2020}, date = {2020-04-01}, journal = {IEEE/ACM Transactions on Networking}, volume = {28}, pages = {709-721}, keywords = {Journal}, pubstate = {published}, tppubtype = {article} }

We consider a scenario of broadcasting information over a network of nodes connected by noiseless communication links. A source node in the network has some data packets to broadcast. It encodes these data packets into n coded packets in such a way that any node in the network that receives any k out of the n coded packets will be able to retrieve all the original data packets. The source transmits the n coded packets to its one-hop neighbours. Every other node in the network follows a probabilistic forwarding protocol, in which it forwards a previously unreceived packet to all its neighbours with a certain probability p. We say that the information from the source undergoes a “near-broadcast” if the expected fraction of nodes that receive at least k of the n coded packets is close to 1. The forwarding probability p is chosen so as to minimize the expected total number of transmissions needed for a near-broadcast. We study how, for a given k, this minimum forwarding probability and the associated expected total number of packet transmissions varies with n. We specifically analyze the probabilistic forwarding of coded packets on two network topologies: binary trees and square grids. For trees, our analysis shows that for fixed k, the expected total number of transmissions increases with n. On the other hand, on grids, a judicious choice of n significantly reduces the expected total number of transmissions needed for a near-broadcast. Behaviour similar to that of the grid is also observed in other well-connected network topologies such as random geometric graphs and random regular graphs

@article{Vinay, title = {Probabilistic forwarding of coded packets on networks}, author = {Kumar, B. R. Vinay and Kashyap, N.}, url = {https://cni.iisc.ac.in/assets/publications/Probabilistic-Forwarding-of-Coded-Packets-on-Networks.pdf}, year = {2020}, date = {2020-02-11}, journal = {IEEE/ACM Transactions on Networking}, keywords = {Journal}, pubstate = {published}, tppubtype = {article} }

Real-time decision making relies on the availability of accurate data and, therefore, delivering status updates in a timely fashion is of paramount importance. The topic of realtime status updates has received much attention in recent years. This article contributes new results to this research area by studying the interplay between average timeliness and design decisions made at the physical layer, for unreliable communication channels. Specifically, this study explores the tension between the fact that more reliable transmissions with lower probabilities of decoding failure tend to improve timely delivery, unless these improvements come at the expense of significantly longer codewords. The average timeliness is adopted as an evaluation criterion, and a framework to efficiently compute the performance of various transmission schemes for the binary erasure channel is developed. We show that the average timeliness decreases as we increase the feedback rate in a hybrid ARQ scheme for a range of codeword lengths. This article also provides design guidelines for the codeword length selection for an hybrid ARQ scheme to improve the average information timeliness. Numerical examples are included to further illustrate the applicability of our findings.

@article{Sarat, title = {Real-Time Status Updates with Perfect Feedback over Erasure Channels}, author = {Bobbili, Sarat Chandra and Parag, Parimal and Chamberland, Jean-Francois}, url = {https://cni.iisc.ac.in/assets/publications/Real-Time-Status-Updates-with-Perfect-Feedback.pdf}, doi = {10.1109/TCOMM.2020.3006224}, year = {2020}, date = {2020-07-01}, journal = {IEEE Transactions on Communications }, pages = {1-1}, keywords = {Journal}, pubstate = {published}, tppubtype = {article} }

This paper is on a coverage estimation procedure for the deployment of outdoor Internet of Things (IoT). In the first part of the paper, a data-driven coverage estimation technique is proposed. The estimation technique combines multiple machine-learning-based regression ideas. The proposed technique achieves two purposes. The first purpose is to reduce the bias in the estimated received signal strength arising from estimations performed only on the successfully received packets. The second purpose is to exploit commonality of physical parameters, e.g. antenna-gain, in measurements that are made across multiple propagation environments. It also provides the correct link function for performing a nonlinear regression in our communication systems context. In the second part of the paper, a method to use readily available geographic information system (GIS) data (for classifying geographic areas into various propagation environments) followed by an algorithm for estimating received signal strength (which is motivated by the first part of the paper) is proposed. Together they enable quick and automated estimation of coverage in outdoor environments. It is anticipated that these will lead to faster and more efficient deployment of outdoor Internet of Things.

@article{1, title = {Coverage Estimation in Outdoor Heterogeneous Propagation Environments}, author = {Rathod, Nihesh and Subramanian, Renu and Sundaresan, Rajesh}, pdf = {Coverage-Estimation-in-Outdoor-Heterogeneous-Propagation-Environments-1.pdf}, doi = {10.1109/ACCESS.2020.2972811}, year = {2016}, date = {2020-02-10}, journal = {IEEE Access}, volume = {8}, pages = {31660 – 31673}, keywords = {Conference}, pubstate = {published}, tppubtype = {article} }