公开(公告)号：US08046413B2

公开(公告)日：2011-10-25

申请号：US11057591

申请日：2005-02-14

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

发明人： Jonathan R. Howell ,  Jacob R. Lorch ,  John R. Douceur ,  Leslie B. 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.

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

公开(公告)号：US07555516B2

公开(公告)日：2009-06-30

申请号：US10996350

申请日：2004-11-23

申请人： Leslie B. Lamport

发明人： Leslie B. Lamport

IPC分类号： G06F15/16 ,  G06F15/173

CPC分类号： G06F11/1494 ,  G06F11/182 ,  G06F11/187 ,  H04L67/1095

摘要： A distributed computing system can achieve consensus while introducing fewer message delays by using an algorithm that allows the constituent devices to vote on functions received directly from one or more clients. If a conflict occurs, a leader device from among the devices can be selected such that the leader device already knows of the other devices' previous votes, and can determine an appropriate function to propose, using an immediately subsequent proposal number, without performing the first phase of the Paxos algorithm. Alternatively, each device can independently determine, by using the same repeatable mechanism used by a leader device, what function the leader device would propose, and can then vote for that function using the immediately subsequent proposal number. If the devices' votes again result in a conflict, the Paxos algorithm can be used, or additional iterations can be performed prior to resorting to the Paxos algorithm.

摘要翻译： 分布式计算系统可以通过使用允许组成设备对从一个或多个客户端直接接收的功能进行投票的算法来实现共同点，同时引入更少的消息延迟。 如果发生冲突，则可以选择来自设备中的引导设备，使得领导者设备已经知道其他设备的先前投票，并且可以使用即时后续的提案号码来确定适当的功能来提出，而不执行第一 Paxos算法的相位。 或者，每个设备可以通过使用领导者设备使用的相同的可重复机制来独立地确定领导者设备将提出什么功能，并且然后可以使用紧随其后的提案号码对该功能进行投票。 如果设备的投票再次导致冲突，则可以使用Paxos算法，或者在使用Paxos算法之前可以执行其他迭代。

公开(公告)号：US07711825B2

公开(公告)日：2010-05-04

申请号：US10750600

申请日：2003-12-30

申请人： Leslie B. Lamport

发明人： Leslie B. Lamport

IPC分类号： G06F15/16

CPC分类号： G06F11/182 ,  G06F11/1658

摘要： A simplified fault tolerant algorithm is presented for operating a distributed computing system in a fault tolerant manner. A system comprising three computing devices need only have two devices agree to perform any proposed function. Thus, when soliciting a vote for a proposed function, a leader device can also send its vote for the proposed function. This allows any recipient device to complete the quorum with its own vote. Consequently, any recipient device can, without any further messages, determine whether to execute the proposed function. Furthermore, if the device executes the proposed function, it can transmit the results directly to the client that requested the function, saving a message delay. If the quorum of devices used to select and execute proposed functions is itself selected by a quorum, then one of the devices of the system can be an inexpensive device having limited computational ability or storage capacity.

摘要翻译： 提出了一种简化的容错算法，用于以容错方式操作分布式计算系统。 包括三个计算设备的系统仅需要两个设备同意执行任何提出的功能。 因此，当为提出的功能征求投票权时，领导者也可以发送投票给所提议的功能。 这允许任何收件人设备通过自己的投票完成法定人数。 因此，任何接收者设备可以在没有任何进一步消息的情况下确定是否执行所提出的功能。 此外，如果设备执行提出的功能，它可以将结果直接发送到请求功能的客户端，从而节省消息延迟。 如果用于选择和执行提出的功能的设备的法定人数本身是由法定人数选定的，则系统的一个设备可以是具有有限计算能力或存储容量的廉价设备。

公开(公告)号：US07698465B2

公开(公告)日：2010-04-13

申请号：US10996351

申请日：2004-11-23

申请人： Leslie B. Lamport

发明人： Leslie B. Lamport

IPC分类号： G06F15/16

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

摘要： A distributed computing system can achieve a generalized consensus, enabling commands that commute to be selected in any order. A leader can learn of previously selected sequences of commands, and can propose a compatible sequence of commands. Devices can select a sequence of commands that is compatible with previously selected sequences. Additional commands can be selected by selecting a sequence of commands comprising a previously selected sequence and the additional commands. Further efficiencies can be realized if the devices receive proposals directly from clients. Two or more proposals arriving in varying orders at the various clients may be selected in varying orders. However, if those proposals commute, a generalized consensus nevertheless exists despite the variations, enabling the system to continue efficient operation. To conserve memory, a checkpoint command that does not commute with any other command can be used to secure a sequence of commands for archiving or deletion.

