The problem of clock synchronization is studied in an arbitrary network ${\mathcal{G}} = ({\mathcal{V}},{\mathcal{E}})$ with $|{\mathcal{V}}|$ server nodes and $|{\mathcal{E}}|$ edges. Every pair of adjacent servers has a time discrepancy (edge information) that is only known approximately to one or both of the two adjacent servers. A master node aims to coordinate the otherwise independent clocks of the servers by eliminating the loop-wise offset surplus in the network. The goal is to minimize the communication cost between server nodes and the master node. Optimal schemes are found for the two cases where each time discrepancy is known by 1) both adjacent servers, and 2) only one of the adjacent servers. Notably, the scheme for the first case is robust to a straggler (slow or failed server). An algorithm that outperforms the natural (uncoded) baseline is proposed for the general setting that is a mix of the two cases. Classes of such mixed setting are identified where the algorithm represents the optimal solution.

DNA, with remarkable properties of high density and stability, particularly for long-term data archiving, is one of the most appealing storage media. Emerging DNA storage technologies use composite DNA letters, where information is represented by a probability vector, leading to higher information density and lower synthesizing cost than single DNA letters. However, it faces the problem of inevitable noise and information corruption. This paper studies the channel of composite DNA letters in DNA storage and block codes for symmetric limited-magnitude errors on probability vectors. We provide outer and inner bounds for limited-magnitude probability error correction codes. Moreover, we propose code constructions where the number of errors is bounded by t, the error magnitudes are bounded by l, and the probability resolution is fixed as k. Our constructions exploit the properties of the limited-magnitude errors, and improve the performance in terms of complexity and redundancy.

The distributed matrix multiplication problem with an unknown number of stragglers is considered, where the goal is to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across$N$servers. There are up to$N - R$stragglers but the exact number is not known a priori. Motivated by reducing the computation load of each server, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing task for each server is separated into several subtasks, constructed based on Entangled Polynomial codes by Yu et al. The final results can be obtained from either a larger number of servers with a smaller amount of computation completed per server or a smaller number of servers with a larger amount of computation completed per server. The required finite field size of the proposed solution is less than$2N$. Moreover, the optimal design parameters such as the partitioning of the input matrices are discussed. Our constructions can also be generalized to other settings such as batch distributed matrix multiplication and secure distributed matrix multiplication.

The distributed matrix multiplication problem with unknown number of stragglers is considered, where the goal is to allow a master to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across$N$servers. We assume there are at most$N-R$stragglers but the exact number is not known a priori. Motivated by reducing the latency, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing job for each server is separated into 2 layers, constructed based on Entangled Polynomial (EP) codes by Yu el al. The final results can be obtained when a larger number of servers complete the task from the first layer or a smaller number of servers complete the tasks from both 2 layers. The required finite field size of the proposed solution is less than$2N$. Moreover, the optimal partitioning of the input matrices is discussed. Our constructions can also be generalized to batch matrix multiplication.

A secure multi-party batch matrix multiplication problem (SMBMM) is considered, where the goal is to allow a master to efficiently compute the pairwise products of two batches of massive matrices, by distributing the computation across S servers. Any X colluding servers gain no information about the input, and the master gains no additional information about the input beyond the product. A solution called Generalized Cross Subspace Alignment codes with Noise Alignment (GCSA- NA) is proposed in this work, based on cross-subspace alignment codes. The state of art solution to SMBMM is a coding scheme called polynomial sharing (PS) that was proposed by Nodehi and Maddah-Ali. GCSA-NA outperforms PS codes in several key aspects - more efficient and secure inter-server communication, lower latency, flexible inter-server network topology, efficient batch processing, and tolerance to stragglers.

The private search problem is introduced, where a dataset comprised of L i.i.d. records is replicated across N non-colluding servers, and a user wishes to search for all records that match a privately chosen value, without revealing any information about the chosen value to any individual server. Each record contains P symbols, and each symbol takes values uniformly and independently from an alphabet of size K. Considering the large number of records in modern datasets, it is assumed that L is much larger than the alphabet size K. The capacity of private search is the maximum number of bits of desired information that can be retrieved per bit of download. The asymptotic (large K) capacity of private search is shown to be 1 - 1/N, even when the scope of private search is further generalized to allow OR search, AND search, NOT search and sequence search. The results are based on the asymptotic behavior of a new converse bound for private information retrieval with arbitrarily dependent messages. The asymptotic behavior is also applicable to T-colluding servers or (N, T)-MDS coded servers.

We consider the problem of T-Private Information Retrieval with private side information (TPIR-PSI). In this problem, N replicated databases store K independent messages, and a user, equipped with a local cache that holds M messages as side information, wishes to retrieve one of the other K - M messages. The desired message index and the side information must remain jointly private even if any T of the N databases collude. We show that the capacity of TPIR-PSI is (1+ T/N + ⋯ +(T/N)K-M-1)-1. As a special case obtained by setting T = 1, this result settles the capacity of PIR-PSI, an open problem previously noted by Kadhe et al. We also consider the problem of symmetric-TPIR with private side information (STPIR-PSI), where the answers from all N databases reveal no information about any other message besides the desired message. We show that the capacity of STPIR-PSI is 1 - T/N if the databases have access to common randomness (not available to the user) that is independent of the messages, in an amount that is at least T/N -T bits per desired message bit. Otherwise, the capacity of STPIR-PSI is zero.

The private search problem is introduced, where a dataset comprised of L i.i.d. records is replicated across N non-colluding servers, each record takes values uniformly from an alphabet of size K, and a user wishes to search for all records that match a privately chosen value, without revealing any information about the chosen value to any individual server. The capacity of private search is the maximum number of bits of desired information that can be retrieved per bit of download. The asymptotic (large K) capacity of private search is shown to be 1-1/N, even as the scope of private search is further generalized to allow approximate (OR) search over a number of realizations that grows with K. The results are based on the asymptotic behavior of a new converse bound for private information retrieval with arbitrarily dependent messages.