Distributed Systems — Silicon Valley

Our research activities in the distributed system area range from protocols and algorithms to decentralized architectures and services. We address fundamental issues such as scalability, fault-tolerance, security, manageability, and mobility. We also explore the basic building blocks for distributed systems including networks and operating systems. We place a high value on advancing the state-of-the-art in distributed systems, building experimental prototypes, collaborating with colleagues, publishing our results in the open literature, and having substantial impact on Microsoft products.

Current Projects

Community Information Management
Expanding on the notion of personal information management (PIM), the Community Information Management (CIM) project is exploring system support for loosely structured, semitrustful communities with common information needs. Consider, for example, the parents of a youth soccer team that need to share team rosters, phone numbers, practice schedules, action photos, party plans, and other information that may be contributed and updated by various community members. Addressing the needs of community information management requires fundamental research in a number of areas that go beyond storage and communication including identity, trust, replication, provenance, and contextual awareness.

Research in the Constellation project focuses on innovative methods to discover dependencies between services and hosts in enterprise networks and on end-user machines. The objective is to enhance the ability of network administrators and end-users to diagnose faults, detect changes, and be alerted to configuration problems. The approach is based on discovering local dependencies between the input and output packets in each computer in the network, relying only on passive observation of these packets, and on information such as source/destination, request/response, and time stamps. The project is a joint effort between the Cambridge Lab and the Silicon Valley Lab.

The Dryad Project aims to advance the state of the art in writing and managing distributed applications. Converting a sequential and/or single-machine program into a form in which it can be executed in a concurrent, potentially distributed environment is known to be hard. One long-standing technique to address this is to decompose the program into two logical layers: a high-level skeleton which expresses the data-flow, distribution and concurrency properties; and a collection of subroutines each of which is scheduled by the high-level layer, and executes locally with restricted communications to the rest of the program. The Dryad project is developing a programming model which adopts this approach to tackle both data- and compute-intensive problems, scaling from future single-machine many-core PCs up to large-scale data-centers.

The goal of DryadLINQ is to make distributed computing on large compute cluster simple enough for ordinary programmers. DryadLINQ combines two important pieces of Microsoft technology: the Dryad distributed execution engine and the .NET Language Integrated Query (LINQ). Dryad provides reliable, distributed computing on thousands of servers for large-scale data parallel applications. LINQ enables developers to write and debug their applications in a SQL-like query language, relying on the entire .NET library and using Visual Studio. DryadLINQ is a simple, powerful, and elegant programming environment for writing large-scale data parallel applications running on large PC clusters.

Foundations of Distributed Computing
This research effort focuses on key problems in distributed systems such as replication, fault tolerance and synchronization. Recent work includes a protocol for distributed leader election without having any eventual timely links, a novel optimistic replication technique developed for Microsoft's WinFS system, lower bound results for asynchronous consensus, and a generalization of consensus that permits a state-machine implementation to avoid lower-bound results on conventional consensus for non-conflicting commands. We have also developed a new Fast Paxos algorithm that achieves the lower bounds for fast consensus and a Paxos-based non-blocking transaction commit algorithm that can achieve the same number of message delays as two-phase commit.

Sequoia aims to make distributed applications network-aware. That is, enable applications to take advantage of the characteristics of the underlying network such as proximity, bandwidth capacity, and topology. It intends to achieve this through the key concept of prediction trees, a virtual topology of the network, where virtual nodes representing routers connect real end hosts, and carefully computed edge weights model path properties such as latency and bandwidth.

StarTrack is a framework for enabling track-based applications. Each track is a sequence of entries recording a person’s time, location, and application-specific data. Mobile devices collect tracks and opportunistically upload them to the StarTrack server. StarTrack stores recorded tracks in a database and provides applications with a comprehensive set of operations for comparing, clustering, and querying tracks.

Spamming has been a growing problem in the Internet. This project focuses on spammer identification rather than spam identification, and we seek to identify zombie-based spammers. We explore host network properties (for example: proxy/NAT servers, dynamically assigned IP addresses), and correlate such fine-grained information with network telescope traces and spammimg activities. We emphasize that spammer identification at the network level is independent of spam content and is often straightforward to integrate with existing filtering frameworks.

TidyFS is a distributed filesystem that is designed to be the simplest distributed filesystem useful for data-parallel computation with Dryad. While simple, the system provides fault tolerance and data replication similar to GFS or the Cosmos store.

Inactive Projects

  • Boxwood
    New data abstractions for storage infrastructure
  • Keychain
    Your desktop on a keychain
  • Koh-i-Noor
    Erasure coding for arrays of inexpensive, reliable disks
  • Nocturnal
    Automated Messenger-based information sharing and collaboration
  • Singularity
    New OS for dependable systems

Microsoft Product Engagement

Here are just a few examples of the way that our work has impacted Microsoft products:

  • Michael Isard worked with MSN Search on the design and implementation of their production search engine in areas including fault tolerance and automatic management; scalable query processing; and distributed data-mining.
  • Chandu Thekkath worked closely with the Hotmail product team in implementing scalable, easy to manage, and cost effective solutions for storing and retrieving e-mail.
  • Doug Terry worked with the WinFS team on the design of a novel and efficient replication protocol that is now the core of the Microsoft Sync Framework.