Theodore Ming-Tao Wong

HTML without this header

IBM Research
650 Harry Road
San Jose, CA 95120-6099

theowong (at) us (dot) ibm (dot) com
http://www.tmwong.org

Carnegie Mellon University (August 1997 - May 2004)
Graduate Student, Parallel Data Laboratory
Doctor of Philosophy in Computer Science
Master of Science in Computer Science (conferred May 2001)

Cornell University (January 1994 - August 1995)
Master of Engineering in Computer Science

Oxford University (October 1989 - June 1993)
Bachelor of Arts in Engineering Science

Almaden Research Center, IBM Research, San Jose, California

Research Staff Member (December 2003 - Present)
Conducting research and development on middleware for high-performance distributed computing systems. My focus areas include: lightweight distributed consistency control, secure group membership protocols, and algorithms for automatic resource management.

• The Pleiades architecture for DARPA System F6 (Future, fast, flexible, fractionated, free-flying spacecraft united by information exchange) (February 2008 - present)

  The DARPA System F6 program intends to demonstrate that a traditional, large, monolithic satellite can be replaced by a group of smaller, individually launched, wirelessly networked and cluster-flown spacecraft modules. Each ‘fractionated’ module can contribute a unique capability to the rest of the network, such as computing, ground communications, or payload functionality. The ultimate goal of the program is to launch a fractionated spacecraft system and demonstrate it in orbit in approximately four years.

  Orbital Sciences Corporation, teamed with IBM, Jet Propulsion Laboratory, Georgia Institute of Technology, SpaceDev, and Aurora Flight Sciences, has received an award for the first phase of System F6 to:

  • Develop key technologies to enable the fractionated approach, including robust networking, reliable wireless communications, fault-tolerant distributed computing, wireless power transfer, and autonomous cluster navigation

  • Select a space system mission of value to a national security space stakeholder and develop a system design to accomplish that mission

  • Develop an innovative analytical approach using econometric tools that determine the risk-adjusted cost and value of a both a fractionated space system and a monolithic program of record with equivalent capability

  • Develop an evolved hardware-in-the-loop test-bed to emulate the designed fractionated spacecraft using a cluster of networked computers.

• Kybos: Self-management for distributed brick-based storage (December 2003 - February 2008)

  The growth in the amount of data being stored and manipulated for commercial, scientific, and intelligence applications is worsening the manageability and reliability of data storage systems. The expansion of such large-scale storage systems into petabyte capacities puts pressure on cost, leading to systems built out of many cheap but relatively unreliable commodity storage servers. These systems are expensive and difficult to manage—current figures show that management and operation costs are often several times purchase cost—partly because of the number of components to configure and monitor, and partly because system management actions often have unexpected, system-wide side effects. Also, these systems are vulnerable to attack because they have many entry points, and because there are no mechanisms to contain the effects either of attacks or of subsystem failures.

  Kybos is a distributed storage system that addresses these issues. It will provide manageable, available, reliable, and secure storage for large data collections, including data that is distributed over multiple geographical sites. Kybos is self-managing, which reduces the cost of administration by eliminating complex management operations and simplifying the model by which administrators configure and monitor the system. Kybos stores data redundantly across multiple commodity storage servers, so that the failure of any one server does not compromise data. Finally, Kybos is built as a loosely-coupled federation of servers, so that the compromise or failure of some servers will not impede remaining servers from continuing to take collective action toward system goals.

  Our primary application is the self-management of federated (but potentially unreliable) clusters of storage servers, but we anticipate that the algorithms we have developed (and will implement) will have broad applicability to the general class of problems involving the coordination of independent autonomous agents with a collective set of mission goals.

Baskin School of Engineering, University of California, Santa Cruz

Research Fellow (April 2006 - Present)
Collaborating with faculty and students of the Institute for Scalable Scientific Data Management on research in storage systems for high-end computing, with a focus on resource management and end-to-end I/O performance guarantees.

• End-to-end performance management for large distributed systems

  Storage systems for large and distributed clusters of compute servers are themselves large and distributed. Their complexity and scale makes it hard to manage these systems, and in particular they make it hard to ensure that applications using them get good, predictable performance. At the same time, shared access to the system from multiple applications, users, and competition from internal system activities leads to a need for predictable performance.

  Our project investigates mechanisms for improving storage system performance in large distributed storage systems through mechanisms that integrate the performance aspects of the path that I/O operations take through the system, from the application interface on the compute server, through the network, to the storage servers. We focus on five parts of the I/O path in a distributed storage system: I/O scheduling at the storage server, storage server cache management, client-to-server network flow control, client-to-server connection management, and client cache management.

Storage Systems Program, Hewlett-Packard Laboratories, Palo Alto, California

