Home
Biography
Publications
       Book
       Papers
       Patents
Research
Teaching
Editorial


Eli Upfal


Brown University
P.O. Box 1910
Providence, RI 02912
USA
Voice: 401-863-7645
Fax: 401-863-7657
Mail: eli@cs.brown.edu
 

 

 

 

    

 

Patents:

 F.P. Preparata and E. Upfal. “Systems and Methods for Sequencing by Hybridization II”. U.S. patent 7,034,143, April 25, 2006.

 F.P. Preparata and E. Upfal. “Systems and Methods for Sequencing by Hybridization I”. U.S. patent 6,689,563, February 10, 2004.

J. Palmer, R. Strong, and E. Upfal. “Method and Apparatus for Accessing Shared Resources with Asymmetric Safety in Multiprocessing System”. U.S. Patent 6,748,438, June 8, 2004.

 J. Palmer, R. Strong, and E. Upfal. “Method and Apparatus for Ordered Reliable Multicast with Asymmetric Safety in Multiprocessing System”. U.S. Patent 6,092,220, July18, 2000.

J. Palmer, R. Strong, and E. Upfal. “Method for Coordinating Membership with Asymmetric Safety in a Distributed System.” U.S. patent 5,923,831, July 13, 1999.

J.L. Hafner, N. Megiddo, and E. Upfal. “Fast querysearch in large dimension database” U.S. patent 5,848,404, December 8, 1998.

 H.T. Olnowich, J. Bruck, J.W. Feeney, M.H. Fisher, E. Upfal, and A.R. Williams. “Multi-stage interconnection network with selectable function — switching apparatus”. U.S. patent 5,835,024, November 10, 1998.

 H.T. Olnowich, J.W. Fenney, J. Bruck, and E. Upfal. “Increasing probability multi­stage network”. U.S. patent 6,226,683, May 1, 2001.

 H.T. Olnowich, J.W. Fenney, J. Bruck, and E. Upfal. “Increasing probability multi­stage network”. U.S. patent 5,542,048, July 30, 1996.

 M. Snir, S. Bruck, E. Upfal, and H.T. Olnowich. “Adaptive switching apparatus for multi-stage networks”. U.S. patent 5,345,229, September 6, 1994.

 S. Arora, T.K. Knight, F.T. Leighton, B.M. Maggs, and E. Upfal. “Switching net­works 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.


Inventors: Preparata; Franco P. (Providence, RI); Upfal; Eliezer (Providence, RI)
Assignee: Brown University Research Foundation (Providence, RI)
 
Appl. No.: 416779
Filed: October 13, 1999

 

Current U.S. Class: 536/24.3 ; 435/6; 536/23.1; 536/24.31; 536/24.32; 536/25.3; 702/20
Current International Class: C07H 21/00 (20060101); C12Q 1/68 (20060101); G06F 19/00 (20060101)
Field of Search: 536/23.1,24.3,24.31,24.32,25.3 702/20 435/6

 

 

 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.


Inventors:

Palmer; John Davis (San Jose, CA); Strong, Jr.; Hovey Raymond (San Jose, CA); Upfal; Eliezer (Providence, RI)

Assignee:

International Business Machines Corporation (Armonk, NY)

Appl. No.:

971276

Filed:

November 17, 1997

 

Current U.S. Class:

709/229; 709/220; 709/221; 709/222; 713/201

Intern'l Class:

G06F 015/16

Field of Search:

709/220,221,201,208,209,229,223,224 713/200,201 714/11,12,5,43 370/254

 

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.


Inventors:

Preparata; Franco P. (Providence, RI); Upfal; Eliezer (Providence, RI)

Assignee:

Brown University Research Foundation (Providence, RI)

Appl. No.:

735776

Filed:

December 13, 2000

Current U.S. Class:

435/6

Intern'l Class:

C12Q 001/68

Field of Search:

435/6 436/94

  

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.


Inventors:

Olnowich; Howard Thomas (Endwell, NY); Bruck; Jehoshua (Palo Alto, CA); Feeney; James William (Endicott, NY); Upfal; Eli (Palo Alto, CA)

Assignee:

International Business Machines Corporation (Armonk, NY)

Appl. No.:

625379

Filed:

April 1, 1996

Current U.S. Class:

709/238

Intern'l Class:

