We investigate the problem of MapReduce and coded MapReduce. MapReduce is a programming model for the website search engine. It has three phases: Map, Shuffle, and Reduce. Even though it is an extensively used tool for distributed computing, the communication time involved in the shuffle phase can be a bottleneck for the overall system delay. Coded MapReduce was recently proposed that trades replicated computation for shorter communication. In this thesis, we formally define the model and algorithm of MapReduce and coded MapReduce. Moreover, we implement them with identical Map and Reduce functions. The communication time and the overall system time is analyzed theoretically and measured experimentally. Finally, as an example, reverse indexing is implemented under MapReduce and coded MapReduce framework. We analyze and measure the delay performance for this case as well. We find that when each Map computation task is replicated twice, the coded MapReduce scheme is almost twice as fast as the naive MapReduce scheme.

Motivated by the Smith-Waterman algorithm, this dissertation studies the problem of alignment on the DNA sequences. Traditional methods like the Smith-Waterman algorithm is applying classic dynamic programming on the DNA nucleotide sequences. However, they have several disadvantages. The first one is that the Smith-Waterman algorithm is utilizing the DNA nucleotide sequences to achieve the alignment and can only show how two sequences are aligned, not a finalized aligned sequence. And various parameters, the penalty for substitution, insertion, and deletion, designed by users could occur different alignment results. This work proposes the method of dynamic time warping(DTW) combined with Nanopore technology and base-calling technology to achieve a finalized aligned sequence and improve the base-calling accuracy. In particular, DTW, Nanopore technology, and guppy base-caller are utilized to the DNA strands and finally, we can show base-calling sequences with higher accuracy compared to the base-calling sequences without alignment. Simulation results can show that our soft information alignment can finalize the aligned sequences and improve the base-calling accuracy.

Driven by the growth of data-centric applications, efficient data storage and retrieval has become crucial for modern service providers. Storage systems are becoming increasingly complex, in response to the various challenges rising from the different layers of storage systems. This dissertation aims at designing novel data coding techniques improving device-level reliability and reducing storage and communication costs at the system level.

We consider the repair problem in distributed storage systems (DSSs), which refers to the process of regenerating the content of inaccessible or failed nodes. Repairing failures is necessary to maintain a desired level of fault-tolerance in DSSs. Specifically, we consider the repair problem of multiple erasures in a centralized manner. Using information-theoretic tools, we derive fundamental limits for the problem. Our analysis exhibits a fundamental tradeoff between the storage overhead required for reliability and the amount of data being transferred during repair. Accordingly, we propose several data coding techniques operating at various points of the tradeoff, with provable optimality for certain configurations.

A standard assumption in coding theory for distributed storage is that messages are static, and write and read operations are completed instantaneously for every non-failed storage node. In this work, we study the fundamental problem of storing evolving information in distributed networks from a coding-theoretic perspective.

Specifically, we study the design of storage-efficient algorithms for emulating atomic shared memory over an asynchronous, distributed message-passing system, a fundamental question in the field of distributed algorithms, as well as a ubiquitous problem in distributed computing applications. We propose new erasure-code based algorithms and compare their merits to existing ones. In particular, our algorithms feature a parameter v that allows a system designer to trade off between the storage size and liveness of read operations, while guaranteeing the strictest consistency requirement, atomicity.

Finally, we consider the device level and study the reliability of resistive memories (RRAMs). RRAMs are a promising non-volatile memory technology with high storage densities. However, the readout reliability of RRAMs is impaired due to the sneak path problem. In crossbar arrays, sneak paths cause different reliability levels across array cells. Motivated by this problem, we study the framework of polar coding over channels with different reliability levels, and we propose a coding technique improving its bit error rate (BER) performance. We then apply our framework to the crossbar array and demonstrate a significant reduction in BER.

Having timely and fresh knowledge about the current state of information sources is critical in a variety of applications. In particular, a status update may arrive at the destination much later than its generation time due to processing and communication delays. The freshness of the status update at the destination is captured by the notion of age of information. In this study, we first analyze a network with a single source, $n$ servers, and the monitor (destination). The servers independently sense the source of information and send the status update to the monitor. We then extend our result to multiple independent sources of information in the presence of $n$ servers. We assume that updates arrive at the servers according to Poisson random processes. Each server sends its update to the monitor through a direct link, which is modeled as a queue. The service time to transmit an update is considered to be an exponential random variable. We examine both homogeneous and heterogeneous service and arrival rates for the single-source case, and only homogeneous arrival and service rates for the multiple sources case. We derive a closed-form expression for the average age of information under a last-come-first-serve (LCFS) queue for a single source and arbitrary $n$ homogeneous servers. For $n=2,3$, we derive the explicit average age of information for arbitrary sources and homogeneous servers, and for a single source and heterogeneous servers. For $n=2$ we find the optimal arrival rates given fixed sum arrival rate and service rates.

The high demand for data storage and data communication brings many new challenges and concerns, including but not limited to, how to efficiently store data in devices and how to reliably communicate data between different devices to avoid possible errors. Those two problems correspond to the two most important concepts in information theory: source coding and channel coding, where the former compresses data to reduce its size, and the latter enlarges the data to combat errors.In this thesis, four problems about source coding and channel coding are presented with applications in information storage and networks.

