公开(公告)号：US20060143517A1

公开(公告)日：2006-06-29

申请号：US11021983

申请日：2004-12-22

申请人： John Douceur ,  Jonathan Howell

发明人： John Douceur ,  Jonathan Howell

IPC分类号： G06F11/00

CPC分类号： G06F11/1484

摘要： A mechanism that enables a nondeterministic client-server application to be run as a replicated state machine without requiring the application to be modified. A replicated state machine substrate is utilized to coordinate the execution of multiple virtual machine monitors, each of which runs an identical copy of an operating system and server application. The virtual machine monitors each act as deterministic state machines, virtualizing state machine characteristics and behaviors.

摘要翻译： 一种使非确定性客户端 - 服务器应用程序作为复制状态机运行而不需要修改应用程序的机制。 复制状态机基板用于协调多个虚拟机监视器的执行，每个虚拟机监视器运行操作系统和服务器应用程序的相同副本。 虚拟机监视每个动作为确定性状态机，虚拟化状态机特性和行为。

公开(公告)号：US20060136369A1

公开(公告)日：2006-06-22

申请号：US11015227

申请日：2004-12-17

申请人： John Douceur ,  Jonathan Howell

发明人： John Douceur ,  Jonathan Howell

IPC分类号： G06F17/30

CPC分类号： G06F17/30194

摘要： Disclosed are “black-box leases” that protect information consistency and that allow for information sharing in a distributed file system while hiding from a client information about other clients' use of the file system. This information hiding also allows greater concurrency because changes to the file system are permitted as long as they do not affect the leases as observed by the clients. For each data field protected by a black-box lease, a client has a two-value data structure: SelfValue represents the client's intended use of the data field, and OtherValue is an aggregation of the other clients' intended uses of that data field. Knowing only this aggregate OtherValue, but without knowing any specifics of the other clients' usage patterns, the client knows how it may use the data field without adversely affecting the consistency of data in the distributed file system.

摘要翻译： 公开的是“黑箱租赁”，其保护信息一致性并且允许在分布式文件系统中的信息共享，同时隐藏客户端关于其他客户端使用文件系统的信息。 此信息隐藏还允许更大的并发性，因为只要不影响客户端遵守的租约，就允许对文件系统进行更改。 对于由黑盒租赁保护的每个数据字段，客户端具有两值数据结构：SelfValue表示客户端对数据字段的预期用途，而OtherValue是其他客户端该数据字段的预期用途的聚合。 只知道这个聚合的OtherValue，但是不知道其他客户端的使用模式的任何细节，客户端知道如何使用数据字段，而不会对分布式文件系统中的数据的一致性产生不利影响。

公开(公告)号：US08135987B2

公开(公告)日：2012-03-13

申请号：US12793547

申请日：2010-06-03

申请人： John Douceur ,  Jonathan Howell ,  Jacob R. Lorch

发明人： John Douceur ,  Jonathan Howell ,  Jacob R. Lorch

IPC分类号： G06F11/00

CPC分类号： G06F11/187 ,  G06F11/1482 ,  G06F2201/82

摘要： A replicated state machine with N replica servers may be configured to tolerate a count of F faults. A first operation (of a first ordering type) executes when a first quorum of correctly functioning replicas is available. A second operation (also of the first operation type) executes when a second quorum of correctly functioning replicas is available. A third operation (of a second ordering type) executes when a third quorum of correctly functioning replicas are available. The operations are executed by the replicated state machine such that: (1) the replicated state machine does not guarantee operational ordering between the first operation and the second operation; (2) the replicated state machine guarantees ordering between the first operation and the third operation; and (3) the replicated state machine guarantees ordering between the second operation and the third operation.

摘要翻译： 具有N个副本服务器的复制状态机可以被配置为容忍F个故障的计数。 当正常运行的副本的第一个法定数量可用时，执行第一个操作（第一个排序类型）。 当正常运行的副本的第二个法定值可用时，执行第二个操作（也是第一个操作类型）。 当正常运行的副本的第三个法定值可用时，执行第三次操作（第二次排序类型）。 这些操作由复制状态机执行，使得：（1）复制状态机不保证第一操作和第二操作之间的操作顺序; （2）复制状态机保证第一操作和第三操作之间的顺序; 和（3）复制状态机保证第二操作和第三操作之间的顺序。

公开(公告)号：US20070168364A1

公开(公告)日：2007-07-19

申请号：US11275550

申请日：2006-01-13

申请人： John Douceur ,  Jonathan Howell

发明人： John Douceur ,  Jonathan Howell

IPC分类号： G06F7/00

CPC分类号： G06F17/3012 ,  Y10S707/99945

摘要： Non-mutating tree-structured file identifiers are used to identify files stored in a file system. Each of multiple files in the file system has a corresponding non-mutating file identifier, and these file identifiers are assigned and maintained using a tree structure.

