US 9,753,792 B2 · Method and system for byzantine fault tolerant data replication

Abstract

A method for byzantine fault tolerant data replication with a plurality of 2f+1 data servers and one or more clients includes storing data in at least f+1 different data servers out of the 2f+1 data servers, and storing metadata of the stored data under a metadata-identifier in a metadata-service (MDS). The stored metadata includes a unique identifier of the stored data, a fingerprint of the stored data, and a list of the at least f+1 different data servers which have stored the data.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims13

Dependent claims

A method for byzantine fault tolerant data replication with a plurality of 2f+1 data servers and one or more clients, the method comprising:

storing data in at least f+1 different data servers of the 2f+1 data servers;
storing metadata of the stored data under a metadata-identifier in a metadata-service (MDS), wherein the stored metadata includes a unique identifier of the stored data, a fingerprint of the stored data, and a list of the at least f+1 different data servers which have stored the data;
and
reading the stored data by, a first one of the one or more clients by:
(a) querying a first data server of the list of the at least f+1 different data servers with the unique identifier of the data based on the stored metadata provided by the MDSupon being queried with the metadata-identifier,
(b) providing the stored data according to the unique identifier;
and
(c) providing the stored data to the first client based on a match of the fingerprints of the stored data and of the stored metadata.

5 more elements

Dependencies are inferred from the claim text.

Description3,929 words

Summary576 words

#This application is a U.S. National Stage Application under 35 U.S.C. §371 of International Application No. PCT/EP2014/055436 filed on Mar. 18, 2014, and claims benefit to European Patent Application No. 13160155.1 filed on Mar. 20, 2013. The International Application was published in English on Sep. 25, 2014 as WO 2014/147085 A2 under PCT Article 21(2).

#The present invention relates to a method for a byzantine fault tolerant data replication with a plurality of 2f+1 data servers and one or more clients.

#Data replication provides in general availability and data durability in the presence of failures. For example a replicated data store features strong consistency if it displays a behavior of a non-replicated data store in which operations are executed sequentially. However, performance and scalability are major problems.

Brief description of the drawings3 figures

#The present invention will be described in even greater detail below based on the exemplary figures. The invention is not limited to the exemplary embodiments. All features described and/or illustrated herein can be used alone or combined in different combinations in embodiments of the invention. The features and advantages of various embodiments of the present invention will become apparent by reading the following detailed description with reference to the attached drawings which illustrate the following:

#FIG. 1 shows schematically steps of a method according to a first embodiment of the present invention;

#FIG. 2 shows schematically steps of a method according to a second embodiment of the present invention; and

Detailed description3,226 words

#Since tolerating Byzantine faults requires f servers more than needed to tolerate only crash failures, one of the problems of byzantine quorum-based data replication are the additional costs compared to crash tolerant systems. For example as shown in the non-patent literature of Rui Fan, Nancy A. Lynch: Efficient Replication of Large Data Objects. DISC 2003: 75-91, 2f+1 servers are used to tolerate f crashes, yet no byzantine faults can be tolerated.

#In an embodiment, the present invention provides a method and a system for a byzantine fault tolerant data replication which have improved efficiency, in particular in terms of storage server acquisition costs and maintenance costs as well as in terms of storage space.

#In an embodiment, the present invention provides a method for byzantine fault-tolerant data replication with less than 3f+1 data servers.

Facts

Application

14/778,084Filed 18 Mar 2014

Priority

EP 1316015520 Mar 2013

Published

US 2016/0283123 A129 Sep 2016

Granted

5 Sep 2017

Term ends

18 Mar 2034

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification8 codes

G06F 11/0709
The processing taking place on a specific hardware platform or in a specific software environment: in a distributed system consisting of a…
G06F 3/0619
Improving the reliability of storage systems: in relation to data integrity, e.g. data losses, bit errors
G06F 3/065
Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems: replication mechanisms
G06F 3/067
Adopting a particular infrastructure: distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Timeline

20 Mar 2013Priority claimedEP 13160155
18 Mar 2014Application filedUS 14/778,084
29 Sep 2016PublishedUS 2016/0283123 A1
8 Mar 2017Assigned to NEC Europe Ltd.assignment of assignor's interest
5 Sep 2017GrantedUS 9,753,792 B2
5 Oct 2020Assigned to NEC Laboratories Europe GmbHassignment of assignor's interest
12 Oct 2026TodayWithin its term
18 Mar 2034Term endsEstimated

Method and system for byzantine fault tolerant data replication

Life of this patent

Method and system for byzantine fault tolerant data replication

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims13

Description3,929 words

Drawings

Classification8 codes

Life of this patent

Description3,929 words