Distributed computing enables scalable machine learning by distributing tasks across multiple nodes, but ensuring privacy in such systems remains a challenge. This paper introduces a novelprivate coded distributed computingmodel that integrates privacy constraints to keep task assignments hidden. By leveragingplacement delivery arrays(PDAs), we design an extended PDA framework to characterize achievable computation and communication loads under privacy constraints. By constructing two classes of extended PDAs, we explore the trade-offs between computation and communication, showing that although privacy increases communication overhead, it can be significantly alleviated through optimized PDA-based coded strategies.

Distributed computing methods play a vital role in scalable machine learning as they divide computations across multiple nodes to handle large-scale tasks efficiently. However, maintaining privacy within such systems is a key challenge, particularly for sensitive use cases like federated learning. This paper presents a private coded distributed computing model that incorporates privacy safeguards into distributed computing processes, ensuring that the task allocation of each node remains undisclosed. By leveraging placement delivery arrays (PDAs), the proposed framework introduces a private coding scheme that achieves a balance between computation and communication loads while preserving privacy. We design an extended PDA merging multiple PDAs to formulate the achievable computation and communication loads under privacy constraints.

This paper addresses the challenge of best arm identification in stochastic multi-armed bandit (MAB) models under privacy-preserving constraints, such as in dynamic spectrum access networks where secondary users must privately detect underutilized channels. While previous network security research has explored securing MAB algorithms through techniques such as homomorphic encryption or differential privacy, these methods often suffer from high computational overhead or introduce noise that strictly decreases accuracy. In contrast, this work focuses on lightweight solutions that ensure data confidentiality without compromising the accuracy of best arm identification. We introduce two secure protocols that leverage additive secret sharing and threshold secret sharing. The proposed model, employing aggregation nodes and a comparator node, securely distributes computations to prevent any entity from accessing complete reward or ranking data. Furthermore, the protocol ensures resistance to collusion and fault tolerance, while maintaining computational efficiency. These contributions establish a scalable and robust framework for privacy-preserving best arm identification, offering practical and secure solutions that use MAB methods for network security.

This paper explores the multi-access distributed computing (MADC) model, a novel distributed computing framework where mapper and reducer nodes are distinct entities. Unlike traditional MapReduce frameworks, MADC leverages coding-theoretic techniques to minimize communication overhead without necessitating file replication across mapper nodes. We introduce a new approach utilizing combinatorial designs, specifically t-designs, to construct efficient coding schemes that achieve a computation load of 1. By establishing a connection between t-designs and MapReduce Arrays, we characterize the achievable communication loads and demonstrate the flexibility of our method in selecting the number of reducer nodes. The proposed scheme significantly reduces the number of reducer nodes relative to existing combinatorial topology schemes, at the expense of increased communication cost.

A novel distributed computing model calledMulti-access Distributed Computing (MADC)was recently introduced in the literature. The MADC models with Combinatorial Topology (CT) were studied, where there are A mapper nodes andK= (Λ α) reducer nodes with each reducer node connected to distinct α mapper nodes. In this paper, we represent MADC models via 2-layered bipartite graphs called Map-Reduce Graphs (MRGs) and a set of arrays called Map-Reduce Arrays (MRAs). The connection between MRAs and MRGs is established, thereby exploring new topologies and providing coded shuffling schemes for the MADC models with MRGs using the structure of MRAs. A novelNearest Neighbor Connect-MRG (NNC-MRG)is explored and a coding scheme is provided for MADC models with NNC-MRG. Moreover, CT is generalized to Generalized Combinatorial-MRG (GC-MRG). A set ofg–regular MRAs is provided which corresponds to the existing scheme for MADC models with CT and extended those to generate another set of MRAs to represent MADC models with GC-MRG. One of the major limitations of the existing scheme for CT is that it requires an exponentially large number of reducer nodes and input files for large Λ. This can be overcome by representing CT by MRAs, where coding schemes can be derived even if some of the reducer nodes are not present. Another way of tackling this is by using a different MRG, specifically NNC-MRG, where the number of reducer nodes and files required are significantly smaller compared to CT.

We consider two critical aspects of security in thedistributed computing (DC)model:secure data shufflingandsecure coded computing. It is imperative that any external entity overhearing the communication does not gain any information about theintermediate values (IVs)exchanged during the shuffling phase of the DC model. Our approach ensures IV confidentiality during data shuffling. Moreover, each node in the system must be able to recover the IVs necessary for computing its output functions but must also remain oblivious to the IVs associated with output functions not assigned to it. We design secure DC methods and establish achievable limits on the tradeoffs between the communication and computation loads to contribute to the advancement of secure data processing in distributed systems. First, we establish that the computation and communication loads stay the same as for non-secure data shuffling. However, implementing secure data shuffling requires additional overhead for storing secret keys at the nodes. Next, we show that for secure coded computation, both the computation and communication loads increase compared to the non-secure scenario, along with the overhead for storing secret keys. Finally, we extend our security results to a novel distributed computing model known asmulti-access distributed computing (MADC), which was recently introduced. The MADC model features two distinct sets of nodes, namelymapperandreducernodes. Unlike the original setting where mapper and reducer nodes were the same, in this model, they are separate entities, and each reducer node is connected to multiple mapper nodes. We show that, for MADC models also, computation and communication loads remain the same with or without secure data shuffling. However, secure coded computation results in increased computation and communication loads compared to the non-secure case, and both scenarios require overhead for storing secret keys at the reducer nodes.