For source coding, SEAL is presented, which is a novel data compression approach for system log data and supports causality analysis for system security. Based on information-theoretic observations on system event data, the approach achieves lossless compression and supports near real-time retrieval of historic events. In the compression step, the causality graph induced by the system logs is investigated, and abundant edge reduction potentials are explored. In the query step, for maximal speed, decompression is opportunistically executed. SEAL greatly alleviates the exponentially-growing storage demand for causality analysis in industrial computer security.

For channel coding, an error-correcting code based on low-density parity-check code(LDPC) for DNA storage is first introduced. In this work, DNA storage that uses affordable and portable nanopore sequencing is considered as the reading mechanics. Unlike traditional data storage systems, errors occur asymmetrically among the four types of nucleotide bases of DNA. Quaternary codes can be employed for error correction, but suffer from high complexity. For this problem, a turbo-like decoder for the DNA storage channel is designed. Meanwhile, the corresponding density evolution algorithms are designed to prove the optimal bound for the decoders. Simulation results show that the binary LDPC codes have a similar bit error rate but with a speedup by a factor of 4 compared to quaternary codes.

Next, a source of synchronization errors in DNA storage is identified, which could result in missing symbols in the read result from nanopore sequencing. To limit such errors, constrained codes are presented. Moreover, this work shows encoding algorithms and maximum a posteriori decoding algorithms in the presence of additive Gaussian noise and deletions. The simulation shows a trade-off between the coding rate and the missing-symbol rate. The decoding simulation results show that the algorithms can correct missing-symbols error efficiently. Meanwhile,simulated data from DeepSimulator by Y. Li et al. [1] and the real-world data also show that the constrained DNA strings have fewer missing-symbol errors.

Finally, coding for network synchronization is investigated. This work studies the problem of clock synchronization in an arbitrary network, viewed as a graph. Each server is a node, and two nodes are connected by an edge if their time discrepancy (edge weight) is measured. The time discrepancy is known by one or both of these two servers. The goal is to reduce the communication cost between server nodes and the master node, which collects the discrepancy information to eliminate the loop-wise offset surplus in the network. For the two important cases where each time discrepancy is known by both adjacent servers and by only one of the adjacent servers, the optimal schemes are found.

1. Li, Yu, et al. "DeepSimulator1. 5: a more powerful, quicker, and lighter simulator for Nanopore sequencing." Bioinformatics 36.8 (2020): 2578-2580.

The modern information age is heralded by exciting paradigms that generate a tremendous amount of data, such as health records, financial transactions, and social media user information. As information becomes increasingly available, distributed computing becomes more and more important, especially in information retrieval, search, and computation. The high demand for distributed computing brings many new challenges and concerns. This dissertation focuses on privacy, security, and flexibility issues in distributed computing from an information-theoretic perspective. Specifically, we study the privacy problem via private information retrieval (PIR) with a focus on the scenarios with available side information and private search. The security and flexibility problems are investigated via coded distributed computing. Two settings for matrix multiplication are studied: the secure multi-party computation and the distributed computation with a flexible number of available servers.

PIR allows a user to retrieve one message from databases while preserving the privacy of the desired message index. We investigate the role of side information in PIR, meaning a subset of the messages known by the user. Assume T is the number of possible colluding databases, despite which the privacy of the desired message and the side information should still be maintained. We focus on T-Private Information Retrieval with Private Side Information (TPIR-PSI) and characterize its capacity. A novel achievable scheme is proposed. As a special case obtained by setting T = 1, our result settles the capacity of PIR-PSI, an open problem previously noted by Kadhe et al. We extend our results to the problem of symmetric-TPIR with private side information (STPIR-PSI). Then, we consider private search, where a user searches for all records matching a symbol from the servers, without revealing any information about the queried symbol. Private search is shown to be highly related to PIR with arbitrarily dependent messages. A new converse bound is presented for PIR with arbitrary dependence. Based on the asymptotic behavior of the new converse bound, the asymptotic capacity of private search is characterized. Our result is further generalized to OR search, AND search, NOT search and sequence search.

As the next step, we consider secure multi-party batch matrix multiplication (SMBMM). Two batches of matrices are individually coded and transmitted to the computation servers, who communicate with each other and a master such that the product of the matrices is decoded at the master. The matrices are kept secure from the servers and the master, except that the master obtains the final product. A solution called Generalized Cross Subspace Alignment codes with Noise Alignment (GCSA-NA) is proposed based on cross-subspace alignment codes. Compared to the state-of-art solution, polynomial sharing, GCSA-NA outperforms it 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. Moreover, the idea of noise alignment can be applied to symmetric secure private information retrieval to achieve the asymptotic capacity.

Finally, we focus on the flexibility of the coded distributed matrix multiplication. The goal is also to compute the matrix product from distributed servers. However, servers do not communicate among themselves and the number of stragglers (slow servers) is not known a priori. A novel flexible construction is proposed to fully utilize the computation capability of available servers. The main idea is to require non-straggler servers to finish more sub-tasks to compensate for the effect of the stragglers. The fundamental trade-off between server storage capacity and computation load is investigated.