G06F 015/173

Field of Search:

395/800 370/60 709/238,239,240,243

  

Method and apparatus for ordered reliable multicast with asymmetric safety in a multiprocessing system

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.


Inventors:

Palmer; John Davis (San Jose, CA); Strong, Jr.; Hovey Raymond (San Jose, CA); Upfal; Eliezer (Palo Alto, CA)

Assignee:

International Business Machines Corporation (Armonk, NY)

Appl. No.:

972111

Filed:

November 17, 1997

Current U.S. Class:

714/43; 709/220

Intern'l Class:

G06F 011/30

Field of Search:

714/43,55,56,749,814,815 709/237,220 364/240.9,241.8

   

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.


Inventors:

Palmer; John Davis (San Jose, CA); Strong, Jr.; Hovey Raymond (San Jose, CA); Upfal; Eliezer (Providence, RI)

Assignee:

International Business Machines Corporation (Armonk, NY)

Appl. No.:

924811

Filed:

September 5, 1997

Current U.S. Class:

714/12

Intern'l Class:

G06F 011/00

Field of Search:

395/182.1,182.11,182.02,185.1,200.11

 

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.


Inventors:

Hafner; James Lee (San Jose, CA); Megiddo; Nimrod (Palo Alto, CA); Upfal; Eliezer (Palo Alto, CA)

Assignee:

International Business Machines Corporation (Armonk, NY)

Appl. No.:

823396

Filed:

March 24, 1997

Current U.S. Class:

707/3; 707/5; 707/6; 707/100; 707/101

Intern'l Class:

G06F 017/30

Field of Search:

707/3,100,101,5,6


  

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."


Inventors:

Olnowich; Howard Thomas (Endwell, NY); Bruck; Jehoshua (La Canada, CA); Feeney; James William (Endicott, NY); Fisher; Michael Hans (Rochester, MN); Upfal; Eliezer (Palo Alto, CA); Williams; Arthur Robert (Croton-On-Hudson, NY)

Assignee:

International Business Machines Corporation (Armonk, NY)

Appl. No.:

481855

Filed:

June 7, 1995

Current U.S. Class:

340/2.22; 340/2.23; 370/381; 370/388; 379/273; 710/316

Intern'l Class:

H03K 017/04

Field of Search:

340/825.79,825.03,825.8,826,825.89 370/388,398,397,399,381,379,359 326/41,38 395/312,800,311 364/514 C 379/219,220,221,224,268,271,272,273,291,292,306

 

 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.


Inventors:

Olnowich; Howard T. (Endwell, NY); Bruck; Jehoshua (Palo Alto, CA); Feeney; James W. (Endicott, NY); Upfal; Eli (Palo Alto, CA)

Assignee:

International Business Machines Corporation (Armonk, NY)

Appl. No.:

946514

Filed:

September 17, 1992

Current U.S. Class:

709/243; 340/2.6; 370/388

Intern'l Class:

H01J 013/00

Field of Search:

395/275,200,200.15 340/825.8 370/54 364/238.1,242.94,DIG. 1

 

 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.


Inventors:

Arora; Sanjeev (Berkeley, CA); Knight, Jr.; Thomas F. (Belmont, MA); Leighton; Frank T. (Newton Center, MA); Maggs; Bruce M. (Princeton, NJ); Upfal; Eliezer (Palo Alto, CA)

Assignee:

Massachusetts Institute of Technology (Cambridge, MA)

Appl. No.:

218318

Filed:

March 25, 1994

Current U.S. Class:

340/2.21; 370/351; 370/388; 379/271; 379/272

Intern'l Class:

H01H 067/00

Field of Search:

340/826,827,825.8,825.16 370/54,60,94.1 379/271,272,273,274,275,277,8,9,15,16,17

  

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.


Inventors:

Olnowich; Howard T. (Endwell, NY); Bruck; Jehoshua (Palo Alto, CA); Snir; Marc (Briarcliff Manor, NY); Upfal; Eli (Palo Alto, CA)

Assignee:

International Business Machines Corporation (Armonk, NY)

Appl. No.:

947023

Filed:

September 17, 1992

Current U.S. Class:

370/360; 370/384

Intern'l Class:

H04Q 001/00

Field of Search:

340/825.8,825.89,825.3,825.31 370/16,54,94.1,60