Summer Research Intern (June 1999 - August 1999)
Conducted research into cooperative caching methods for high-end storage systems. Demonstrated that a simple algorithm could yield useful (sometimes substantial) speedups. See My cache or yours? Making storage more exclusive under "Refereed publications" for details.

Information Technology Section, Albert R. Mann Library, Cornell University

Senior Programmer/Analyst (January 1997 - August 1997)
Designed and implemented a storage and retrieval system for delivering digitally scanned monographs over the Internet, as part of the Core Historical Literature of Agriculture project. Took responsibility for system development from its design through to its deployment.

Isis Distributed Systems, Ithaca, New York

Software Engineer, Message Distribution Service (MDS) (May 1996 - January 1997)
Software Engineer, Isis Software Developer's Kit (SDK) (August 1995 - May 1996)
Collaborated in the development of a new MDS release that increased performance. Also provided maintenance engineering and quality assurance testing for the SDK. Experience included porting MDS to Windows NT, adding performance and stability enhancements to the code base, and writing extensive new MDS user documentation.

Cornell Information Technologies, Ithaca, New York

Technical Consultant (October 1993 - April 1995)
Worked as part of a front-line computer support team for Windows- and MSDOS-based platforms.

JP Morgan & Co., Incorporated, New York, New York

Summer Intern, Global Technology and Operations (June 1994 - August 1994)
Designed and developed software for computing credit exposure on interest-rate derivatives.

• David M. LoBosco, Glen E. Cameron, Richard A. Golding, and Theodore M. Wong. The Pleiades fractionated space system architecture and the future of national security space. In Proceedings of the AIAA SPACE 2008 Conference, September 2008

  Our paper is the first in a series of publications to document the development of a fractionated space system. We explain the derivation of the technical approach for system development and present the preliminary architecture. We will publish future papers following the PDR, CDR, and flight demonstration

  Acrobat PDF (992 KB)

• Tim Kaldewey, Theodore M. Wong, Richard Golding, Anna Povzner, Scott Brandt, and Carlos Maltzahn. Virtualizing disk performance. In Proceedings of the 14th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2008), April 2008 (Best student paper)

  Large- and small-scale storage systems frequently serve a mixture of workloads, an increasing number of which require some form of performance guarantee. Providing guaranteed disk performance—the equivalent of a “virtual disk”—is challenging because disk requests are non-preemptible and their execution times are stateful, partially non-deterministic, and can vary by orders of magnitude. Guaranteeing throughput, the standard measure of disk performance, requires worst-case I/O time assumptions orders of magnitude greater than average I/O times, with correspondingly low performance and poor control of the resource allocation. We show that disk time utilization—analogous to CPU utilization in CPU scheduling and the only fully provisionable aspect of disk performance—yields greater control, more efficient use of disk resources, and better isolation between request streams than bandwidth or I/O rate when used as the basis for disk reservation and scheduling.

  Acrobat PDF (256 KB)

• Anna Povzner, Tim Kaldewey, Scott Brandt, Richard Golding, Theodore M. Wong, and Carlos Maltzahn. Efficient guaranteed disk request scheduling with Fahrrad. In Proceedings of the ACM SIGOPS/EuroSys European Conference on Computer Systems 2008 (EuroSys 2008), April 2008

  Guaranteed I/O performance is needed for a variety of applications ranging from real-time data collection to desktop multimedia to large-scale scientific simulations. Reservations on throughput, the standard measure of disk performance, fail to effectively manage disk performance due to the orders of magnitude difference between best-, average-, and worst-case response times, allowing reservation of less than 0.01% of the achievable bandwidth. We show that by reserving disk resources in terms of utilization, it is possible to create a disk scheduler that supports reservation of nearly 100% of the disk resources, provides arbitrarily hard or soft guarantees depending upon application needs, and yields efficiency as good or better than best-effort disk schedulers tuned for performance. We present the architecture of our scheduler, prove the correctness of its algorithms, and provide results demonstrating its effectiveness.

  Acrobat PDF (400 KB)

• David O. Bigelow, Suresh Iyer, Tim Kaldewey, Roberto C. Pineiro, Anna Povzner, Scott A. Brandt, Richard A. Golding, Theodore M. Wong, and Carlos Maltzahn. End-to-end performance management for scalable distributed storage. In Proceedings of the Petascale Data Storage Workshop, November 2007

  Acrobat PDF (130 KB)

• Richard A. Golding and Theodore M. Wong. Walking toward moving goalposts: agile management for evolving systems. In Proceedings of the First Workshop on Hot Topics in Autonomic Computing (HotAC I), June 2006

  Much of the practical work in the autonomic management of storage systems has taken the “bolt-on” approach: take existing systems and add a separate management system on the side. While this approach can improve legacy systems, it has several problems, including scaling to heterogeneous and large systems and maintaining consistency between the system and the management model. We argue for a different approach, where autonomic management is woven throughout a system, as in the K2 distributed storage system that we are implementing. This distributes responsibility for management operations over all nodes according to ability and security, and stores management state as part of the entities being managed. Decision algorithms set general configuration goals and then let many system components work in parallel to move toward the goals.

  Acrobat PDF (136 KB)