摘要翻译： 分布式计算系统可以实现一般化的共识，使命令能够以任何顺序进行选择。 领导者可以了解以前选择的命令序列，并且可以提出一个兼容的命令序列。 设备可以选择与以前选择的序列兼容的命令序列。 可以通过选择包括先前选择的序列和附加命令的命令序列来选择附加命令。 如果设备直接从客户端接收建议，则可以实现更高的效率。 可以以不同的顺序选择在不同客户端以不同顺序到达的两个或多个提议。 但是，如果这些提案通勤，尽管存在差异，仍然存在广泛的共识，使系统能够继续有效运行。 为了节省内存，可以使用不与任何其他命令通勤的检查点命令来保护用于归档或删除的一系列命令。

公开(公告)号：US5138615A

公开(公告)日：1992-08-11

申请号：US370284

申请日：1989-06-22

申请人： Leslie B. Lamport ,  Thomas L. Rodeheffer ,  K. Mani Chandy

发明人： Leslie B. Lamport ,  Thomas L. Rodeheffer ,  K. Mani Chandy

IPC分类号： H04L12/56

CPC分类号： H04L45/28 ,  H04L45/02 ,  H04L45/16 ,  H04L45/40 ,  H04L45/48

摘要： A mesh connected local area network provides automatic packet switching and routing between host computers coupled to the network. The network has a multiplicity of cut-through, nonblocking switches, each capable of simultaneously routing a multiplicity of data packets. Low host-to-host latency is achieved through the use of cut-through switches with separate internal buffers for each packet being routed. The switches are interconnected with one another and are coupled to the host computers of the network by point to point full duplex links. While each switch can be coupled to ten or more network members, i.e., switches and hosts, each link is coupled to only two network members and is dedicated to carrying signals therebetween. Whenever a new switch or link is added to the network, and whenever a switch or link fails, the switches in the network automatically reconfigure the network by recomputing the set of legal paths through the network.

公开(公告)号：US20100017495A1

公开(公告)日：2010-01-21

申请号：US12571272

申请日：2009-09-30

申请人： Leslie B. Lamport

发明人： Leslie B. Lamport

IPC分类号： G06F15/16

CPC分类号： H04L63/123 ,  H04L63/1441

摘要： A distributed computing system can operate in the face of malicious failures on the part of some of its constituent devices, and provide a minimum of message delays between receiving a client request and providing a response, when each device within the system verifies the sender of any message it receives, and the propriety of the message.

摘要翻译： 分布式计算系统可以面对其一些组成设备的恶意故障，并且在接收客户端请求和提供响应之间提供最小的消息延迟，当系统内的每个设备验证任何 收到的消息，以及消息的适当性。

公开(公告)号：US07565433B1

公开(公告)日：2009-07-21

申请号：US10184773

申请日：2002-06-28

申请人： Leslie B. Lamport

发明人： Leslie B. Lamport

IPC分类号： G06F15/16

CPC分类号： G06Q10/107

摘要： A distributed computing system can operate in the face of malicious failures on the part of some of its constituent devices when each device within the system verifies the sender of any message it receives, and the propriety of the message. The sender can be verified through message authentication schemes or digital signature schemes, though message authentication can provide a more computationally efficient solution. The propriety of a message can be verified by receiving a sufficiently large number of equivalent, properly authenticated messages such that, even if every malicious device transmitted a message, at least one message would have been sent by a properly functioning device. If the number of malicious devices is represented by the variable “M”, a sufficient number of equivalent, properly authenticated messages to verify that the message is true can be any number of messages greater than M. Furthermore, the receipt of more than 2M equivalent properly authenticated messages can allow the receiving device to prove the propriety of the message to any device it forwards the messages onto. The proper operation of the distributed computing system can, therefore, proceed in the face of M number of malicious failures and F number of total failures, which can include malicious and non-malicious failures, if the number of constituent devices in the distributed computing system is greater than 2F+M.

摘要翻译： 当系统中的每个设备验证其接收到的任何消息的发送者以及消息的适当性时，分布式计算系统可以面对其一些组成设备的恶意故障。 可以通过消息认证方案或数字签名方案来验证发送方，尽管消息认证可以提供更有计算效率的解决方案。 消息的适当性可以通过接收足够大量的等效的，正确认证的消息来验证，使得即使每个恶意设备发送消息，至少一个消息将被正常运行的设备发送。 如果恶意设备的数量由变量“M”表示，则足够数量的等效的，正确认证的消息来验证消息是否为真，可以是大于M的任何数量的消息。此外，接收到超过2M的等效 正确认证的消息可以允许接收设备证明消息的适当性，将消息转发到任何设备。 因此，如果分布式计算系统中的组成设备的数量，分布式计算系统的适当操作可以面对M个恶意故障和F个总故障数，其中可能包括恶意和非恶意故障 大于2F + M。

公开(公告)号：US5261085A

公开(公告)日：1993-11-09

申请号：US913759

申请日：1992-07-13

