 |
Home |
|
|
Biography |
|
|
Publications |
|
Book |
|
|
Papers |
|
|
Patents |
|
|
|
Research |
|
|
Teaching |
|
|
Editorial |
 | |
|
| |
 |
 | |
 | ||
 |
 | |
| ||
|
| ||
|
| ||
|
Patents: S. Arora, T.K. Knight, F.T. Leighton, B.M. Maggs, and E. Upfal. “Switching networks with expansive and/or dispersive logical clusters message routing”. U.S. patent 5,521,591, March 1996.
Systems and methods for
sequencing by hybridization II Abstract The systems and methods described herein relate to nucleic acid probes comprising a a pattern of universal and designate nucleotides, or `gapped` probes, and the use of sets of gapped probes in sequencing by hybridization to determine the sequence of nucleic acid sequences. The inclusion of universal nucleotides in the probes allows for efficient and rapid sequencing of longer nucleotide sequences than can be sequenced using traditional probes. The systems and methods described herein also relate to apparatus for sequencing nucleic acids which include gapped probes, as well as computer systems capable of analyzing data generated using gapped probes in such apparatus.
Method and apparatus for accessing shared resources with asymmetric safety in a multiprocessing system Abstract In a multiprocessing system, access to a shared resource is arbitrated among multiple computing nodes. The shared resources has a membership view resulting from a predetermined membership protocol performed by the shared resource and the computing nodes. Preferably, this membership protocol includes a termination condition guaranteeing asymmetric safety among all members of the multiprocessing system. The shared resource arbitrates access to itself by fencing computing nodes outside shared resource's membership view. In one embodiment, the shared resource may comprise a data storage facility, such as a disk drive. Illustratively, computation of the shared resource's membership view may employ a procedure where each computing node subscribes to the resource during prescribed membership intervals.
System and methods for sequencing by hybridization I Abstract The systems and methods described herein relate to nucleic acid probes comprising a a pattern of universal and designate nucleotides, or `gapped` probes, and the use of sets of gapped probes in sequencing by hybridization to determine the sequence of nucleic acid sequences. The inclusion of universal nucleotides in the probes allows for efficient and rapid sequencing of longer nucleotide sequences than can be sequenced using traditional probes. The systems and methods described herein also relate to apparatus for sequencing nucleic acids which include gapped probes, as well as computer systems capable of analyzing data generated using gapped probes in such apparatus.
Increasing probability multi-stage network Abstract Disclosed is is a switch-based network interconnection which uses intelligent switching apparatus devices for improving the performance and connection establishing capability of multi-stage switching networks. The invention method is particularly effective In asynchronous circuit-switched networks. The most important feature of the invention methodology is the an increasing probability for the success of making a connection through all the stages of a multi-satge network. As a connection progresses through a multi-stage network, it must win successive stages of the network, one at a time, until it has made its way from on side of the network to the other and established the commanded source-to-destination connection. The uniqueness in the present invention is that as the connection at each stage of the network is established, looking forward to the next stage, the probability will be greater of establishing the next connection without encountering blocking than it was for the present stage. This presents an ever increasing probability for establishing a successful connection as a path works its way through the network. This is opposite of most traditional networks, whose probabiltiy for success diminishes with every stage in the connection sequence.
Abstract Ordered machine-readable messages are reliably delivered among processing members in a multiprocessing computer system. The system includes multiple processing nodes, each having a unique source-ID and a membership view including one or more of the processing nodes with which it can nominally exchange messages. When a stimulus message is received by a first processing node, the node increments a coordinated local counter (CC). The node also sends a multicast message to all processing nodes in the first node's membership group. The multicast message includes the received stimulus message, the incremented CC value, and the first node's source-ID. The node further sets a timer, exclusively associated with the incremented CC value. When a multicast message is received at a processing node, the node performs a multicast input processing routine. The node sets its CC equal to the greater of its current value or the received multicast message's CC value. The node also sends an acknowledgement message to all processing nodes in its membership group. Also, in response to the multicast message, the node sets a timer, exclusively associated with the received multicast message's CC value. Whenever a node's timer associated with a CC value expires before messages with the same CC value have been received from each of the node's membership group, the node invokes a membership protocol requiring asymmetric safety.
Method for coordinating membership with asymmetric safety in a distributed system Abstract A method is disclosed for coordinating membership subject to an asymmetric safety condition from multiple processes in a distributed system. Each is callable by a distributed application for system status or for executing tasks of the application. Initially, each process sends the other processes its view on their status, where the view includes the names of a group of the processes. It then waits for similar views from other processors except those regarded as failed in its own view, up to a predetermined timeout. Each process then generates a resulting view by intersecting its local view with the names of those processes from which it has received views. The local views are updated based on the resulting views and again exchanged until a termination condition occurs.
Fast query search in large dimension database Abstract A computer-implemented database search method includes arranging data points in a tree structure, with upper nodes being labeled by respective randomly selected representative data point and with the distance between each data point which is related to a first node and the label of the first node being less than the distance between the data point and the label of nodes in other branches. When a query is received, the distance between the query and the label of each node in the upper-most level is determined, and the nodes arranged in sequence, shortest distance first. Then, the process is repeated for the first "f" nodes in the sequence, and so on, until a sequence of leaves (i.e., data points having no dependent nodes or leaves) is obtained. The first "k" leaves are returned as the "k" closest database matches to the query. Alternatively, geometric information pertaining to the data points is recorded when the database is populated, and then, for query execution, nodes of data are ranked according to the geometric information as it relates to the query, with the node rankings terminated when a high bound for the geometric relationship between the query and a node is reached.
Multi-stage interconnection network with selectable function switching apparatus Abstract The present invention addresses the limitations of prior art ALLNODE switches by including dual priority, adaptive, path seeking, and flash-flood functionalities in a single ALLNODE switch. The switch of the present invention further includes a selection device responsive to a selection signal for enabling the selection of the mode of switch operation from any one of the foregoing functionalities. The selection signal is applied to the switch in a number of different ways including: the transmission of a command over the data path interface to the switch; the transmission of a command over special purpose serial or parallel control lines; or via hardwiring. Thus, the selection of functionality for the switch is capable of being made in either a dynamic or static fashion. The present invention further comprises two new high performance networks utilizing the selectable function ALLNODE switch. The networks have a different functionality being performed at each stage, and comprise a "Multi-Dilated Path Seeking Network" and a "Nested Path Seeking and Flash-Flood Network."
Increasing probability multi-stage network Abstract A multi-stage circuit switched network for improving connection establishment using intelligent switching devices. As a transmission makes its way through the network stages, the probability of connecting to a destination increases, i.e., the chance of encountering a blocked device output is decreased. This is opposite of most traditional networks, whose probability for success diminishes with every stage in the connection sequence.
Switching networks with expansive and/or dispersive logical clusters for message routing Abstract A class of switching networks is comprised of expansive logical clusters and/or dispersive logical clusters. These clusters are of low degree. The class of networks include multibutterfly networks as well as multi-Benes networks. These networks provide for fault tolerance and routing and for efficient routing. Moreover, routing is provided in a non-blocking fashion.
Adaptive switching apparatus for multi-stage networks Abstract Disclosed is a method and apparatus for improving the performance and connection establishing capability of multi-stage switching networks by providing additional intelligent features in the individual switching apparatus devices at each stage of the network. The invention method is particularly effective in asynchronous circuit-switched networks. The most important feature to be added is adaptivity of the switching apparatus; where adaptivity means the ability of each switching element to determine for itself which of several optional alternate paths to try at each stage of the network based on availability. This is a better approach because it brings the decision directly to the switching apparatus involved, which has the data required to make an intelligent path selection decision to circumvent blocking in the multi-stage network.
|