• Theodore M. Wong, Richard A. Golding, Caixue Lin, and Ralph A. Becker-Szendy. Zygaria: Storage performance as a managed resource. In Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2006), April 2006

  Large-scale storage systems often hold data for multiple applications and users. A problem in such systems is isolating applications and users from each other to prevent their corresponding workloads from interacting in unexpected ways. Another is ensuring that each application receives an appropriate level of performance. As part of the solution to these problems, we have designed a hierarchical I/O scheduling algorithm to manage performance resources on an underlying storage device. Our algorithm uses a simple allocation abstraction: an application or user is associated with a corresponding pool of throughput, and manages throughput within its pool by opening sessions. The algorithm ensures that each pool and session receives at least a reserve rate of throughput and caps usage at a limit rate, using hierarchical token buckets and EDF I/O scheduling. Once it has fulfilled the reserves of all active sessions and pools, it shares unused throughput fairly among active sessions and pools such that they tend to receive the same amount. It thus combines deadline scheduling with proportional-style resource sharing in a novel way. We assume that the device performs its own low-level head scheduling, rather than modeling the device in detail. Our implementation shows the correctness of our algorithm, imposes little overhead on the system, and achieves throughput nearly equal to that of an unmanaged device.

  Acrobat PDF (424 KB)

• Winfried W. Wilcke et al. IBM Intelligent Bricks project—Petabytes and beyond. IBM Journal of Research and Development, 50(2/3), pp. 181–198, March–May 2006

  This paper provides an overview of the Intelligent Bricks project in progress at IBM Research. It describes common problems faced by data center operators and proposes a comprehensive solution based on brick architectures. Bricks are hardware building blocks. Because of certain properties, defined here, scalable and reliable systems can be built with collections of identical bricks. An important feature is that brick-based systems must survive the failure of any brick without requiring human intervention, as long as most bricks are operational. This simplifies system management and allows very dense and very scalable systems to be built. A prototype storage server in the form of a 3x3x3 array of bricks, capable of storing 26 TB, is operational at the IBM Almaden Research Center. It successfully demonstrates the concepts of the Intelligent Bricks architecture. The paper describes this implementation of brick architectures based on newly developed communication and cooling technologies, the software developed, and techniques for building very reliable systems from low-cost bricks, and it discusses the performance and the future of intelligent brick systems.

• Theodore M. Wong, Chenxi Wang, and Jeannette M. Wing. Verifiable secret redistribution for archive systems. In Proceedings of the First International IEEE Security in Storage Workshop (SISW 2002), December 2002

  We present a new verifiable secret redistribution protocol for threshold sharing schemes that forms a key component of a proposed archival storage system. Our protocol supports redistribution from (m,n) to (m',n') threshold sharing schemes without requiring reconstruction of the original data. The design is motivated by archive systems for which the added security of threshold sharing of data must be accompanied by the flexibility of dynamic shareholder changes. Our protocol enables the dynamic addition or removal of shareholders, and also guards against mobile adversaries. We observe that existing protocols either cannot be extended readily to allow redistribution between different access structures, or have vulnerabilities that allow faulty old shareholders to distribute invalid shares to new shareholders. Our primary contribution is that in our protocol, new shareholders can verify the validity of their shares after redistribution between different access structures.

  Acrobat PDF (424 KB)

• Theodore M. Wong and John Wilkes. My cache or yours? Making storage more exclusive. In Proceedings of the USENIX Annual Technical Conference, June 2002, pp. 161-175

  Modern high-end disk arrays often have several gigabytes of cache RAM. Unfortunately, most array caches use management policies which duplicate the same data blocks at both the client and array levels of the cache hierarchy: they are inclusive. Thus, the aggregate cache behaves as if it was only as big as the larger of the client and array caches, instead of as large as the sum of the two. Inclusiveness is wasteful: cache RAM is expensive.

  We explore the benefits of a simple scheme to achieve exclusive caching, in which a data block is cached at either a client or the disk array, but not both. Exclusiveness helps to create the effect of a single, large unified cache. We introduce a DEMOTE operation to transfer data ejected from the client to the array, and explore its effectiveness with simulation studies. We quantify the benefits and overheads of demotions across both synthetic and real-life workloads. The results show that we can obtain useful (sometimes substantial) speedups.

  During our investigation, we also developed some new cache-insertion algorithms that show promise for multi-client systems, and report on some of their properties.

  Acrobat PDF (264 KB)