申请人： Leslie B. Lamport

发明人： Leslie B. Lamport

IPC分类号： G06F11/00 ,  G06F11/18 ,  G06F11/20

CPC分类号： G06F11/182 ,  G06F11/1425 ,  G06F11/1658 ,  G06F11/187

摘要： System and method for implementing a distributed state machine in which consistency is maintained despite the failure of any number of processes and communication paths. This machine and method are suitable for systems with modest reliability requirements that do not justify the expense of an extremely fault tolerant, real-time implementation. One process in a network of server processes is chosen as the leader, and that leader is responsible for broadcasting state machine commands to the other processes. The commands are numbered consecutively, and they are recorded in stable storage by the processes. Each command is broadcast through a uniquely numbered ballot or referendum, and each process participating in a ballot may either vote to accept the command or not vote. To be issued, a command must be voted for by a majority of the processes in the system. Each issued command is stored by each of the processes in the majority set which voted for it, and since any two majority sets must have at least one process in common, any command which has been issued will appear in the store of at least one process of any majority set participating in a subsequent ballot. When a new leader is chosen, messages are exchanged between the new leader and the other processes in the system to ensure that each of the processes has all of the commands that the other processes have. As part of this procedure, any command for which one of the processes has previously voted but does not have a command number is broadcast as a proposed command in a new ballot.

摘要翻译： 用于实现分布式状态机的系统和方法，其中尽管任何数量的进程和通信路径都失败，但仍保持一致性。 该机器和方法适用于具有适度可靠性要求的系统，这不能证明极端容错，实时实施的费用。 选择服务器进程网络中的一个进程作为领导者，该领导负责将状态机命令广播到其他进程。 这些命令是连续编号的，它们通过进程记录在稳定的存储器中。 每个命令通过独一无二的投票或公民投票进行广播，参与投票的每个进程可以投票接受命令，也可以不投票。 要发布，系统中的大多数进程必须对命令进行投票。 每个发出的命令由投票给它的多数集合中的每个进程存储，并且由于任何两个多数组必须具有至少一个共同的进程，所以已经发出的任何命令将出现在至少一个进程的存储中 多数参加随后的投票。 当选择新的领导者时，消息在新的领导者和系统中的其他进程之间交换，以确保每个进程都具有其他进程具有的所有命令。 作为此过程的一部分，任何一个进程以前投票但没有命令编号的命令都作为新投票中的提议命令进行广播。

公开(公告)号：US08073897B2

公开(公告)日：2011-12-06

申请号：US12571272

申请日：2009-09-30

申请人： Leslie B. Lamport

发明人： Leslie B. Lamport

IPC分类号： G06F15/16

CPC分类号： H04L63/123 ,  H04L63/1441

摘要： A distributed computing system can operate in the face of malicious failures on the part of some of its constituent devices, and provide a minimum of message delays between receiving a client request and providing a response, when each device within the system verifies the sender of any message it receives, and the propriety of the message.

摘要翻译： 分布式计算系统可以面对其一些组成设备的恶意故障，并且在接收客户端请求和提供响应之间提供最小的消息延迟，当系统内的每个设备验证任何 收到的消息，以及消息的适当性。

公开(公告)号：US08005888B2

公开(公告)日：2011-08-23

申请号：US10750601

申请日：2003-12-30

申请人： Leslie B. Lamport

发明人： Leslie B. Lamport

IPC分类号： G06F15/16

CPC分类号： G06F9/542 ,  G06F2209/544 ,  H04L29/06 ,  H04L67/10 ,  H04L69/329

摘要： A conflict tolerant message delay reducing consensus algorithm is presented for operating a distributed computing system. The devices of the distributed computing system can directly receive client requests, and can execute the requests and respond directly to the clients, saving message delays. If there is a conflict, the ultimately selected request can be the request submitted by the client with the highest client identifier. A device can change its vote, and execute a different request, if it is made by a client having a more dominant client identifier. All but one of the clients can also be a device implementing the system. A device that has executed a requested function may no longer submit a request in the same step. Consequently, a request is executed by the system when all devices have executed the request. If one or more devices fails, any fault tolerant consensus algorithm can be used.

摘要翻译： 提出了一种用于操作分布式计算系统的冲突容忍消息延迟减少共识算法。 分布式计算系统的设备可以直接接收客户端请求，可以执行请求，直接响应客户端，保存消息延迟。 如果存在冲突，则最终选择的请求可以是具有最高客户端标识符的客户端提交的请求。 如果客户端具有较为主导的客户端标识符，设备可以更改其投票，并执行不同的请求。 除了一个客户端之外，所有客户端也可以是实现系统的设备。 执行请求的功能的设备可能不再在同一步骤中提交请求。 因此，当所有设备执行请求时，系统执行请求。 如果一个或多个设备出现故障，则可以使用任何容错共识算法。