Research

Current Projects

• Security issues arising in large-scale distributed computations
  
  The past year has seen the birth of several commercial enterprises whose goal is to capitalize on the abundance of ``spare'' compute cycles in personal computers by providing an efficient and convenient platform for very large scale distributed computations. Application domains which potentially benefit from such huge amounts of compute include DNA sequencing and protein folding in the biotech sector, graphics in the entertainment industry, and exhaustive regression and other statistical and modeling applications in the financial and oil industries. Such large scale distributed computations running in an untrusted environment raise a number of security concerns. These include the potential for either intentional or unintentional corruption of data at individual nodes, or for the collusion of a group of malicious nodes. While several (though not all) of the commercial platforms under development include measures to ensure the privacy of data and protect proprietary software, these efforts typically amount to security through obscurity. Guaranteed reliability of results performed on these platforms can be achieved trivially through redundancy, but in many situations this is both inefficient and expensive -- firms providing the platform generate revenue from finishing large numbers of jobs, and firms utilizing the service are often charged based on some measure of total cycles required. Often neither benefits from redundancy. On the other hand, without some measure of redundancy, there can be no guarantee of the validity of returned results. We approach the problem from two angles. First, we have developed and are currently analyzing a number of frameworks which attempt to balance the need for reliability with the need for efficient use of resources. Second, we are examining issues of resilience in distributed computations. For the framework development, our techniques include both simulation and probabilistic analysis, and include a wide variety of models of potential attack strategies and defenses. Once we have refined our frameworks, we will test them by running several compute jobs on the Frontier distributed computing platform developed by Parabon Computation, Inc. in Fairfax, Virginia. (I designed and implemented the Parabon Exhaustive Regression Engine, which runs on Pioneer, and so am familiar with their API as well as the overall Frontier architecture.) Each job will involve tens of thousands of nodes, with specific proportions of the nodes running ``rogue'' code. Our approach to the question of resilience has been to develop a rough taxonomy of classes of computations, since often times the the degree of damage that may be caused by rogue nodes depends on the nature of the computation. For example, an optimization problem that involves a simple parameter search in a large space is more resilient if the function being analyzed obeys some notion of continuity, since potential extrema can be easily verified (so a rogue node claiming to have a solution is foiled), and since non-optimal parameters should be very near the true extremal parameters (so a rogue node that omits a number of good results is foiled).
  
  
• PinPoint Spatial Location Protocols (Joint work with A. Agrawala, U. Shankar, and R. Larsen, at the University of Maryland, College Park)
  
  The development of an efficient lightweight mechanism for determining the spatial layout of a wireless network of nodes has proven elusive. Existing approaches (GPS, acoustic, infrared, radio, etc.) either have poor accuracy and range or are very expensive (e.g. differential GPS) and may require elaborate infrastructure support. PinPoint Technology provides an accurate, rapid, and inexpensive solution to this problem. Specifically, it allows a set of wireless nodes distributed in 3D space to rapidly and accurately determine both the propagation delay between every pair of nodes, and the relative clock drift and offset between every pair of nodes. This, in turn, allows calculation of the inter-node distances, and thus the spatial layout of the nodes, as well as the local clock times at other nodes, and hence the ability to carry out precise synchronized actions. The techniques are based on a novel way of integrating clocks and timers with UHF communications, together with the use of time-based protocols. These time-based protocols (protocols that rely on explicit real-time state) allow a flexible TDMA scheduling of all resources, from UHF media to application. Initial results show that our methods can, with nominal hardware, determine locations to an accuracy of a few centimeters and determine clock differences to an accuracy of a nanosecond. With our current protocols, a set of one hundred nodes within UHF range of each other can learn of their inter-node propagation delays and clock attributes in a few seconds; it would take a few tens of seconds for a set of one thousand nodes. The protocol can be periodically repeated either to reduce errors or to track moving nodes. Speeds of 50 mph can be easily accommodated. The PinPoint method is currently the subject of an NSF ITR proposal, in which we envision applying the technique to
  • item Geo-location and movement tracking: Given the location of three nodes and their distance to a fourth node, the location of the fourth node can be easily determined by any node possessing this information. This can be used for location determination in sensor networks, for E911 positioning in cellular networks, smart vehicles, location-based routing in ad-hoc networks, etc.
  • Ad-Hoc networking: A set of nodes with accurate current estimates of remote node clocks can use flexible TDMA rather than the less efficient CSMA/CA to share the wireless media (the latter being the only currently feasible approach in the absence of a base station). In addition, flexible TDMA in multi-hop wireless networks can be used with current techniques in higher layers (e.g. DSDV in routing, mobile IP, etc), though the most dramatic increases in efficiency can be achieved by extending the time-based approach into the network and transport layers.
  • Temporal tomography: By surrounding an object with PinPoint nodes and analyzing the addition delays incurred by signals reflected from or going through the object, one can map the internal and external reflecting surfaces and composition of the object by knowing the speed of waves in different media. To do this at the fine-scale of medical imaging of the human body, picosecond resolution is needed. We propose a ``verniering'' technique that yields the required accuracy while maintaining a cost advantage over current intensity-based approaches such as CAT scans.
  
  
  