• Theodore M. Wong, Richard A. Golding, Joseph S. Glider, Elizabeth Borowsky, Ralph A. Becker-Szendy, Claudio Fleiner, Deepak R. Kenchammana-Hosekote, and Omer A. Zaki. Kybos: Self-management for distributed brick-based storage. IBM Technical Paper RJ10356, August 2005

  Current tools for storage system configuration management make offline decisions, recovering from, instead of preventing, performance specification violations. The consequences are severe in a large-scale system that requires complex actions to recover from failures, and can result in a temporary shutdown of the system. We introduce Kybos, a distributed storage system that makes online, autonomous responses to system changes. It runs on clusters of intelligent bricks, which provide local enforcement of global performance and reliability specifications and so isolate both recovery and application IO traffic. A management agent within Kybos translates simple, high-level specifications into brick-level enforcement targets, invoking centralized algorithms only when taking actions that require global state. Our initial implementation shows that this approach works well.

  Acrobat PDF (208 KB)

• Theodore M. Wong. Decentralized recovery for survivable storage systems. PhD dissertation (Technical Report CMU-CS-04-119), School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, May 2004

  Modern society has produced a wealth of data to preserve for the long term. Some data we keep for cultural benefit, in order to make it available to future generations, while other data we keep because of legal imperatives. One way to preserve such data is to store it using survivable storage systems. Survivable storage is distinct from reliable storage in that it tolerates confidentiality failures in which unauthorized users compromise component storage servers, as well as crash failures of servers. Thus, a survivable storage system can guarantee both the availability and the confidentiality of stored data.

  Research into survivable storage systems investigates the use of m-of-n threshold sharing schemes to distribute data to servers, in which each server receives a share of the data. Any m shares can be used to reconstruct the data, but any m - 1 shares reveal no information about the data. The central thesis of this dissertation is that to truly preserve data for the long term, a system that uses threshold schemes must incorporate recovery protocols able to overcome server failures, adapt to changing availability or confidentiality requirements, and operate in a decentralized manner.

  To support the thesis, I present the design and experimental performance analysis of a verifiable secret redistribution protocol for threshold sharing schemes. The protocol redistributes shares of data from old to new, possibly disjoint, sets of servers, such that new shares generated by redistribution cannot be combined with old shares to reconstruct the original data. The protocol is decentralized, and does not require intermediate reconstruction of the data; thus, it does not introduce a central point of failure or risk the exposure of the data during execution. The protocol incorporates a verification capability that enables new servers to confirm that their shares can be used to reconstruct the original data.

  Acrobat PDF (714 KB)    PostScript (1642 KB)

• Theodore M. Wong and Jeannette M. Wing. Verifiable secret redistribution. Technical Report CMU-CS-01-155, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, October 2001

  Acrobat PDF (176 KB)    PostScript (204 KB)

• John Wilkes and Theodore M. Wong. Exclusive caching in computer systems. United States Patent 6,851,024 (granted 1 February 2005)

  A computer system with mechanisms for exclusive caching that avoids the accumulation of duplicate copies of information in host and storage system caches. A computer system according to these exclusive caching techniques includes a host system having a host cache and a storage system having a storage system cache and functionality for performing demote operations to coordinate the placement of information in the host cache to the storage system caches.

• John Wilkes and Theodore M. Wong. Adaptive data insertion for caching. United States Patent 6,728,837 (granted 27 April 2004)

  A computer system cache monitors the effectiveness of data inserted into a cache by one or more sources to determine which source should receive preferential treatment when updating the cache. The cache may be part of a computer system that includes a plurality of host systems; each host system includes a host cache, connected to a storage system having a storage system cache. Ghost caches are used to record hits from the plurality of host systems performing operations for storing and retrieving data from the storage system cache. The storage system cache includes a cache controller that is operable to calculate a merit figure and determine an insertion point in a queue associated with the storage system cache based on the merit figure. The merit figure is calculated using a weighting algorithm for weighting hits from the plurality of sources recorded in the ghost caches.

• 6th USENIX Conference on File and Storage Technologies (FAST 2008): Program committee

• 24th IEEE Conference on Mass Storage Systems and Technologies (MSST 2007): Program committee

• The 2007 International Conference on Parallel Processing (ICPP 2007): Data-intensive and I/O Computing program committee

• 13th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2007): Real-time and embedded applications / benchmarks (Area A) track committee

• 2nd International Workshop on Storage Security and Survivability (StorageSS 2006): Program committee

• Kernels: Linux 2.6 series (loadable module development)

• Languages: C, C++, Java

• Scripting languages: Perl, Tcl/Tk

• Development environments: Eclipse

• Source control systems: Perforce, CVS, ClearCase