Harvard Computer Science Technical Reports for 2003

TR-01-03 [tr-01-03.ps.gz (338 K)]
Alexandra Fedorova, Margo Seltzer, Kostas Magoutis, and Salimah Addetia. 2003. ``Application Performance on the Direct Access File System.''
The Direct Access File System (DAFS) is a distributed file system built on top of direct-access transports (DAT). Direct-access transports are characterized by using remote direct memory access (RDMA) for data transfer and user-level networking. The motivation behind the DAT-enabled distributed file system architecture is the reduction of the CPU overhead on the I/O data path. In collaboration with Duke University we have created and made available an open-source implementation of DAFS for the FreeBSD platform. In this paper we describe a performance evaluation study of DAFS that was performed with this software. The goal of this work is to determine whether the architecture of DAFS brings any fundamental performance benefits to applications compared to traditional distributed file systems. In our study we compare DAFS to a version of NFS optimized to reduce the I/O overhead. We conclude that DAFS can accomplish superior performance for latency-sensitive applications, outperforming NFS by up to a factor of 2. Bandwidth-sensitive applications do equally well on both systems, unless they are CPU-intensive, in which case they perform better on DAFS. We also found that RDMA is a less restrictive mechanism to achieve copy avoidance than that used by the optimized NFS.
TR-02-03 [tr-02-03.ps.gz (547 K)]
Tim Vasil. 2003. ``Reexamining Operating System Support for Database Management.''
In 1981, Michael Stonebraker observed that database management systems written for commodity operating systems could not effectively take advantage of key operating system services, such as buffer pool management and process scheduling, due to expensive overhead and lack of customizability. The "not quite right" fit between these kernel services and the demands of database systems forced database designers to work around such limitations or re-implement some kernel functionality in user mode. /par We reconsider Stonebraker's 21-year old observations in the context of a modern-day database system, Microsoft SQL Server 2000, and the commodity operating system for which it is explicitly designed, Microsoft Windows 2000. We show that operating system services have become more efficient and flexible so as to meet many of SQL Server's needs directly. We also identify areas where operating system services continue fall short of meeting the needs of a DBMS, and propose several enhancements to rectify these shortcomings.
TR-03-03 [tr-03-03.ps.gz (494 K), tr-03-03.pdf (230 K)]
Kim Hazelwood. 2003. ``Feedback-Directed Query Optimization.''
Current database systems employ static heuristics for estimating the access time of a particular query. These heuristics are based on several parameters, such as relation size and number of tuples. Yet these parameters are only updated intermittently, and the heuristics themselves are hand-tuned. As trends in database systems aim toward self-tuning systems, we can apply the experience of the feedback-directed compiler world to provide robust, self-tuning query optimizers. This paper presents the design and evaluation of a feedback-directed query optimization infrastructure. Using trace-driven simulation, we conclude that dynamic feedback can be quite effective at improving the accuracy of a query optimizer, and adapting to predictable query overhead.
TR-04-03 [tr-04-03.ps.gz (401 K)]
Danil Kirsanov and Steven J. Gortler . 2003. ``Arc-length compression.''
We introduce a novel method for lossy compression of the two-dimensional curves based on the arc-length parameterization. We show that the proposed method has a number of advantages: it is progressive, converges uniformly, and requires the number of the bits proportional to the total arc-length of the curve. The method is applied to the compression of th ehandwritten letters and scanlines of the natural images.
TR-05-03 [tr-05-03.ps.gz (184 K)]
Daniel Ellard, Jonathan Ledlie, and Margo Seltzer. 2003. ``The Utility of File Names.''
For typical workloads and file naming conventions, the size, lifespan, read/write ratio, and access pattern of nearly all files on a system are accurately predicted by the name given to the file when it is created. We discuss some name-related properties observed in three contemporary NFS workloads, and present a method for automatically creating name-based models to predict interesting file properties of new files, and analyze the accuracy of these models for our workloads. Finally, we show how these predictions can be used as hints to optimize the strategies used by the file system to manage new files when they are created.
Jeff Shneidman. 2003. ``.''
TR-07-03 [tr-07-03.ps.gz (882 K)]
Johnny Chen, Michael Mitzenmacher, Chaki Ng, and Nedeljko Varnica. 2003. ``Concatenated Codes for Deletion Channels.''
We design concatenated codes suitable for the deletion channel. The inner code is a combination of a single deletion correcting Varshamov-Tenengolts block code and a marker code. The outer code is a low-density parity-check (LDPC) code. The inner decoder detects the synchronizing points in the received symbol sequence and feeds the outer LPDC decoder with soft information. Even using regular LDPC codes as outer codes our results are promising. Our simulation results demonstrate that the bit error rates of 10^{-6} can be obtained at rate 0.21 when the probability of deletion is 8%.
TR-08-03 [tr-08-03.ps.gz (1142 K)]
Ya'akov Gal and Avi Pfeffer. 2003. ``Modeling Agents' Beliefs using Networks of Influence Diagrams.''
We present a knowledge representation (KR) language that provides for natural, clear and compact models of agents' reasoning processes in games.

