Not Available (click for abstract)

This talk will describe the goals, design, and current status of two projects named Boxwood and Koh-i-Noor that are in progress at Microsoft Research in Silicon Valley.

Boxwood is exploring the design and implementation of persistent, distributed, and fault-tolerant B-Trees. The goal of the project is to provide a high-performance and scalable "B-Tree Service" that is, in turn, used as the underlying substrate by clients such as distributed file systems and distributed data bases. The service is implemented as a cooperating set of CPUs with locally attached storage interconnected by a high speed network. Providing such a service is an interesting challenge in the presence of failures, load imbalances, and concurrency.

Koh-i-Noor is exploring the use of erasure codes to build reliable disk subsystems that tolerate several disk failures before data loss. Unlike mirroring or triplexing, which double or triple the number of disks required to store data, erasure codes can be very cost-effective in providing equivalent (or higher) reliability. Some of the key challenges we have addressed involve getting good read/write performance in the normal case as well as when data is being reconstructed after a failure.