摘要翻译： 非突变树结构文件标识符用于识别存储在文件系统中的文件。 文件系统中的多个文件中的每一个具有相应的非突变文件标识符，并且使用树结构来分配和维护这些文件标识符。

公开(公告)号：US20070073693A1

公开(公告)日：2007-03-29

申请号：US11229053

申请日：2005-09-16

申请人： Tim Harris ,  Simon Peyton-Jones ,  Jonathan Howell ,  John Douceur

发明人： Tim Harris ,  Simon Peyton-Jones ,  Jonathan Howell ,  John Douceur

IPC分类号： G06F17/30

CPC分类号： G06F9/524 ,  G06F9/466

摘要： The described implementations relate to efficient scheduling of transactions and tasks. A memory location, address, or variable previously accessed by a blocked entity is observed periodically to determine an appropriate time to wake and retry the blocked entity. If the previous accessed memory location, address or variable changes state, a scheduler wakes the blocked entity and the blocked entity retries processing. A doubly-indexed data structure of blocked entities and memory locations associated with the blocked entities may be used to efficiently determine when a retrying execution would be profitable.

摘要翻译： 所描述的实现涉及事务和任务的有效调度。 周期性地观察先前被阻塞实体访问的存储器位置，地址或变量，以确定唤醒并重试被阻塞实体的适当时间。 如果先前访问的存储器位置，地址或变量改变状态，则调度器唤醒被阻止的实体，并且被阻止的实体重试处理。 被阻止的实体和与被阻止的实体相关联的存储器位置的双重索引的数据结构可以用于有效地确定重试执行何时是有利可图的。

公开(公告)号：US20060259818A1

公开(公告)日：2006-11-16

申请号：US11489819

申请日：2006-07-20

申请人： Jonathan Howell ,  Eric Traut ,  Jacob Lorch ,  John Douceur

发明人： Jonathan Howell ,  Eric Traut ,  Jacob Lorch ,  John Douceur

IPC分类号： G06F11/00

CPC分类号： G06F9/45558 ,  G06F11/1484 ,  G06F2009/45566 ,  G06F2201/815

摘要： A virtual machine monitor (VMM) is configured to enforce deterministic execution of virtual machines in a multiprocessor machine. The VMM is configured to ensure that any communication by physical processors via shared memory is deterministic. When such VMMs are implemented in a distributed environment of multiprocessor machines coupled via a logical communication link, non-deterministic server applications running on virtual machines using the VMM may be replicated.

摘要翻译： 虚拟机监视器（VMM）被配置为强制执行多处理器机器中的虚拟机的确定性执行。 VMM配置为确保物理处理器通过共享内存的任何通信是确定性的。 当这种VMM在通过逻辑通信链路耦合的多处理器机器的分布式环境中实现时，可以复制在使用VMM的虚拟机上运行的非确定性服务器应用程序。

公开(公告)号：US20060184627A1

公开(公告)日：2006-08-17

申请号：US11057591

申请日：2005-02-14

申请人： Jonathan Howell ,  Jacob Lorch ,  John Douceur ,  Leslie Lamport

发明人： Jonathan Howell ,  Jacob Lorch ,  John Douceur ,  Leslie Lamport

IPC分类号： G06F15/16

CPC分类号： G06F11/187 ,  G06F11/1683 ,  G06F2201/82

摘要： Synchronized devices comprising a distributed system attempt to agree on a compatible sequence of commands to execute. Each device in the distributed system may act as a proposer, acceptor, or a learner. Each proposer proposes a command for each device to execute. The acceptors either accept or reject the proposed commands. The learners keep track of the proposed commands and determine, using a transactional substrate, whether the acceptors have a accepted sequences of commands that commute with respect to one another. Once the learners have determined that a quorum of acceptors have accepted sequences of commands that commute with respect to one another the accepted commands are executed by each device in the distributed system.

摘要翻译： 包括分布式系统的同步设备尝试对要执行的命令的兼容序列达成一致。 分布式系统中的每个设备可以充当提议者，接受者或学习者。 每个提议者为每个设备提出一个命令来执行。 接受者接受或拒绝提出的命令。 学习者跟踪所提出的命令，并使用事务底层来确定接受者是否具有相互相互通信的接受的命令序列。 一旦学习者确定接受者的数量已经接受了相互之间通勤的命令序列，则接受的命令由分布式系统中的每个设备执行。

公开(公告)号：US20050089131A1

公开(公告)日：2005-04-28

申请号：US10694596

申请日：2003-10-23

申请人： Jonathan Howell ,  John Douceur

发明人： Jonathan Howell ,  John Douceur

IPC分类号： G06F1/12 ,  G06F1/14 ,  G06F21/00 ,  G06M3/00 ,  H04L29/06

CPC分类号： H04L63/126 ,  G06F1/12 ,  G06F1/14 ,  G06F21/725