Our language allows for uncertainty about the reasoning processes of other agents, and some forms of bounded rationality. We present formal syntax and semantics for the language and show that it is strictly more expressive than Bayesian games, the traditional formalism for modeling uncertainty in games.

TR-09-03 [tr-09-03.ps.gz (445 K)]
Debasis Mishra and David Parkes. 2003. ``Multi-Item Vickrey-Dutch Auction for Unit-Demand Preferences.''
We consider an economy with one seller and a set of selfish buyers. The seller has a set of indivisible heterogeneous items to sell and each buyer wants at most one of those items. Buyers have private, independent and known value on the items. We propose an exact ``Vickrey-Dutch" auction, where prices of appropriate items are decreased by unity in each iteration. This auction converges to Vickrey payoff point exactly if valuations are integer. We then introduce an approximate Vickrey-Dutch auction in which prices of appropriate items are decreased by a positive bid decrement. This auction converges to the Vickrey payoff point approximately. The terminating conditions of both the auctions are related to a concept called ``Universal Competitive Equilibrium" and we show its relationship to Vickrey payoff point in our model. Using simulation, we show that such Vickrey-Dutch auctions have significant advantage in communication complexity over other existing auctions.
David Parkes. 2003. ``.''
TR-12-03 [tr-12-03.ps.gz (169 K)]
Jeffrey Shneidman, David C. Parkes, and Margo Seltzer. 2003. ``Overcoming Rational Manipulation in Distributed Mechanism Implementations.''
Most existing research on computational mechanism design focuses on mechanism complexity. In our work, we focus instead on the separate and equally important problem of mechanism implementation manipulation. Rational manipulation is an issue when mechanisms are implemented by their participants, a model inherent in {\em distributed algorithmic mechanism design} (DAMD), and sometimes implicit in {\em algorithmic mechanism design} (AMD) implementations. Crucially, we recognize that agents may sometimes selfishly benefit (at overall system cost) by deviating from specified algorithms imposed by a mechanism designer. In this work, we explore techniques to make such deviations irrational.

The main contributions of this paper are as follows: We define two properties for non-manipulatable mechanism implementations, communication- and algorithm compatibility, and identify techniques that can be used to achieve these properties. We demonstrate one way to bring communication- and algorithm compatibility to a well-defined lowest cost interdomain routing problem proposed by Feigenbaum, Papadimitriou, Sami, and Shenker (FPSS). Our approach, relying primarily on redundancy, does not add significant new processing or communication overhead to the distributed FPSS algorithm.

TR-13-03 [tr-13-03.ps.gz (125 K)]
Daniel Ellard, and, and David Alpert. 2003. ``Receipt-Free Secure Elections.''
A fundamental requirement for secure and uncoercible elections is the receipt-free property; if voters cannot prove how they voted to anyone other than themselves, then they cannot be coerced by a second party to cast a particular vote.

We begin by describing a protocol for receipt-free elections that was developed by Benaloh & Tuinstra, and then show how this protocol, although correct, is impractical to implement. We then show how to modify this protocol to make it practical to implement. Our protocol requires the addition of an "uncoercible" third party who witnesses the execution of the protocol to make sure that it is executed correctly, but who does not learn the value of the vote.

