Developing efficient algorithms to synchronize between different versions of files is an important problem with numerous applications. We consider the interactive synchronization protocol introduced by Yazdi and Dolecek, based on an earlier synchronization algorithm by Venkataramanan et al. Unlike preceding synchronization algorithms, Yazdi and Dolecek's algorithm is specifically designed to handle a number of deletions linear in the length of the file. We extend this algorithm in three ways. First, we handle nonbinary files. Second, these files contain symbols chosen according to nonuniform distributions. Finally, the files are modified by both insertions and deletions. We take into consideration the collision entropy of the source and refine the matching graph developed by Yazdi and Dolecek by appropriately placing weights on the matching graph edges. We compare our protocol with the widely used synchronization software rsync, and with the synchronization protocol by Venkataramanan et al. In addition, we provide tradeoffs between the number of rounds of communication and the total amount of bandwidth required to synchronize the two files under various implementation choices of the baseline algorithm. Finally, we show the robustness of the protocol under imperfect knowledge of the properties of the edit channel, which is the expected scenario in practice.

In the framework of write-once memory (WOM) codes, it is important to distinguish between codes that can be decoded directly and those that require the decoder to know the current generation so as to successfully decode the state of the memory. A widely used approach to constructing WOM codes is to design first nondecodable codes that approach the boundaries of the capacity region and then make them decodable by appending additional cells that store the current generation, at an expense of rate loss. In this paper, we propose an alternative method to making nondecodable WOM codes decodable by appending cells that also store some additional data. The key idea is to append to the original (nondecodable) code a short synchronous WOM code and write generations of the original code and the synchronous code simultaneously. We consider both the binary and the nonbinary case. Furthermore, we propose a construction of synchronous WOM codes, which are then used to make nondecodable codes decodable. For short-to-moderate block lengths, the proposed method significantly reduces the rate loss as compared to the standard method.

We study the problem of synchronizing two files X and Y at two distant nodes A and B that are connected through a two-way communication channel. We assume that file Y at node B is obtained from file X at node A by inserting and deleting a small fraction of symbols in X. More specifically, we consider the case where X is a non-binary non-uniform string, and deletions and insertions happen uniformly with rates β d and β i , respectively. We propose a synchronization protocol between node A and node B that needs to transmit O(q/H 2 (β d +β i )n log 1/β d +β i ) bits (where n is the length of X, q is the alphabet size and H 2 is the collision entropy of X) and reconstructs X at node B with error probability exponentially low in n. This protocol readily generalizes the recent result by Tabatabaei Yazdi and Dolecek that dealt with synchronization from binary uniform source and under only deletion errors.

We study the competing goals of utility and privacy as they arise when a provider delegates the processing of its personal information to a recipient who is better able to handle this data. We formulate our goals in terms of the inferences which can be drawn using the shared data. A whitelist describes the inferences that are desirable, i.e., providing utility. A blacklist describes the unwanted inferences which the provider wants to keep private. We formally define utility and privacy parameters using elementary information-theoretic notions and derive a bound on the region spanned by these parameters. We provide constructive schemes for achieving certain boundary points of this region. Finally, we improve the region by sharing data over aggregated time slots.

While some write once memory (WOM) codes are inherently decodable, others require the added knowledge of the current generation in order to successfully decode the state of the memory. If there is no limit on the code length, n, a binary non-decodable t-write WOM code can be made decodable at an insignificant cost in terms of code rate by adding t − 1 cells to store the current generation after replicating the code enough times for the t − 1 cells to be of negligible weight. This justifies the research on non-decodable WOM codes. However, if n is bounded, the t − 1 additional cells may introduce a significant loss in terms of code rate. In this paper, we propose a new method to make non-decodable WOM codes decodable at a lower price when n is bounded. The main idea is to add cells that do not only store the current generation, but also additional data, by using a synchronous (t − 1)-write WOM code of length t − 1 or slightly above which does not contain the all-zero codeword. A bound on the rate of a simple family of synchronous WOM codes with n = t is given, as well as very short codes from this family. Better codes are then obtained by local manipulations of these codes. Finally, a construction of synchronous WOM codes with good properties is proposed to reach higher values of t.

Ternary channels can be used to model the behavior of some memory devices, where information is stored in three different levels. In this paper, error correcting coding for a ternary channel where some of the error transitions are not allowed, is considered. The resulting channel is nonsymmetric, therefore, classical linear codes are not optimal for this channel. We define the maximum-likelihood (ML) decoding rule for ternary codes over this channel and show that it depends on the channel error probability. An alternative decoding rule which depends only on code properties, called dA-decoding, is then proposed. It is shown that dA-decoding and ML decoding are equivalent, i.e., dA-decoding is optimal, under certain conditions. Assuming dA-decoding, we characterize the error correcting capabilities of ternary codes over the nonsymmetric ternary channel. We also derive an upper bound and a constructive lower bound on the size of codes. The results arising from the constructive lower bound are then compared, for short sizes, to optimal codes (in terms of code size) found by a clique-based search. It is shown that the proposed construction method gives good codes, and that in some cases the codes are optimal.