Vmware, Inc.

Microsoft Technology Licensing, LLC

Nicira, Inc.

Dahlia Malkhi

Ittai Abraham

Michael Wei

Guy Golan Gueta

Medhavi Dhawan

Maithem Munshed

Gopala Krishna R Kakivaya

Richard L Hasha

Lu Xun

Zeeshan Altaf Lokhandwala

Anny Martinez Manzanilla

Kartik Ravidas Nayak

Ling Ren

Alexander Spiegelman

Lidong Zhou

Roger Michoud

Michael Reiter

Soumya Basu

Saeed A Behnam

Alin Tomescu

Adrian Seredinschi

Zheng Zhang

Georgios Chrysanthakopoulos

Marcos Kawazoe Aguilera

Philip Alan Bernstein

Chandramohan Amyangot Thekkath

Mayank Agarwal

Nicholas Kushmerick

Leslie B Lamport

Colin Wilson Reid

Eric Schkufza

Asaf Kariv

Shiding Lin

Pieter Noordhuis

Ramakrishna Rao Kotla

Amy Tai

Mahesh Balakrishnan

Ramses V Morales

Po-Shen Loh

Eyal Lubetzky

Yuval Peres

Ragnar Edholm

Yaacov Fernandess

Maofan Yin

Udi Wieder

Yee Jiun Song

Nikos Vasilakis

Gopala Kirhsna R Kakivaya

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

A shared log system can provide a key-index structure (main map) that allows clients (users) to access the state of objects stored in the shared log system. The client can define secondary indices on the main map to provide access to the data that are tailored to the client's data needs. Each client can generate their own customized set of secondary indices different from other clients.

Just-in-time multi-indexed tables in a shared log

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

Methods and systems to sample event messages are described. As event messages are generated by one or more sources, the event messages are stored in a storage queue. An event message policy that represents conditions for storing event messages in a sample log file are input. For each event message output from the storage queue, the event message may be stored in a sample log file when one or more of the conditions of the event message policy are satisfied. The event messages of the sample log file may be displayed in a graphical user interface that enables a user to change the event message policy.

Methods and systems to sample event messages

A replicated service comprises N replicas deployed on compute nodes of a computer network, wherein the replicas are each configured to vote on a proposed transaction output by a leader of the replicas and certify the proposed transaction upon receiving qr*N first votes, where qr is a fractional value between 0 and 1 that represents a quorum required for certification. A method of approving a transaction in the replicated service includes receiving certifications from the replicas, and transmitting an approval of the transaction to the replicas for recording: (i) upon determining that at least qc*N certifications have been received, where qc is a fractional value between 0 and 1 that represents a quorum required for transaction approval and qc&#x3e;qr, or (ii) upon determining that at least qr*N certifications have been received at the end of the time period equal to 2*&#x394;, where &#x394; represents a network delay.

Byzantine fault tolerance that supports heterogeneous clients

A replicated service comprises N replicas deployed on compute nodes of a computer network, wherein the N replicas are each configured to vote on a proposed transaction output by a leader of the N replicas and certify the proposed transaction upon receiving qr*N first votes, where qr is a fractional value between 0 and 1 that represents a quorum required for certification. A method of approving a transaction in the replicated service includes receiving certifications from the N replicas, determining whether or not the certifications are received from at least qr*N replicas during a time period equal to 2*&#x394;, where &#x394; represents a network delay between two compute nodes of the computer network, and transmitting an approval of the transaction to the replicas for recording by the replicas upon determining that at least qr*N certifications have been received at the end of the time period equal to 2*&#x394;.

Flexible byzantine fault tolerant protocol using message delay upper bound for client commit decision

The disclosure describes a failure-free execution agreement that includes n=3F+1 parties acting as replicas, and a number of parties acting as clients. One replica is designated as a primary. At most F replicas are presumed Byzantine faulty. The basic agreement protocol proceeds in three rounds: (1) client sends a request to the primary, who sends to all replicas; (2) each replica sends a threshold-part signature on hash to a first collector; (3) the collector combines the threshold-parts into a single signature and sends to all 3F+1 replicas which then commit and send to a second collector. The client proceeds when a signed block of requests arrives from the second collector.

A log unit provides a shared log for recording updates on data objects. Garbage collection is performed locally and in-place by the log unit. In a marking portion of the garbage collection process, the log unit identifies and marks log entries that record supersedable updates. In a deallocation portion of the process, the log unit deallocates at least portions of the marked log entries that contain supersedable updates.

In-place garbage collection of a sharded, replicated distributed state machine based on supersedable operations

A method of managing a transaction in a control plane executing on a computing system that manages a plurality of services includes: receiving, at the control plane from a client, a plurality of first requests for at least one target service of the plurality of services, each of the plurality of first requests including a transaction indicator identifying the transaction; executing at least one handler of the at least one target service to process the plurality of first requests; receiving, at the control plane from the client, a commit request for the transaction coordinator service, the commit request including an instruction to commit the transaction; and executing a handler of the transaction coordinator service to process the commit request and notify the at least one target service of a status of the commit request.

Transactions in a decentralized control plane of a computing system

A log unit provides a shared log for recording updates on data objects. Garbage collection is performed locally and in-place by the log unit. In a marking portion of the garbage collection process, the log unit identifies and marks log entries that record mergeable updates. In a deallocation portion of the process, the log unit merges one or more mergeable log entries and deallocates at least portions of the merged log entries.

In-place garbage collection of a sharded, replicated distributed state machine based on mergeable operations

Growing community of inventors

Palo Alto, CA, United States of America

Dahlia Malkhi