Vmware, Inc.

Ittai Abraham

Dahlia Malkhi

Guy Golan Gueta

Alexander Spiegelman

Abhishek Gupta

Richard Paul Spillane

Jorge Guerra Delgado

Srinath Premachandran

Sandeep Rangaswamy

Kapil Chowksey

Avishay Yanai

Robert T Johnson

Kartik Ravidas Nayak

Ling Ren

Michael Reiter

Asaf Kariv

Soumya Basu

Yotam Harchol

Alin Tomescu

Adrian Seredinschi

Heidi Howard

Neil Giridharan

Ioan Alin Tomescu Nicolescu

Toly Kournik

Igor Golikov

Andrew Joseph Stone

Vijaychidambaram Velayudhan Pillai

Bryan Fink

Tsvetomir Dimirov Dimitrov

Maofan Yin

Nikolay Kolev Georgiev

Yehonatan Buchnik

Nikhil Kumar

Hristo Staykov

Petar Nedkov Ivanov

Embodiments of the present invention provide systems, methods, and software to manage actions across a cluster of replica computing nodes for a data structure. In one implementation, a first replica in the cluster generates a first action notification and receives one or more additional action notifications from at least one other replica in the cluster. The first replica further determines that consensus exists for the first action notification based on the one or more additional action notifications and, in response to determining that consensus exists, identifies one or more rules associated with the first action notification and initiates one or more actions corresponding to the one or more rules.

Scheduling actions in multiple replicas of computing environment using consensus protocol

The present disclosure is directed to a leader-based partially synchronous BFT SMR protocol that improves upon existing protocols by exhibiting two rounds of communication latency, linear authenticator complexity, and optimistic responsiveness. This is achieved through the novel use of an aggregate signature scheme as part of the protocol's view-change procedure.

Two-round byzantine fault tolerant (BFT) state machine replication (SMR) protocol with linear authenticator complexity and optimistic responsiveness

The present disclosure is directed to a novel reconfiguration framework for a BFT SMR system. With this framework, the configuration of both the system itself and the clients of the system can be modified in a live manner (i.e., without taking the system offline) while preserving correct system operation.

Reconfiguration framework for byzantine fault tolerant (BFT) state machine replication (SMR) systems

A method and system for performing a flexible Byzantine fault tolerant (BFT) protocol. The method includes sending, from a client device, a proposed value to a plurality of replica devices and receiving, from at least one of the plurality of replica devices, a safe vote on the proposed value. The replica device sends the safe vote, based on a first quorum being reached, to the client device and each of the other replica devices of the plurality of replica devices. The method further includes determining that a number of received safe votes for the proposed value meets or exceeds a second quorum threshold, selecting the proposed value based on the determination, and setting a period of time within which to receive additional votes. The method further includes, based on the period of time elapsing without receiving the additional votes, committing the selected value for the single view.

Flexible byzantine fault tolerance

In one set of embodiments, each server executing a secure multi-party computation (MPC) protocol can receive shares of inputs to the MPC protocol from a plurality of clients, where each input is private to each client and where each share is generated from its corresponding input using a threshold secret sharing scheme. Each server can then verify whether the shares of the plurality of inputs are valid/invalid and, for each invalid share, determine whether a client that submitted the invalid share or a server that holds the invalid share is corrupted. If the client that submitted the invalid share is corrupted, each server can ignore the input of that corrupted client during a computation phase of the MPC protocol. Alternatively, if the server that holds the invalid share is corrupted, each server can prevent that corrupted server from participating in the computation phase.

Robust input verification for secure multi-party computation (MPC) with clients

In some embodiments, a method sends first messages that request first information for a set of blocks of the blockchain to the N replicas. Each replica maintains a respective instance of the blockchain. Second messages is received from at least a portion of the N replicas. The second messages include the first information for the set of blocks from each respective instance of the blockchain that is maintained by the N replicas. The method analyzes the first information to determine whether a consensus on the first information is reached by a number of replicas. When consensus is reached, a request is sent to a replica for one or more blocks to back up to a backup blockchain and second information is received for the one or more blocks from the replica. The method uses the second information to back up the one or more blocks in the backup blockchain.

Byzantine fault tolerance protocol for backing up blockchains

In some embodiments, a method receives a share of a signature of a decision block from at least a portion of the plurality of replicas. The share of the signature being generated when a respective replica signs the decision block and the decision block includes a set of requests from a client for a service. A combined signature is created based on the share of the signature block from at least the portion of the plurality of replicas. The method broadcasts a message that includes the combined signature to the plurality of replicas. The plurality of replicas use the combined signature to determine whether to process the decision block for the service.

Byzantine agreement using communications having linear complexity

An asynchronous state machine replication solution in a system of replicas includes executing multiple instances of a consensus protocol, referred to as leader-based views (LBVs) in each replica, where each replica is a leader participant in one of the LBV instances. Each replica drives a decision based on the consensus being reached among the LBV instances, rather than relying the expiration of timers and view changes to drive progress.

Asynchronous liveness boosting of state machine replication

Techniques for implementing linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas are provided. According to one set of embodiments, at a time of performing a view-change from a current view number v to a new view number v+1, a replica in the n replicas corresponding to a new proposer for new view number v+1 can generate a PREPARE message comprising a single COMMIT certificate, where the single COMMIT certificate is the highest COMMIT certificate the new proposer is aware of. The new proposer can then transmit the PREPARE message with the single COMMIT certificate to all other replicas in the n replicas.

Linear view-change BFT

In some embodiments, a method implements a Byzantine fault tolerant protocol. A first replica detects a condition to cause a view change procedure to move from a current view to a next view. The first replica sends a message indicating the first replica wants to leave the current view. Also, the first replica receives a set of messages from second replicas indicating a respective second replica wants to leave the current view. The first replica determines when a property is received to the leave the current view based on the set of messages from the set of second replicas. When it is determined the property is received, the first replica performs a process to leave the current view. When it is determined the property is not received, the first replica stays in the current view and participating in processing a request from a client in the current view.

Byzantine fault tolerant view change processing

A blockchain network include nodes that are configured as time sources. These time-source nodes broadcast respective updates of their local times to all nodes in the blockchain network. Each node computes a summary time value based on the received local time values so that each node uses the same summary time to maintain their respective copies of the blockchain.

Providing real-world time in a replicated state-machine environment

Techniques for implementing Byzantine fault tolerance with verifiable secret sharing at constant overhead are provided. In one set of embodiments, a client can determine a secret value s to be shared with N replicas in a distributed system, s being input data for a service operation provided by the N replicas. The client can further encode s into an f-degree polynomial P(x) where f corresponds to a maximum number of faulty replicas in the distributed system, evaluate P(x) at i for i=1 to N resulting in N evaluations P(i), generate at least one f-degree recovery polynomial R(x) based on a distributed pseudo-random function (DPRF) f(x), and evaluate R(x) at i for i=1 to N resulting in at least N evaluations R(i). The client can then invoke the service operation, the invoking comprising transmitting a message including P(i) and R(i) to each respective replica i.

Byzantine fault tolerance with verifiable secret sharing at constant overhead

Growing community of inventors

Tel Aviv, Israel

Ittai Abraham