Colloquia and Seminars

We introduce the sum channel, a new channel model motivated by applications in distributed storage and DNA data storage. In the error-free case, it takes as input an $\ell$-row binary matrix and outputs an $(\ell+1)$-row matrix whose first $\ell$ rows equal the input and whose last row is their parity (sum) row.

We construct a two-deletion-correcting code with redundancy $2\lceil\log_2\log_2 n\rceil+ \log_2 \ell + O(1)$ for $\ell$-row inputs. When $\ell=2$, we establish a lower bound of $\lceil\log_2\log_2 n\rceil + O(1)$ bits, implying that our redundancy is optimal up to a factor of 2.

We also present a code correcting a single substitution with $\lceil \log_2(\ell+1)\rceil$ redundant bits and prove that it is within one bit of optimality.

A "named page" is a memory page whose content originates from and is backed by a file. Because named pages are regularly read from and written to persistent storage, filesystems strive to preserve file content contiguity, thereby enabling sequential I/O, which can be much faster than random I/O. No analogous effort to preserve contiguity exists for "anonymous pages," which hold unnamed data such as stack or heap bytes. Consequently, swapping a region of anonymous pages in or out can be much slower than reading or writing a region of named pages.

We observe (1) that the main advantage of the existing swap mechanism is high swap area utilization, since any anonymous page can be placed at any offset within the swap file, so there is no fragmentation; but (2) that secondary storage is commonly underutilized, so the cost of random I/O may be unwarranted. We therefore propose "named swapping," which associates each anonymous region with its own (swap) file and thus benefits from the underlying filesystem's efforts to maintain contiguity, improving swap performance by up to an order of magnitude. A key challenge we address is anonymous pages shared across multiple regions due to fork-based copy-on-write.