Source: http://www.google.se/patents/US8051425?hl=sv
Timestamp: 2013-05-22 18:29:43
Document Index: 585473807

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'application No. 02756944']

Patent US8051425 - Distributed system with asynchronous execution systems and methods - Google PatentS�k Bilder Kartor Play YouTube Nyheter Gmail Drive Mer » Avancerad patents�kning | Webbhistorik | Logga in Avancerad patents�kning PatentSystems and methods are provided for reducing latency in distributed systems by executing commands as sufficient information and system resources become available. In one embodiment, commands in a transaction include dependency information and an execution engine is configured to execute the commands...http://www.google.se/patents/US8051425?utm_source=gb-gplus-sharePatent US8051425 - Distributed system with asynchronous execution systems and methods PublikationsnummerUS8051425 B2Typ av kung�relseBeviljande Ans�kningsnummer11/262,308 Publiceringsdatum1 nov 2011 Registreringsdatum28 okt 2005 Prioritetsdatum29 okt 2004�ven publicerat somUS20060101062 UppfinnarePeter J. GodmanDarren P. Schack Ursprunglig innehavareEmc CorporationIvy Holding, Inc.Isilon Systems LlcIsilon Systems, Inc. USA-klassificering718/106709/227709/219718/102 Internationell klassificeringG06F15/16G06F9/46 Kooperativ klassningG06F9/5038 Europeisk klassificeringG06F9/50A6EH�nvisningarCitat fr�n patent (127)Citat fr�n andra k�llor (87)Externa l�nkarUSPTO �verl�telse av �gander�tt till patent som har registrerats av USPTO EspacenetDistributed system with asynchronous execution systems and methodsUS 8051425 B2 Sammanfattning Systems and methods are provided for reducing latency in distributed systems by executing commands as sufficient information and system resources become available. In one embodiment, commands in a transaction include dependency information and an execution engine is configured to execute the commands as the dependencies become satisfied. In some embodiments, the commands also include priority information. If sufficient resources are not available to execute two or more commands with satisfied dependencies, the execution engine determines an order for executing the commands based at least in part on the priority information. In one embodiment, time-intensive commands are assigned a higher priority than commands that are expected to take less time to execute.
obtaining, by a first computing node, a first command and a second command that define functions to be performed in the transaction, wherein the first command includes dependency information that comprises a first local dependency that must be satisfied before the first command is executed and a first remote dependency that must be satisfied before the first command is executed, and wherein the second command includes dependency information that comprises a second dependency that must be satisfied before the second command is executed;
holding the first command in a waiting state until the first local dependency is satisfied;
determining that the second dependency is satisfied;
causing the execution of the second command;
determining that the first local dependency is satisfied and that there is a first remote dependency that must be satisfied;
transmitting the first command to a second computing node for asynchronous execution, the second computing node to determine when to perform the functions defined by the first command based on the first remote dependency included in the first command; and
determining that the first command has been executed at the second computing node.
2. The method of claim 1, wherein determining that the first local dependency is satisfied comprises determining that the second command has been executed.
3. The method of claim 1, wherein the first command and the second command include prioritization information.
4. The method of claim 1, wherein causing the execution of the second command comprises performing the function defined by the second first command on the first computing node.
5. The method of claim 1, wherein causing the execution of the second command comprises:
transmitting the second command to the second computing node for execution, the second computing node to determine when to perform the functions defined by the second command.
receiving data from the second computing node, wherein the data from the second computing node corresponds to data resulting from the execution of at least one of the first command and the second command.
7. The method of claim 1, wherein the first computing node and the second computing node comprise smart storage units.
8. The method of claim 1, wherein the transaction is selected from a group comprising one or more of:
a plurality of commands, each command structured to include dependency information and priority information; and
a plurality of nodes comprising a first node and a second node, each node comprising at least one computer processor,
obtain a first command and a second command that define functions to be performed in a transaction, wherein the first command includes dependency information that comprises a first dependency that must be satisfied before the first command is executed, and wherein the second command includes dependency information that comprises a second local dependency that must be satisfied before the second command is executed and a second remote dependency that must be satisfied before the second command is executed;
process the dependency information included in the first command;
execute the first command only after the first dependency is satisfied;
process the dependency information included in the second command;
transmit the second command to a second node for asynchronous execution only after the second local dependency is satisfied; and
determine that the second node has executed the second command; and
receive the second command from the first node;
process the dependency information associated with the second command; and
execute the second command only after the second remote dependency is satisfied.
10. The distributed system of claim 9, wherein the second local dependency is satisfied after the first command has been executed.
11. The distributed system of claim 9, wherein the first dependency is satisfied after the second command has been executed.
12. The distributed system of claim 9, wherein the first node is further configured to execute the second command subsequent to the second local dependency being satisfied.
13. The distributed system of claim 9, wherein the second node is further configured to transmit a third command to the first computing device for asynchronous execution, the first computing device to determine when to perform the functions defined by the third command based on dependency information included in the third command.
14. The distributed system of claim 9, wherein the second node is further configured to transmit result data to the first node, wherein the result data corresponds to data resulting from the execution of the second command.
15. The distributed system of claim 9, wherein the plurality of nodes comprise smart storage units.
16. The distributed system of claim 9, wherein the transaction is selected from a group comprising one or more of:
REFERENCE TO RELATED APPLICATIONS The present application claims priority benefit under 35 U.S.C. �119(e) from U.S. Provisional Application No. 60/623,846, filed Oct. 29, 2004 entitled �Distributed System with Asynchronous Execution Systems and Methods,� and U.S. Provisional Application No. 60/628,527, filed Nov. 15, 2004 entitled �Distributed System with Asynchronous Execution Systems and Methods.� The present application hereby incorporates by reference herein both of the foregoing applications in their entirety.
The present application relates to U.S. application Ser. No. 11/262,306, titled �Non-Blocking Commit Protocol Systems and Methods,� filed on even date herewith, which claims priority to U.S. Provisional Application No. 60/623,843, filed Oct. 29, 2004 entitled �Non-Blocking Commit Protocol Systems and Method;� and U.S. application Ser. No. 11/262,314, titled �Message Batching with Checkpoints Systems and Methods�, filed on even date herewith, which claims priority to U.S. Provisional Application No. 60/623,848, filed Oct. 29, 2004 entitled �Message Batching with Checkpoints Systems and Methods,� and U.S. Provisional Application No. 60/628,528, filed Nov. 15, 2004 entitled �Message Batching with Checkpoints Systems and Methods.� The present application hereby incorporates by reference herein all of the foregoing applications in their entirety.
After starting 106 the transaction 100, the computer network executes a first command 110 (shown as �CMD_A�). The first command 110 may be executed on the local node, sent to one or more remote nodes, or both. The computer network may wait for the first command 110 to be completed before continuing with the transaction 100. If, for example, the first command 110 is sent to one or more remote nodes for execution thereon, the local node will wait until it receives a response from each of the remote nodes.
Once the first command 110 is complete, the computer network executes a second command 120 (shown as �CMD_B�). The computer network waits for the second command 120 to be completed before executing a third command 130 (shown as �CMD_C�). Again, the computer network waits for the third command 130 to be completed before executing a fourth command 140 (shown as �CMD_D�). Once the fourth command 140 is completed, the transaction 100 ends 108.
SUMMARY Thus, it is advantageous to use techniques and systems for reducing latency in distributed systems by executing commands as sufficient information and system resources become available. In one embodiment, commands in a transaction include dependency information and an execution engine is configured to execute the commands as the dependencies become satisfied. In addition, or in other embodiments, the commands also include priority information. If sufficient resources are not available to execute two or more commands with satisfied dependencies, the execution engine determines an order for executing the commands based at least in part on the priority information. In one embodiment, time-intensive commands are assigned a higher priority than commands that are expected to take less time to execute.
BRIEF DESCRIPTION OF THE DRAWINGS Systems and methods that embody the various features of the invention will now be described with reference to the following drawings, in which:
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS Rather than executing commands sequentially, an execution engine, according to one embodiment, processes commands asynchronously as sufficient information and system resources become available. The commands include dependency information that defines relationships among the commands. For example, a first command may include dependency information that specifies that the execution engine is to hold the first command in a waiting state until determining that one or more nodes in a distributed system have successfully executed a second command. Once the dependency is satisfied, the execution engine moves the first command to a runnable state where it can be executed by the nodes as system resources become available.
The dependency field 220 specifies conditions (also referred to herein as �waiters�) for executing the action defined by the function field 210. For example, the dependency field 220 may specify that certain data should be available before the action defined by the function field 210 is executed. As another example, the dependency field 220 may specify that a node in a distributed system execute one or more other commands to completion before executing the action defined by the function field 210. In other embodiments, the dependency field 220 may store a count of commands (for example, wait count) upon which the command should wait upon as well as a list of other commands that are awaiting completion of this command. As discussed in detail below, an execution engine is configured to move the command 200 from a waiting state to a runnable state as the waiters specified in the dependency field 220 are satisfied. Once in the runnable state, one or more nodes in the distributed system can execute the action defined by the function field 210.
HIGH: Reads which may come from a high latency device. (for example, disk); allocation, upon which many commands may depend. MED: Any command involving a remote node; can be used for everything except parity generation and block reconstruction. LOW: Parity generation, reconstruction. Including the function field 210, the dependency field 220, and the priority field 230 within the command data structure 200 also allows a distributed system to perform a transaction asynchronously. For example, a local node can send commands to a remote node that determines when and in what order to execute the commands without waiting for further messages from the local node. The remote node makes these determinations based on the information in the dependency field 220 and the priority field 230. Pushing control of command ordering from local nodes to remote nodes reduces the number of messages sent across the network, which further reduces latency.
Dependency graphs are one example way to illustrate relationships between commands in a transaction. FIG. 3 is an exemplary dependency graph according to one embodiment illustrating relationships between a plurality of commands in a transaction 300 executed on a computer system. The transaction 300 comprises a start command 310 defining the beginning of the transaction 300, a first command 312 (shown as �CMD_A�), a second command 314 (shown as �CMD_B�), a third command 316 (shown as �CMD_C�), a fourth command 318 (shown as �CMD_D�) and an end command 320 defining the end of the transaction 300. The commands 312, 314, 316, 318 can be executed, for example, on a local node of a distributed system, on a remote node of the network, or both.
The node 410 comprises a layout manager module 412 and an execution manager module 414. As used herein, the word module is a broad term having its ordinary and customary meaning and can also refer to logic embodied in hardware or firmware, or to a collection of software instructions (i.e., a �software module�), possibly having entry and exit points, written in a programming language, such as, for example, C or C++. A software module may be compiled and linked into an executable program, installed in a dynamic link library, or may be written in an interpreted programming language such as BASIC, Perl, or Python. It will be appreciated that software modules may be callable from other modules or from themselves, and/or may be invoked in response to detected events or interrupts. Software instructions may be embedded in firmware, such as an EPROM. It will be further appreciated that hardware modules may be comprised of connected logic units, such as gates and flip-flops, and/or may be comprised of programmable units, such as programmable gate arrays or processors. The modules described herein are preferably implemented as software modules, but may be represented in hardware or firmware.
In addition, the layout manager module 412 may be configured to determine a new file layout during a restriping process used when the protection scheme of a file is changed. For example, if a file goes from 3+1 parity protection to 4+1 parity protection, the layout manager module 412 determines a new file layout so data can be moved to storage units in the new layout in a manner that meets the new parity protection. In one embodiment, the layout manager module 412 continues to manage the old layout until the new layout is complete to allow users access to the file under the old layout such that the data is protected by the old parity scheme until the new parity scheme is available. In one embodiment, when repairing data, the number of protection groups for a single transaction may be calculated by using the least common-multiple of the old protection group's parity group size �n� and the new protection group's parity group size �n� such that no individual blocks are covered by two different parity protection blocks.
The execution manager module 414 is also referred to herein as an �execution engine� or �engine.� Exemplary pseudocode according to one embodiment of the invention for executing the engine can be found in the attached Appendix which forms a part of the patent application. It should be recognized, however, that the exemplary pseudocode is not meant to limit the scope of the invention.
In one embodiment, an execution engine is used in a distributed file system as described in U.S. patent application Ser. No. 10/007,003, filed Nov. 9, 2001 and issued as U.S. Pat. No. 7,685,126 on Mar. 23, 2010, which claims priority to Application No. 60/309,803 filed Aug. 3, 2001, and U.S. patent application Ser. No. 10/714,326, filed Nov. 14, 2003, which claims priority to Application No. 60/426,464, filed Nov. 14, 2002, all of which are hereby incorporated herein by reference herein in their entirety. For example, the execution engine may be used in an intelligent distributed file system that enables the storing of file data among a set of smart storage units which are accessed as a single file system and utilizes a metadata data structure to track and manage detailed information about each file, including, for example, the device and block locations of the file's data blocks, to permit different levels of replication and/or redundancy within a single file system, to facilitate the change of redundancy parameters, to provide high-level protection for metadata and to replicate and move data in real-time. In addition, the execution engine may be configured to write data blocks or restripe files distributed among a set of smart storage units in the distributed file system wherein data is protected and recoverable even if a system failure occurs during the restriping process.
FIGS. 8 and 9 illustrate one embodiment of recovering mirrored data when a node fails in a distributed file system. Recovering data may include, for example, using error correction to reconstruct lost data, generating error correction data to reprotect lost data, and/or generating error correction data to protect data using a different error correction scheme. FIG. 8 is a block diagram according to one embodiment representing recovery of lost data blocks using a mirrored protection scheme in a distributed file system. A first data block D1 is stored on a first node (i.e., �Node 1�), a second data block D2 is stored on a second node (i.e., �Node 2�), and a third data block D3 is stored on a third node (i.e., �Node 3�). The system uses a mirroring scheme wherein copies of the data blocks D1, D2, D3 are respectively stored in different nodes than the originals. A copy of the first data block D1 is stored on the second node as mirror data block M1. A copy of the second data block D2 is stored on the third node as mirror data block M2. A copy of the third data block D3 is stored on a fourth node (i.e., �Node 4�) as mirror data block M3. Thus, the data blocks D1, D2, D3 have corresponding copies M1, M2, M3 such that if one of the nodes fail, information stored on that node can be recovered.
FIG. 10 is an exemplary block diagram according to one embodiment representing data blocks written to nodes in a distributed file system using a 3+1 parity scheme. As shown in FIG. 10, a first data block D1, a second data block D2 and a third data block D3 are written from a data buffer 1000 to three nodes. The first data block D1 is written to a first node (i.e., �Node 1�), the second data block D2 is written to a second node (i.e., �Node 2�), and the third data block D3 is written to a third node (i.e., �Node 3�).
Returning to FIG. 10, parity data P corresponding to the three data blocks D1, D2, D3 is written to a fourth node (i.e., �Node 4�). In one embodiment, the system generates the parity data P by performing an XOR operation on the three data blocks D1, D2, D3 though other error correction schemes may be used. The XOR operation can be performed on a bit-by-bit, byte-by-byte, or block-by-block basis. If one of the four nodes fails, the information on the failed node can be recovered by performing an XOR operation on the other three nodes. If the first node fails, for example, the first data block D1 can be recovered by XORing the second data block D2, the third data block D3 and the parity data P, and then storing the recovered first data block D1 in a new location. In such a case, the parity data P would not need to be recomputed.
The 3+1 parity scheme includes a first 3+1 parity group 1210 and a second 3+1 parity group 1212. The first 3+1 parity group 1210 includes a first data block D1 stored on a first node (i.e., �Node 1�), a second data block D2 stored in a second node (i.e., �Node 2�), a third data block D3 stored in a third node (i.e., �Node 3�), and first parity data P1 stored in a fourth node (i.e., �Node 4�). In one embodiment, the first parity data P1 is generated by performing an XOR operation on the first data block D1, the second data block D2, and the third data block D3.
The second 3+1 parity group 1212 includes a fourth data block D4 stored on the second node, a fifth data block D5 stored on a fifth node (i.e., �Node 5�), a sixth data block D6 stored on the fourth node, and a second parity data P2 stored on the first node. In one embodiment, the second parity data P2 is generated by performing an XOR operation on the fourth data block D4, the fifth data block D5, and the sixth data block D6.
Appendix This Appendix forms a part of the patent application entitled �DISTRIBUTED SYSTEM WITH ASYNCHRONOUS EXECUTION SYSTEMS AND METHODS,�.
This Appendix includes a list of exemplary commands and pseudocode for an execution engine that reduces latency in a distributed file system by executing commands as sufficient information and system resources become available. It should be recognized, however, that the list of exemplary commands and pseudocode is not meant to limit the scope of the invention, but only to provide details for a specific embodiment. This Appendix includes the Appendices incorporated by reference above from U.S. Provisional Application No. 60/623,846, filed Oct. 29, 2004 entitled �Distributed System with Asynchronous Execution Systems and Methods,� and U.S. Provisional Application No. 60/628,527, filed Nov. 15, 2004 entitled �Distributed System with Asynchronous Execution Systems and Methods,� which are hereby incorporated by reference herein in their entirety.
1. ALLOC(dev,lbns)�Alloc space for the specified blocks 2. FEC(fec_instructions)�Compute FEC group 3. FREE(baddr_range_array)�Free blocks (used by restriper) 4. READ(baddr,dest)�Read the specified block 5. RECONSTRUCT(lbn)�Reconstruct the specified block 6. SETBLKADDRS(void)�Set block addresses into inodes 7. WRITE(data,baddr)�Write data from block to location 8. XFER�Move blocks from a vp to a devvp. 9. ZERO_READ(baddr,dest)�Read the specified block, assuming it was all zero (bzero unaffected region) PSEUDOCODE FOR EXECUTION ENGINE
Citat fr�n patent citerade patent Registreringsdatum Publiceringsdatum S�kande TitelUS51631318 sep 198910 nov 1992Auspex Systems, Inc.Parallel i/o network file server architectureUS51811626 dec 198919 jan 1993Eastman Kodak CompanyDocument management and production systemUS521278422 okt 199018 maj 1993Delphi Data, A Division Of Sparks Industries, Inc.Automated concurrent data backup systemUS523004716 apr 199020 jul 1993International Business Machines CorporationMethod for balancing of distributed tree file structures in parallel computing systems to enable recovery after a failureUS525120612 apr 19915 okt 1993International Business Machines Corp.Hybrid switching system for a communication nodeUS525898413 jun 19912 nov 1993International Business Machines CorporationMethod and means for distributed sparing in DASD arraysUS532962623 okt 199012 jul 1994Digital Equipment CorporationSystem for distributed computation processing includes dynamic assignment of predicates to define interdependenciesUS535959415 maj 199225 okt 1994International Business Machines CorporationPower-saving full duplex nodal communications systemsUS54036392 sep 19924 apr 1995Storage Technology CorporationFile server having snapshot application data groupsUS545987126 aug 199317 okt 1995International Computers LimitedDetection and resolution of resource deadlocks in a distributed data processing systemUS548169923 mar 19952 jan 1996Digital Equipment CorporationDurable atomic storage update managerUS554872421 mar 199420 aug 1996Hitachi Computer Engineering Co., Ltd.File server system and file access control method of the sameUS554879528 mar 199420 aug 1996Quantum CorporationMethod for determining command execution dependencies within command queue reordering processUS55686294 nov 199322 okt 1996At&T Global Information Solutions CompanyMethod for partitioning disk drives within a physical disk array and selectively assigning disk drive partitions into a logical disk arrayUS559670912 nov 199221 jan 1997International Business Machines CorporationMethod and apparatus for recovering parity protected dataUS560666923 maj 199525 feb 1997International Business Machines CorporationSystem for managing topology of a network in spanning tree data structure by maintaining link table and parent table in each network nodeUS56128651 jun 199518 mar 1997Ncr CorporationDynamic hashing method for optimal distribution of locks within a clustered systemUS56492002 dec 199615 jul 1997Atria Software, Inc.Dynamic rule-based version control systemUS56574393 nov 199512 aug 1997International Business Machines CorporationDistributed subsystem sparingUS566894324 maj 199616 sep 1997International Business Machines CorporationVirtual shared disks with application transparent recoveryUS56806217 jun 199521 okt 1997International Business Machines CorporationSystem and method for domained incremental changes storage and retrievalUS56945935 okt 19942 dec 1997Northeastern UniversityDistributed computer database system and methodUS569689519 jun 19959 dec 1997Compaq Computer CorporationFault tolerant multiple network serversUS573482617 sep 199231 mar 1998International Business Machines CorporationVariable cyclic redundancy coding method and apparatus for use in a multistage networkUS575475629 feb 199619 maj 1998Hitachi, Ltd.Disk array system having adjustable parity group sizes based on storage unit capacitiesUS576165929 feb 19962 jun 1998Sun Microsystems, Inc.Method, product, and structure for flexible range locking of read and write requests using shared and exclusive locks, flags, sub-locks, and countersUS577464313 okt 199530 jun 1998Digital Equipment CorporationEnhanced raid write hole protection and recoveryUS57993052 nov 199525 aug 1998Informix Software, Inc.Method of commitment in a distributed database transactionUS580557812 mar 19968 sep 1998International Business Machines CorporationAutomatic reconfiguration of multipoint communication channelsUS580590026 sep 19968 sep 1998International Business Machines CorporationMethod and apparatus for serializing resource access requests in a multisystem complexUS58060656 maj 19968 sep 1998Microsoft CorporationData system with distributed tree indexes and method for maintaining the indexesUS58227907 feb 199713 okt 1998Sun Microsystems, Inc.Voting data prefetch engineUS586231224 okt 199519 jan 1999Seachange Technology, Inc.Loosely coupled mass storage computer clusterUS587056311 okt 19959 feb 1999International Business Machines CorporationMethod and apparatus for optimizing message transmissionUS587841013 sep 19962 mar 1999Microsoft CorporationFile system sort order indexesUS58784146 jun 19972 mar 1999International Business Machines Corp.Constructing a transaction serialization order based on parallel or distributed database log filesUS588404623 okt 199616 mar 1999Pluris, Inc.Apparatus and method for sharing data and routing messages between a plurality of workstations in a local area networkUS588409818 apr 199616 mar 1999Emc CorporationRAID controller system utilizing front end and back end caching systems including communication path connecting two caching systems and synchronizing allocation of blocks in caching systemsUS58843036 feb 199716 mar 1999International Computers LimitedParallel searching techniqueUS58901477 mar 199730 mar 1999Microsoft CorporationScope testing of documents in a search engine using document to folder mappingUS591799826 jul 199629 jun 1999International Business Machines CorporationMethod and apparatus for establishing and maintaining the status of membership sets used in mirrored read and write input/output without loggingUS593383416 okt 19973 aug 1999International Business Machines IncorporatedSystem and method for re-striping a set of objects onto an exploded array of storage units in a computer systemUS59436907 apr 199724 aug 1999Sony CorporationData storage apparatus and method allocating sets of dataUS596396311 jul 19975 okt 1999International Business Machines CorporationParallel file system and buffer management arbitrationUS59667072 dec 199712 okt 1999International Business Machines CorporationMethod for managing a plurality of data processes residing in heterogeneous data repositoriesUS599608916 dec 199730 nov 1999Seachange International, Inc.Loosely coupled mass storage computer clusterUS600000718 maj 19987 dec 1999Monolithic System Technology, Inc.Caching in a multi-processor computer systemUS601466921 okt 199711 jan 2000Sun Microsystems, Inc.Highly-available distributed cluster configuration databaseUS602141428 dec 19981 feb 2000Sun Microsystems, Inc.Single transaction technique for a journaling file system of a computer operating systemUS602916823 jan 199822 feb 2000Tricord Systems, Inc.Decentralized file mapping in a striped network file system in a distributed computing environmentUS603857031 maj 199514 mar 2000Network Appliance, Inc.Method for allocating files in a file system integrated with a RAID disk sub-systemUS604436715 apr 199828 mar 2000Hewlett-Packard CompanyDistributed I/O storeUS605275912 nov 199818 apr 2000Nstor CorporationMethod for organizing storage devices of unequal storage capacity and distributing data using different raid formats depending on size of rectangles containing sets of the storage devicesUS605554321 nov 199725 apr 2000VeranoFile wrapper containing cataloging information for content searching across multiple platformsUS605556411 mar 199825 apr 2000Hewlett Packard CompanyAdmission control where priority indicator is used to discriminate between messagesUS60701726 mar 199730 maj 2000Oracle CorporationOn-line free space defragmentation of a contiguous-file file systemUS60818338 jul 199627 jun 2000Kabushiki Kaisha ToshibaMemory space management method, data transfer method, and computer device for distributed computer systemUS60818835 dec 199727 jun 2000Auspex Systems, IncorporatedProcessing system with dynamically allocatable buffer memoryUS610875917 sep 199722 aug 2000Powerquest CorporationManipulation of partitions holding advanced file systemsUS611718123 dec 199812 sep 2000Sun Microsystems, Inc.Synchronization mechanism for distributed hardware simulationUS612275422 maj 199819 sep 2000International Business Machines CorporationMethod and system for data recovery using a distributed and scalable data structureUS613812621 jul 199924 okt 2000Network Appliance, Inc.Method for allocating files in a file system integrated with a raid disk sub-systemUS61548548 jan 199828 nov 2000Emc CorporationLogical partitioning of a redundant array storage systemUS617337411 feb 19989 jan 2001Lsi Logic CorporationSystem and method for peer-to-peer accelerated I/O shipping between host bus adapters in clustered computer networkUS62020856 dec 199613 mar 2001Microsoft CorportionSystem and method for incremental change synchronization between multiple copies of dataUS620905925 sep 199727 mar 2001Emc CorporationMethod and apparatus for the on-line reconfiguration of the logical volumes of a data storage systemUS62196934 nov 199717 apr 2001Adaptec, Inc.File array storage architecture having file system distributed across a data processing platformUS62263773 jun 19981 maj 2001Avaya Technology Corp.Prioritized transaction server allocationUS627900730 nov 199821 aug 2001Microsoft CorporationArchitecture for managing query friendly hierarchical valuesUS63213451 mar 199920 nov 2001Seachange Systems, Inc.Slow response in redundant arrays of inexpensive disksUS633416819 feb 199925 dec 2001International Business Machines CorporationMethod and system for updating data in a data storage systemUS63538238 mar 19995 mar 2002Intel CorporationMethod and system for using associative metadataUS638462618 apr 20017 maj 2002Micro-Star Int'L Co., Ltd.Programmable apparatus and method for programming a programmable deviceUS638562619 nov 19987 maj 2002Emc CorporationMethod and apparatus for identifying changes to a logical object based on changes to the logical object at physical levelUS639348330 jun 199721 maj 2002Adaptec, Inc.Method and apparatus for network interface card load balancing and port aggregationUS639731122 maj 199528 maj 2002Texas Instruments IncorporatedSystem and method for defragmenting a file systemUS640521924 sep 199911 jun 2002F5 Networks, Inc.Method and system for automatically updating the version of a set of files stored on content serversUS640831316 dec 199818 jun 2002Microsoft CorporationDynamic memory allocation based on free memory sizeUS641525915 jul 19992 jul 2002American Management Systems, Inc.Automatic work progress tracking and optimizing engine for a telecommunications customer care and billing systemUS642178110 aug 199816 jul 2002Openwave Systems Inc.Method and apparatus for maintaining security in a push serverUS643457417 dec 199813 aug 2002Apple Computer, Inc.System and method for storing and retrieving filenames and files in computer memory using multiple encodingsUS64497305 apr 200110 sep 2002Seachange Technology, Inc.Loosely coupled mass storage computer clusterUS645338925 jun 199917 sep 2002Hewlett-Packard CompanyOptimizing computer performance by using data compression principles to minimize a loss functionUS645713930 dec 199824 sep 2002Emc CorporationMethod and apparatus for providing a host computer with information relating to the mapping of logical volumes within an intelligent storage systemUS646344230 jun 19988 okt 2002Microsoft CorporationContainer independent data binding systemUS649684228 maj 199917 dec 2002Survol Interactive TechnologiesNavigating heirarchically organized informationUS649909113 nov 200024 dec 2002Lsi Logic CorporationSystem and method for synchronizing data mirrored by storage subsystemsUS650217211 jan 200231 dec 2002Via Technologies, Inc.Memory accessing and controlling unitUS65021743 mar 199931 dec 2002International Business Machines CorporationMethod and system for managing meta dataUS652313011 mar 199918 feb 2003Microsoft CorporationStorage system having error detection and recoveryUS65264782 feb 200025 feb 2003Lsi Logic CorporationRaid LUN creation using proportional disk mappingUS654644315 dec 19998 apr 2003Microsoft CorporationConcurrency-safe reader-writer lock with time out supportUS654951312 okt 199915 apr 2003AlcatelMethod and apparatus for fast distributed restoration of a communication networkUS655711418 sep 200129 apr 2003Seachange Technology, Inc.Loosely coupled mass storage computer clusterUS65678948 dec 199920 maj 2003International Business Machines CorporationMethod and apparatus to prefetch sequential pages in a multi-stream environmentUS65679267 nov 200120 maj 2003Seachange International, Inc.Loosely coupled mass storage computer clusterUS657124428 okt 199927 maj 2003Microsoft CorporationRun formation in large scale sorting using batched replacement selectionUS65713495 okt 199927 maj 2003Seachange Technology, Inc.Loosely coupled mass storage computer clusterUS657474530 apr 20023 jun 2003Seachange International, Inc.Loosely coupled mass storage computer clusterUS65946554 jan 200115 jul 2003Ezchip Technologies Ltd.Wildcards in radix- search tree structuresUS659466024 jan 200015 jul 2003Microsoft CorporationShare latch clearingUS659474411 dec 200015 jul 2003Lsi Logic CorporationManaging a snapshot volume or one or more checkpoint volumes with multiple point-in-time images in a single repositoryUS659817426 apr 200022 jul 2003Dell Products L.P.Method and apparatus for storage unit replacement in non-redundant arrayUS661879811 jul 20009 sep 2003International Business Machines CorporationMethod, system, program, and data structures for mapping logical units to a storage space comprises of at least one array of storage unitsUS663141113 jul 20017 okt 2003Freshwater Software, Inc.Apparatus and method for monitoring a chain of electronic transactionsUS665855414 okt 19992 dec 2003National Science FoundationElectronic processor providing direct data transfer between linked data consuming instructionsUS666218422 sep 20009 dec 2003International Business Machines CorporationLock-free wild card search data structure and methodUS66716862 nov 200130 dec 2003Pardon GuyDecentralized, distributed internet data managementUS67420208 jun 200025 maj 2004Hewlett-Packard Development Company, L.P.System and method for managing data flow and measuring service in a storage networkUS689548210 sep 199917 maj 2005International Business Machines CorporationReordering and flushing commands in a computer memory subsystemUS690752011 jan 200214 jun 2005Sun Microsystems, Inc.Threshold-based load address prediction and new thread identification in a multithreaded microprocessorUS69204945 okt 200119 jul 2005International Business Machines CorporationStorage area network methods and apparatus with virtual SAN recognitionUS704356720 dec 20029 maj 2006Seagate Technology LlcMethod and apparatus for determining the order of execution of queued commands in a data storage systemUS71035973 okt 20025 sep 2006Mcgoveran David OAdaptive transaction manager for complex transactions and business processUS711393813 feb 200326 sep 2006Gravic, Inc.Method of increasing system availability by splitting a systemUS718174629 jun 200120 feb 2007Intel CorporationInitialization, reconfiguration, and shut down of a module functionUS720680517 nov 200017 apr 2007Oracle International CorporationAsynchronous transcription object management systemUS72900568 sep 200030 okt 2007Oracle International CorporationMonitoring latency of a network to manage termination of distributed transactionsUS73700646 aug 20026 maj 2008Yousefi Zadeh HomayounDatabase remote replication for back-end tier of multi-tier computer systemsUS757766718 sep 200318 aug 2009Netezza CorporationProgrammable streaming data processor for database appliance having multiple processing unit groupsUS2002002920010 sep 20017 mar 2002Dulin CharlesSystem and method for providing certificate validation and other servicesUS2002007816119 dec 200020 jun 2002Philips Electronics North America CorporationUPnP enabling device for heterogeneous networks of slave devicesUS2003023338516 apr 200318 dec 2003Bladelogic,Inc.Method and system for executing and undoing distributed server change operationsUS200401585496 feb 200412 aug 2004Jens JensenMethod and apparatus for online transaction processingUS2004024044418 sep 20032 dec 2004International Business Machines CorporationSystem and method for managing transactions in a messaging systemUS2005004419718 aug 200324 feb 2005Sun Microsystems.Inc.Structured methodology and design patterns for web servicesUS2005013825223 dec 200323 jun 2005Arm LimitedTransaction request servicing mechanismCitat fr�n andra k�llorH�nvisning1Apr. 20, 2004 International Search Report PCT/US03/36699.2Arthur S. Rose, Letter to Steven M. Bauer, Aug. 31, 2007, 4 pages.3Arthur S. Rose, Letter to Steven M. Bauer, Aug. 7, 2006, 2 pages.4Arthur S. Rose, Letter to Steven M. Bauer, Feb. 23, 2007, 1 page.5Arthur S. Rose, Letter to Steven M. Bauer, Jun. 22, 2007, 1 page.6Arthur S. Rose, Letter to Steven M. Bauer, Nov. 9, 2006, 2 pages.7Aug. 6, 2004 International Search Report PCT/US03/33704.8Birk, Y., Deterministic load-balancing schemes for disk-based video-on-demand storage servers, Mass Storage Systems 1995; Storage-At the Forefront of Information Infrastructures', Proceedings of the Fourteenth IEEE Symposium on Monterey, CA, Sep. 11-14, 1995, pp. 17-25.9Birk, Y., Deterministic load-balancing schemes for disk-based video-on-demand storage servers, Mass Storage Systems 1995; Storage�At the Forefront of Information Infrastructures', Proceedings of the Fourteenth IEEE Symposium on Monterey, CA, Sep. 11-14, 1995, pp. 17-25.10Bob Duzett, et al., An Overview of the nCube 3 Supercomputer, IEEE, Jul. 1992, pp. 458-464.11Byteandswitch, "Discovery Chooses Isilon," Apr. 23, 2007, 1 page (Exhibit C).12Coulouris et al., Distributed Systems Concepts and Design, Addison-Wesley, Second Edition, 1994, pp. 353-371 and 377-405.13Darrell D.E. Long et al., Swift/RAID: A Distributed RAID System, Computing Systems, vol. 7, No. 3 Summer 1994, pp. 333-359.14Dorai et al.:, "Transport Threads: Resource Sharing in SMT Processor for High Single-Thread Performance", proceedings of the 2002 International Conference on Parallel Architectures and Complication Techniques, Sep. 2002, 12 pages.15Duchamp, Dan: "Analysis of Transaction Management Performance", ACM Symposium on Operating Systems Principles, Dec. 1989, pp. 177-190.16European Search Report dated May 21, 2007 issued to EP application No. 02756944.1-2201.17Feb. 22, 2008 Int'l Search report PCT/US07/018326, 20 pages.18Garcia-Molina H et al: "Database System Implementation, passage" Database System Implementation, Jan. 1, 2000, pp. I-V, 423-509.19Gerhard Weikum, et al., Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery, Morgan Kaufmann, 2002, pp. 1-435.20Gerhard Weikum, et al., Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery, Morgan Kaufmann, 2002, pp. 1-450.21Gerhard Weikum, et al., Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery, Morgan Kaufmann, 2002, pp. 436-853.22Gerhard Weikum, et al., Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery, Morgan Kaufmann, 2002, pp. 451-863.23Gibson, Garth A. et al., The Scotch Parallel Storage System, IEEE, 1995, pp. 403-410.24Gray J et al: "Transaction processing: concepts and techniques (excerpt), Passage" Transaction Processing: Concepts and Techniques, Jan. 1, 1993, pp. 373-445.25Haerder T et al: "Principles of Transaction-Oriented Database Recovery" ACM Computing Surveys, ACM, New York, NY, US, vol. 15, No. 4, Dec. 1, 1983, pp. 287-317.26Hisayuki Aoki, Parallel Filesystem MFS, IPSJ SIG Technical Reports, Japan, Information Processing Society of Japan, Aug. 26, 1996, vol. 96, No. 79, pp. 31 to 36 (stamped Citation 1 / English Translation attached) total 23 pages.27IOS Commands, Feb. 6, 2005, Pantz.org, [online], , pp. 1-12 as printed.28IOS Commands, Feb. 6, 2005, Pantz.org, [online], <web.archive.org/web/20050206184604/http://pantz.org/os/ios/ioscommands.shtml>, pp. 1-12 as printed.29IP Forwarding with Cisco Routers Lab Exercises, Jun. 15, 1999 [online], , pp. 1-11 as printed.30IP Forwarding with Cisco Routers Lab Exercises, Jun. 15, 1999 [online], <ws.edu.isoc.org/data1999/1481713642400af6a2de65a/ip�fwd�cisco�config.ppt>, pp. 1-11 as printed.31Isilon Systems, "Isilon IQ Plateform Overview", 4 pages (Exhibit A).32Isilon Systems, "Uncompromising Reliability through Clustered Storage", Sep. 2006, 10 pages (Exhibit B).33Jan. 23, 2009 Examination Report EP 02 75 6944, 5 pages.34Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993, pp. 1-290.35Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993, pp. 1-328.36Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993, pp. 291-628.37Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993, pp. 329-664.38Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993, pp. 630-1070.39Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993, pp. 665-1105.40John Henry Hartman, The Zebra Striped Network File System, 1994, pp. 1-148, University of California at Berkeley.41Keidar,et al.: Increasing the Resilience of Distributed and Replicated Database Systems (1998) pp. 1-25.42Kenneth P. Birman, Building Secure and Reliable Network Applications, Manning, 1996, pp. 1-327.43Kenneth P. Birman, Building Secure and Reliable Network Applications, Manning, 1996, pp. 328-620.44Kumar Akhil, "An analysis of borrowing policies for escrow transactions in a replicated data environment", Institute of Electrical and Electronics Engineers; Proceedings of the International Conference on Data Engineering, Los Angeles, Feb. 5-9, 1990; Los Alamitos, IEEE, Comp. Soc. Press, US. vol. Conf. 6, Feb. 5, 1990, pp. 446-454, XP010018185 ISBN: 978-0-8186-2025-6 p. 446, left-hand column, line 1-p. 447, last line.45Kumar Akhil, "An analysis of borrowing policies for escrow transactions in a replicated data environment", Institute of Electrical and Electronics Engineers; Proceedings of the International Conference on Data Engineering, Los Angeles, Feb. 5-9, 1990; Los Alamitos, IEEE, Comp. Soc. Press, US. vol. Conf. 6, Feb. 5, 1990, pp. 446-454, XP010018185 ISBN: 978-0-8186-2025-6 p. 446, left-hand column, line 1�p. 447, last line.46Levy E., Ed.-Institute of Electrical and Electronics Engineers: "Incremental restart (database management)" Proc. Int. Conf. Data Eng., Kobe, JP, Apr. 8-12, 1991; IEEE Comp. Soc. Press, U.S., vol. Conf. 7, Apr. 8, 1991, pp. 640-648.47Levy E., Ed.�Institute of Electrical and Electronics Engineers: "Incremental restart (database management)" Proc. Int. Conf. Data Eng., Kobe, JP, Apr. 8-12, 1991; IEEE Comp. Soc. Press, U.S., vol. Conf. 7, Apr. 8, 1991, pp. 640-648.48Lougher P. et al., "Scalable storage servers for digital audio and video," International Conference on Storage and Recording Systems, 1994, Keele, UK, Jan. 1, 1994, pp. 140-143.49May 18, 2009 Int'l Search report PCT/US08/059798, 18 pages.50May 8, 2008 Int'l Search report PCT/US07/018324, 13 pages.51MCSA/MSCE/MCDBA Self Paced Training Kit: MS SQL Server 2000 System Administration, May 14, 2003, Microsoft Press, Second Edition, 12 pages.52Michael Stonebraker et al., Distributed RAID: A new Multiple copy Algorithm, IEEE 1990, pp. 430-437, Berkeley, California.53Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996, pp. 1-409.54Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996, pp. 410-871.55Nov. 15, 2002 International Search Report PCT/US02/24728.56Oct. 22, 2009 Int'l Preliminary Report on Patentability PCT/US08/059798, 10 pages.57Oct. 8, 2008 European Supplemental Search Report EP 02 75 6944, 6 pages.58Pei Cao et al., The TickerTAIP parallel RAID architecture, 1993, 12 pages, Princeton, NJ.59Pei Cao et al., The TickerTAIP parallel RAID architecture, ACM Transactions on Computer Systems, vol. 12, No. 3, Aug. 1994, 34 pages, Palto Alto, California.60Peterson, Zachary Nathaniel Joseph, "Data Placement For Copy-On-Write Using Virtual Contiguity," Master of Science in Computer Science Thesis, University of California, Santa Cruz, Sep. 2002, 67 pages.61Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman, Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987, pp. 1-270 .62Ramez Elmasri, Fundamentals of Database Systems 3rd ed, Sep. 30, 1999, Addison-Wesley, pp. 155, 169, 171, 172, 173, 178, 181, 182, 381, 771.63Reddy, P. Krishna et al., Reducing the blocking in two phase commit with backup sites Apr. 15, 2003, Elsevier, pp. 39-47.64Sanjay Ghemawat et al., The Google File System, Symposium on Operating Systems Principles, Oct. 19-22, 2003, 15 pages, Bolton Landing, NY.65Sape Mullender, editor, Distributed Systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 1993, pp. 1-315.66Sape Mullender, editor, Distributed Systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 1993, pp. 1-327.67Sape Mullender, editor, Distributed Systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 1993, pp. 316-595.68Sape Mullender, editor, Distributed Systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 1993, pp. 328-604.69Silaghi, Raul et al.: "Porting OMTTs to CORBA", Lecture Notes in Computer Science, vol. 2888/2003, Nov. 2003, pp. 1521-1542.70Stallings, William, "Operating Systems," Prentice Hall, Fourth Edition, 2001, pp. 197-253 and 265-293.71Steven M. Bauer, Letter to Arthur S. Rose, Feb. 6, 2007, 2 pages.72Steven M. Bauer, Letter to Arthur S. Rose, Jun. 7, 2007 (including claim chart), 28 pages.73Steven M. Bauer, Letter to Arthur S. Rose, Oct. 31, 2006, 1 page.74Steven M. Bauer, Letter to Arthur S. Rose, Sep. 25, 2006, 2 pages.75Steven M. Bauer, Letter to Steve Goldman, Jul. 31, 2006 (including the first page of the patents), 8 pages.76Supp EPO Search Report, App. No. EP 03 78 3599; dated Apr. 29, 2008, 2 pages.77Taneja Group Technology Analysts, "The Power of InfiniBand and Clustered Storage", Dec. 2005, 8 pages (Exhibit E).78Tanenbaum, Andrew S., MINIX Operating System, Japan, Apr. 21, 1989, 1st Edition, pp. 328, 505; Also attached is what Applicant believes is the English language version: Tanenbaum, Andrew S., Operating Systems: Design and Implementation, Prentice-Hall, 1987, pp. 279, 347, 348.79Todd A. Gerety, Letter to Arthur S. Rose, Jun. 26, 2007 (including exhibits listed separately), 1 page.80United States Court of Appeals, Federal Circuit, Seachange International, Inc. Vs. C-Cor, Inc., Jun. 29, 2005, 22 pages.81United States Court of Appeals, Federal Circuit, Seachange International, Inc. Vs. nCUBE, Corp., Oct. 26, 2004, 28 pages.82United States District Court, Delaware, Seachange International, Inc. Vs. nCUBE, Corp., Apr. 7, 2004, 13 pages.83United States District Court, Delaware, Seachange International, Inc. Vs. nCUBE, Corp., Aug. 29, 2000, 12 pages.84Wedde H. F., et al.: "A universal framework for managing metadata in the distributed Dragon Slayer System", Proceedings of the Euromicro Conference. Euromicro. Informatics: Inventing the Future, Proceedings of Euromicro Workshop on Multimedia and Telecommunications, vol. 2, Sep. 5, 2000, pp. 96-101.85Wei-Min Shen and Behnam Salemi; Distributed and Dynamic Task Reallocation in Robot Organizations; IEEE 2002; pp. 1019-1024.86Yamashita, Hirofumi, et al., "Development of RAID Filesystem VAFS/HR," The Special Interest Group Notes of IPSJ, Japan, Information Processing Society of Japan, Sep. 16, 1994, vol. 94, No. 80, p. 9-16.87Yoshitake Shinkai, Cluster File System: HAMFS, Fujitsu, Japan, Fujitsu Limited, Jul. 9, 1999, vol. 50, No. 4, pp. 210 to 214 (stamped Citation 2 / English Translation attached) total 16 pages.RoteraOriginalbildGoogles startsida - Webbplatskarta - Massh�mtningar av USPTO - Sekretesspolicy - Anv�ndarvillkor - Om Google Patent - Skicka feedbackDessa data tillhandah�lls av IFI CLAIMS Patent Services©2012 Google