摘要： The clocks of remote computing devices are synchronized within a range of certainty through the determination of an upper bound and a lower bound around a reference time. A message from a computing device is propagated up a network tree of devices to a device having a reference time, which encodes the reference time and returns the message down the tree. Each receiving device can determine that the reference time could not have occurred before their transmission of the message, nor could it have occurred after their receipt of the return message. Cryptographic hashes can be used to guard against malicious computing devices. Alternate paths and scheduling of messages can be used to provide a narrower spread between the upper and lower bounds, and clock drift can be accounted for by increasing the spread over time.

摘要翻译： 通过确定参考时间周围的上限和下限，远程计算设备的时钟在确定的范围内同步。 来自计算设备的消息被传播到设备的网络树到具有参考时间的设备，该参考时间对参考时间进行编码并将消息返回到树下。 每个接收设备可以确定参考时间在其发送消息之前不能发生，也不能在接收到返回消息之后发生。 密码散列可用于防范恶意计算设备。 消息的替代路径和调度可用于在上限和下限之间提供较窄的扩展，并且可以通过增加随时间推移来计算时钟漂移。

公开(公告)号：US20070168393A1

公开(公告)日：2007-07-19

申请号：US11275434

申请日：2005-12-30

申请人： Jonathan Howell ,  John Douceur

发明人： Jonathan Howell ,  John Douceur

IPC分类号： G06F17/30

CPC分类号： G06F17/30371 ,  Y10S707/99938

摘要： A delta pager maintains a database with atomic, isolated transactions. When a transaction seeks to make changes to the database, the delta pager stores the changes in write buffers, and applies the changes when intervening transactions do not literally or substantively change the state of the database relied upon by the transaction. The delta pager applies the changes to commit the transaction by conjoining the write buffers with the current state of the database to form a new data structure representing the state of the database. The delta pager coalesces write buffers to maintain efficiency, subject to snapshots the delta pager respects to preserve selected states of the database. The delta pager makes selected sections of the database durable by moving selected data to a durable store. The delta pager also provides cache objects between the durable store and current transactions to promote efficient access to data.

摘要翻译： 三角形寻呼机维护具有原子，隔离事务的数据库。 当事务寻求对数据库进行更改时，增量寻呼机将更改存储在写入缓冲区中，并且当中间事务不会字面上或实质上更改事务依赖的数据库的状态时应用更改。 三角寻呼机通过将写缓冲区与数据库的当前状态相结合来应用更改来提交事务，以形成表示数据库状态的新数据结构。 delta寻呼机合并写入缓冲区以保持效率，根据快照，差异传感器将保留数据库的所选状态。 三角形寻呼机通过将选定的数据移动到耐用商店来使数据库的选定部分保持持久。 三角形寻呼机还在耐用存储和当前事务之间提供缓存对象，以促进对数据的高效访问。

公开(公告)号：US20070156588A1

公开(公告)日：2007-07-05

申请号：US11275435

申请日：2005-12-30

申请人： Jonathan Howell ,  John Douceur

发明人： Jonathan Howell ,  John Douceur

IPC分类号： G06Q99/00 ,  H04L9/00 ,  G06F12/14 ,  H04L9/32 ,  G06F11/30 ,  H04K1/00

CPC分类号： G06F9/526 ,  G06F12/0844 ,  G06F2209/522 ,  G06F2209/523 ,  G06Q20/3674

摘要： Scalable leases reduce latency and reduce the burden on a server in managing data leases. Instead of processing individual lease requests for clients seeking access to the same data, scalable leases provide for blanket leases that all of the clients can use to access the selected data. Leases may be encrypted or selectively distributed to restrict access to the data. Moreover, distributed data structures may be used to cache leases at identifiable nodes in a network to offload work from the server without all clients in the network having to cache all blanket leases issued. Thresholds for issuing blanket leases may be determined or adjusted by considerations such as demand for the selected data and server workload. Similarly, leases may be renewed on the basis of demand for selected data, conflicting lease requests, and other factors. Scalable leases may be issued for read leases and controlled write leases.

摘要翻译： 可扩展租赁减少延迟并减少服务器管理数据租赁的负担。 寻求访问相同数据的客户不需要处理单独的租赁请求，而是可扩展租赁提供所有客户端可以使用来访问所选数据的全面租赁。 租赁可以被加密或选择性地分配，以限制对数据的访问。 此外，分布式数据结构可以用于在网络中的可识别节点处高速缓存租约，以从服务器卸载工作，而网络中的所有客户端都不得不缓存所有发布的全部租约。 可以通过诸如对所选择的数据和服务器工作负载的需求等考虑来确定或调整用于签发覆盖租赁的阈值。 同样，租赁可以根据对所选数据的需求，相互冲突的租赁请求等因素进行更新。 可租赁租赁可以用于租赁和受控的书面租赁。