James Aspnes - US grants

Computer systems of the future may consist of thousands or even millions of processors. Inevitably some of the processors will fail. Faulty processors need to be repaired so that the system on continue functioning. The goal of this project is to investigate improvements to the existing algorithms for parallel fault diagnosis. Second, and more importantly, the project will develop dynamic models for fault diagnosis that are more realistic than previous models.

James Aspnes
"Fault-Tolerant Distributed Resource Location"

Resource location is a fundamental problem in distributed computing.
Examples include such basic tasks as translating URLs into machine
addresses, mapping telephone numbers to individual telephones, and
searching for documents on the Web. Typical current solutions involve
maintaining centralized directories that become bottlenecks that
impair speed and reliability; such solutions are also unsuited to
peer-to-peer systems where individual machines come and go freely. The
research examines how to distribute directory information
holographically throughout the network, so that the costs of searches
are spread evenly, no specialized server machines are needed, and
resources can still be found even if a large fraction of the machines
leave the system.

The main technique is the construction of random graphs whose nodes
(representing resources and machines) are assigned coordinates in some
space based on their keys. Searching for a resource involves moving a
token from some initial node to adjacent nodes closer to the target
until the target is reached. Core components of the project are the
design of graph structures that provide the correct mix of
short-distance and long-distance edges for fast searching and the
design of local mechanisms for building and repairing such structures
quickly without central coordination.

Multi-homed networks are typically consisting of a number of access links be-longing to several distinct service providers. Many networks in the Internet are becoming multi-homed because multi-homing has the potential to improve availability and robustness, improve end-to-end application performance, re-duce operational cost of a user's network, and improve competitiveness of ser-vice providers. In this research project, the researchers will design architecture, algorithms, and protocols for multi-homing to contribute to the efficient opera-tion of multi-homed networks, which are becoming a critical component of the national information infrastructure. This research also aims to develop and dis-tribute a software tool to evaluate key perspectives of global, heterogeneous networks consisting of adaptive single-homed networks, multi-homed networks, and overlay networks.

Most computer programming describes a sequence of steps to be carried out one by one by a single processor core. As the rate of increase in processor speed has slowed, CPU manufacturers have responded by building systems with many processor cores that together carry out multiple tasks simultaneously. These processors share a common memory that they use both for their own individual computations and for communication with other processors. Organizing this shared memory so that the processors can make progress without being delayed by other processors requires careful coordination and the design of specialized data structures and communication protocols to allow efficient cooperation without conflicts. The project will study how letting processors make random choices between different ways to accomplish the same task to improve the efficiency and amount of memory used by these data structures, an approach that appears to be necessary given known impossibility results for non-randomized methods. This may significantly improve our ability to exploit the power of multicore machines, while simplifying the work of programmers of these machines. In addition to this impact on computer science and the practice of programming, the project will directly impact both undergraduate and graduate research. Because concurrent data structures are well-suited to undergraduate implementation projects, which avoid difficulties that often arise with involving undergraduates in more theoretical research, the project will serve as a bridge for recruiting students into cutting-edge, high-stakes research, including students from under-represented groups. At the graduate level, results from the project will feed directly into the PI's teaching, including updates to the PI's publicly-available lecture notes already in use by many students at other institutions.

The main question considered by the project is: Can we remove bottlenecks in concurrent executions of programs in shared-memory system using data structures that avoid traditional concurrency control tools like locking? Two techniques that appear promising are the use of randomization, which avoids problems where bad timing consistently produces bad executions in which different processes interfere with each others' operations, and limited-use assumptions, where shared data structures are designed under the assumption that they will only be used for a limited number of operations, allowing for significant reductions in cost and complexity. In addition to applying these techniques individually to the design of concurrent shared-memory data structures, the project will also consider how these methods can complement each other, for example by the use of randomized helping techniques to transform short-lived limited-use data structures into long-lived unlimited-use data structures. A key element of this work will be the development of improved cost measures for shared-memory data structures, including dynamic measures of space complexity that more accurately reflect practical memory usage than the worst-case measures of maximum memory consumption found in previous work.