This paper studies the shuffling phase in a distributed computing model with rate-limited links between nodes. Each node is connected to all other nodes via a noiseless broadcast link with a finite capacity. For this network, the shuffling phase is described as a distributed index-coding problem to extend an outer bound for the latter to the distributed computing problem. An inner bound on the capacity region is also established by using the distributed composite-coding scheme introduced for the distributed index-coding problem. We consider some special cases of the distributed computing problem through two examples for which we prove that the inner and outer bounds agree, thereby establishing the capacity regions. We, then, generalize the special cases to any number of nodes and computation loads under certain constraints.

A novel distributed computing model called Multi-access Distributed Computing (MADC) was recently introduced in [B. Federico and P. Elia, “Multi-Access Distributed Computing,” June 2022, [online] Available: http://www.arXiv:2206.12851]. The MADC models with Combinatorial Topology (CT) were studied, where there are$\Lambda$mapper nodes and$\dot{K}=\binom{\lambda}{\alpha}$reducer nodes with each reducer node connected to distinct$\alpha$mapper nodes. In this paper, we represent MADC models via 2-layered bipartite graphs called Map-Reduce Graphs (MRGs), and a set of arrays called Map-Reduce Arrays (MRAs) inspired from the Placement Delivery Arrays (PDAs) used in the coded caching literature. The connection between MRAs and MRGs is established, thereby providing coded shuffling schemes for the MADC models using the structure of MRAs. Moreover, a set of$g$-regular MRAs is provided which corresponds to the existing scheme for MADC models with CT. One of the major limitations of the existing scheme for CT is that it requires an exponentially large number of reducer nodes for large$\Lambda$. This can be overcome by representing CT by MRAs, where coding schemes can be derived even if some of the reducer nodes are not present.

In this paper we consider multi-access coded caching problem introduced by Hachem et.al., where each user has access to$L$neighboring caches in a cyclic wrap-around fashion. We focus on the deterministic schemes for a specific class of multi-access coded caching problem based on the concept of PDA. We construct new PDAs which specify the delivery scheme for the specific class of multi-access coded caching problem discussed in this paper. For the proposed scheme, the coding gain is larger than that of the state-of-the-art while the sub-packetization level varies only linearly with the number of users. Hence, the advantage of the proposed scheme is two-fold, in terms of the coding gain as well as the sub-packetization level.

A variant of the index coding problem (ICP), the embedded index coding problem (EICP) was introduced in [A. Porter and M. Wootters, "Embedded Index Coding," ITW, Sweden, 2019] which was motivated by its application in distributed computing where every user can act as sender for other users and an algorithm for code construction was reported. The construction depends on the computation of minrank of a matrix, which is computationally intensive. In [A.A. Mahesh, N. S. Karat and B. S. Rajan, "Min-rank of Embedded Index Coding Problems," ISIT, 2020], the authors have provided an explicit code construction for a class of EICP - Consecutive and Symmetric Embedded Index Coding Problem (CS-EICP). We introduce the idea of sub-packetization of the messages in index coding problems to provide a novel code construction for CSEICP in contrast to the scalar linear solutions provided in the prior works. For CS-EICP, the normalized rate, which is defined as the number of bits transmitted by all the users together normalized by the total number of bits of all the messages, for our construction is lesser than the normalized rate achieved by Mahesh et al., for scalar linear codes.

Coding theoretic techniques have been proposed for synchronous Gradient Descent (GD) on multiple servers to mitigate stragglers. These techniques provide the flexibility that the job is complete when any k out of n servers finish their assigned tasks. The task size on each server is found based on the values of k and n. However, it is assumed that all the n jobs are started when the job is requested. In contrast, we assume a tiered system, where we start with n1≥ k tasks, and on completion of c tasks, we start n2- n1more tasks. The aim is that as long as k servers can execute their tasks, the job gets completed. This paper exploits the flexibility that not all servers are started at the request time to obtain the achievable task sizes on each server. The task sizes are in general lower than starting all n2tasks at the request times thus helping achieve lower task sizes which helps to reduce both the job completion time and the total server utilization.

A new variant of index coding problem termed as Pliable Index Coding Problem (PICOD) is formulated in [S. Brahma, C. Fragouli, "Pliable index coding", IEEE Transactions on Information Theory, vol. 61, no. 11, pp. 6192-6203, 2015]. In PICOD, we consider a server holding a set of messages and there is a set of clients having a subset of messages with them. Each client is satisfied if it receives any of the message which it doesn't have. We discuss the class of PICOD where the side information is consecutive. We provide index codes for two cases - for the class where each client gets exactly one desired message and for a class where total number of messages decoded by the effective clients is maximized. Another variant of index coding problem is - c-Constrained Pliable Index Coding Problem [Linqi Song, Christina Fragouli and Tianchu Zhao, "A Pliable Index Coding Approach to Data Shuffling," arXiv:1701.05540v3 [cs.IT] 3 May 2018]. It is basically PICOD with a c-constraint, i.e, each message is decoded by at most c clients demanding that message. We provide index codes for some classes of this variant with consecutive side information.

For index coding problems with special structure on the side-information graphs called Interlinked Cycle (IC) structures index codes have been proposed in the literature (C. Thapa, L. Ong, and S. Johnson, "Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques", in IEEE Trans. Inf. Theory, vol. 63, no. 6, Jun. 2017 with a correction in "Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques", in arxiv (arxiv:1603.00092v2 [cs.IT] 25 Feb 2018)). In this paper we consider a generalization of IC structures called IC structures with interlocked outer cycles. For IC structures with interlocked outer cycles we show that the optimal length (also known as the minrank of the index coding problem) depends on the maximum number of disjoint outer cycles. We give two sufficient conditions such that if any of these is satisfied then we provide explicit optimal index code construction. The conditions mentioned above are shown to be not necessary by an explicit example.