• Clock Synchronization in Cyclone networks (Joint work with A. Agrawala and S. Hawkins at the University of Maryland, College Park)
  
  A Cyclone network is a class of connection oriented synchronous communication network that utilizes a cyclic approach to node resource management. Resources are reserved for the duration of a cycle, a fixed length period during which fixed size chunks of data are transmitted. Because reservations specify both time (i.e. cycle number) and link (i.e. the link from node i to node j), there is no run-time contention for resources between different scheduled communication tasks. This allows the system to provide deterministic (predictable) service levels, and results in zero delay jitter, lossless data transmission, and efficient processing of datagrams on every node of the transmission path. Nodes in a Cyclone network (called cyclonodes) are controlled by clocks local to the individual nodes. Because discrepancies among the local clocks can be expected, and because Cyclone network protocols require tight temporal coordination, clock synchronization is essential. For this purpose, each cycle is divided into a transmission period of fixed (and global) duration and an idle period of variable duration. The variability of the length of the idle period is used to adjust the lengths of the cycles on individual nodes, ensuring both relatively uniform cycle lengths and very low phase discrepancies. It should also be noted that the algorithm presented here does not technically achieve ``clock'' synchronization, but instead achieves the necessary ``cycle'' synchronization. That is, the local clocks can, over time, have widely varying time readings---the times they provide are not in any way synchronized with ``global time'', and local clocks do not adjust their time readings in any way. Rather, it is the cycle start and end times, that remain synchronized. We have developed a lightweight cycle synchronization algorithm for such networks, and have verified its performance both via simulation and analysis. Initial analysis focuses on an idealized model of the network, in which clock rates, link latencies, discretization errors, and errors due to noisy transmission links are ignore. Using this model, system behavior is described by a system of difference equations which can be analyzed using Markov chain techniques, since the key variable in the matrix equations turns out to be the transition matrix for an ergodic Markov chain. I showed that cycle synchronization properties are related to the convergence properties and rate of this transition matrix. Our second stage model includes the error and noise factors omitted in the base case, and thus provides a more realistic barometer of system performance. Relying on methods from transform theory and function theoretic operator theory, I showed that even in this case, cycles remain synchronized within tolerable levels. Though theoretically satisfying, the major impact of the algorithm is the potential for dramatically lowering the synchronization costs of synchronous optical networks, both in terms of the bandwidth required for synchronization protocols, and in terms of hardware, as our algorithm eliminates the need for cesium clocks (or near cesium accuracy clocks).
  
  
• Information Dynamics

Projects on which I have worked in the past

• The Isotach Project in the Department of Computer Science at the University of Virginia (joint work with members of the Isotach Group at the University of Virginia)
  
  Isotach systems are parallel and/or distributed systems designed to provide synchronization mechanisms with substantially reduced overhead. This is accomplished by providing strong guarantees regarding message delivery order. These guarantees provide sequential consistency and atomicity over the operations performed by parallel programs without the need for more expensive traditional synchronization methods such as locks and barriers. Isotach systems achieve event ordering through an extension of Lamport's notion of logical time: Isotach logical time is represented as an ordered n-tuple of nonnegative integers. Message logical delivery times satisfy the isotach invariant, which states that a message sent at time (i,j,k) will be delivered at time (i+ d, j, k), where d is the logical distance between the source and destination. Since this invariant guarantees that messages travel through the network at a constant logical rate, a process can control the receive time of a message by knowing the logical distances to destinations, and controlling when messages are emitted into the network. Logical time is advanced, and the network kept loosely synchronized (in physical time), through a token passing mechanism. Although Isotach networks should theoretically achieve greatest efficiency with the help of special hardware components, they can be built entirely in software using commercial off-the-shelf hardware. An initial prototype system (dubbed V1 and described in J. Regehr's Masters thesis, which can be found here) was built under a DARPA contract by the Isotach group at the University of Virginia. The three principle system components, the switch interface unit (SIU), token manager (TM), and shared memory manager (SMM) modules, were initially implemented in software using a Myrinet network running Illinois Fast Messages v1.1, and 180 and 200 MHz Pentium Pro and 166 MHz Pentium machines running Red Hat Linux. In V1, the SIU code was split between the processors on the Myrinet network interface boards (LANais) and the corresponding hosts, the TM code ran on LANai boards attached to hosts whose only purpose was to support the TMs, and the SMM code ran on each (non TM) host. In the V2 prototype, that I helped implement, the SIUs and TMs are special hardware devices, with the SIUs located in-link between the network interface boards and the switches to which these boards are connected, and the TMs attached directly to a port on each network switch. My contributions to the Isotach effort involved implementing a software SIU capable of interoperating with and testing the hardware SIU, investigating the interplay between various high performance messaging layers and Isotach primitives, and exploring general fault tolerance principles in distributed systems and their possible application to Isotach.
  
  
• Spectral Multiplicity Theory:
  
  In a past life, I was a mathematician. I worked in the area of function theoretic operator theory, and in particular looked at question involving spectral multiplicity theory. I studied unitary operators on L²(R) of the form T = F M_g F^-1M_u, where F is the Fourier transform, M_f denotes multiplication by f, g is in H^infinity(R), and |u| = 1 almost everywhere. I obtained a complete description of the spectral multiplicity theory for these operators, and this allowed a description of T in terms of shift operators and (M_u)_ac, the well understood absolutely continuous part of M_u acting on the reducing subspace H_ac of L²(R). Specifically, if the dimension of the orthogonal complement (in H²) of gH², which is a shift invariant subspace, is infinite, then T is a bilateral shift of infinite multiplicity. If the subspace has finite dimension n, then T is unitarily equivalent to the direct sum of U_n and an operator A, where A is the restriction of the the n-fold direct sum of (M_u)_ac to a reducing subspace of the n-fold direct sum of H_ac (containing at least one summand H_ac), and U_n is a bilateral shift of multiplicity n. If in addition n=1, then T is unitarily equivalent to the orthogonal direct sum of U₁ and (M_u)_ac.