TR-14-03 [tr-14-03.ps.gz (197 K)]
Daniel Ellard, Michael Mesnier, Eno Thereska, Gregory R. Ganger, and Margo Seltzer. 2003. ``Attribute-Based Prediction of File Properties.''
We present evidence that attributes that are known to the file system when a file is created, such as its name, permission mode, and owner, are often strongly related to future properties of the file such as its ultimate size, lifespan, and access pattern. More importantly, we show that we can exploit these relationships to automatically generate predictive models for these properties, and that these predictions are sufficiently accurate to enable optimizations.
TR-15-03 [tr-15-03.ps.gz (78 K)]
Daniel Ellard. 2003. ``The File System Interface is an Anachronism.''
Contemporary file systems implement a set of abstractions and semantics that are suboptimal for many (if not most) purposes. The philosophy of using the simple mechanisms of the file system as the basis for a vast array of higher-level mechanisms leads to inefficient and incorrect implementations. We propose several extensions to the canonical file system model, including explicit support for lock files, indexed files, and resource forks, and the benefit of session semantics for write updates. We also discuss the desirability of application-level file system transactions and file system support for versioning.
TR-16-03 [tr-16-03.ps.gz (475 K)]
Ningning Zhu, Jiawu Chen, Tzi-cker Chiueh, and Daniel Ellard. 2003. ``An NFS Trace Player for File System Evaluation.''
File system traces have been used in simulation of specific design techniques such as disk scheduling, in workload characterization and modeling, and in identifying interesting file access patterns for performance optimizations. Suprisingly they are rarely used to test the correctness and to evaluate the performance of an actuaal file system or server. The main reason is that up until now there did not exist a flexible and easy-to-use trace player that, given an input trace, can properly initialize the test file system and replay the trace to the test system in such a way that respects dependency constraints among file access requests in the trace. This paper describes the design, implementation, and evaluation of an NFS trace play-back tool called FEUT (File system Evaluation Using Traces), which can automatically derive the initial file system image from a trace, speed up or slow down a trace play-back using temporal or spatial scaling, and features a highly efficient implementation that minimizes the CPU and disk I/O overhead during trace play-back. Experiments using a large NFS trace set show that trace-driven file system evaluation can indeed produce substantially different throughput and latency measurements than synthetic benchmarks such as SPECsfs, and FEUT's trace player is actually more efficient than SPECsfs's workload generator despite the fact that the former requires more CPU computation and disk I/O accesses.
TR-17-03 [tr-17-03.ps.gz (223 K)]
Daniel Ellard and James Megquier. 2003. ``DISP: Practical, Efficient, Secure and Fault Tolerant Data Storage for Distributed Systems.''
We present DISP, a practical, efficient and secure client/server protocol for data storage and retrieval in a distributed environment and show how this protocol can tolerate Byzantine failure. We discuss variations on DISP that can be used as building blocks for different applications, and measure the performance of DISP on commodity hardware.
TR-18-03 [tr-18-03.ps.gz (156 K), tr-18-03.pdf (193 K)]
Kim Hazelwood. 2003. ``Eliminating Voltage Emergencies via Microarchitectural Voltage Control Feedback and Dynamic Program Modification.''
As processor clock gating becomes more and more prevalent, the resulting processor current fluctuations increase the chance of the power supply violating its operating voltage range. Today, low-power research has focused on hardware mechanisms to reduce the chances of these voltage emergencies. While these hardware solutions are very effective at reducing di/dt to an acceptable range, they do so at a performance penalty to the executing program. On the other hand, a compiler is well-equipped to rearrange instructions such that current fluctuations are less dramatic, while minimizing the performance implications. Furthermore, a software-based dynamic optimizer can eliminate the problem at the source-code level during program execution. This paper proposes complementing the hardware techniques with additional compiler-based techniques for eliminating power virus loops, and other recurring power problems. We propose that hardware solutions remain intact, but we extend them to additionally provide feedback to the dynamic optimization system, which can provide a permanent solution to the problem, often without affecting the performance of the executing program. We found that recurring voltage fluctuations do exist in the SPECcpu2000 benchmarks, and that given very little information from the hardware, a dynamic optimizer can locate and correct many of the recurring voltage emergencies.