Ordering device, data processing device, ordering method, computer program product, and multiplex system

Patent metadata

Field	Value
Publication number	US-10162719-B2
Application number	US-201615266073-A
Country	US
Kind code	B2
Filing date	Sep 15, 2016
Priority date	Aug 5, 2014
Publication date	Dec 25, 2018
Grant date	Dec 25, 2018

Abstract

According to an embodiment, an ordering device determines a processing order of pieces of data in each computer in a multiplex system. The device includes a preliminary elector and a confidence elector. The preliminary elector is configured to generate, when a vote having the current order number, the current round number, and a nominated state is acquired from a primary computer, a vote that includes data included in the acquired vote, the current order number, a round number following the current round number, and a winning-assured state. The confidence elector is configured to determine, when a vote having the current order number, the current round number, and the winning-assured state is acquired for identical data from each of a threshold or more of the computers, data included in the acquired vote to be data to be processed at the current order number.

First claim

What is claimed is:

1. A computer in a multiplex system that includes a plurality of computers each executing identical processing on a plurality of pieces of data in an identical order, the computer comprising:
one or more processors that execute instructions to perform operations, comprising:
receiving the plurality of pieces of data;
data processing the plurality of pieces of data to form a processed plurality of pieces of data in a processing order;
transmitting the processed plurality of pieces of data, wherein the data processing further comprises:
managing a current order number and a current round number;
causing a first preliminary election by,
in a first case in which a vote order number is identical to the current order number, a round number is identical to the current round number, and a selection state is a nominated state acquired from a primary computer among the plurality of computers, generating a generated vote that includes data included in a vote acquired from the primary computer, the current order number, a round number following the current round number, and a winning-assured state,
outputting the generated vote to the plurality of computers, and
incrementing the current round number to a next value;

causing a confidence election by, in a second case in which the vote order number is identical to the current order number, the round number is identical to the current round number, and the selection state is the winning-assured state that is acquired for identical data from each of a first threshold or more of the plurality of computers, determining data included in the vote acquired from each of the first threshold or more of the plurality of computers to be data to be processed at the current order number; and
processing data according to the order number.

2. The computer according to claim 1 , the operations further comprise causing a second preliminary election by
in a third case in which no vote is generated by the first preliminary election, and the vote order number is identical to the current order number, the round number is identical to the current round number, and the selection state is a nominated state that is acquired for identical data from each of a majority of the plurality of computers, the generated vote includes data included in the vote acquired from the majority of the plurality of computers, the current order number, a round number following the current round number, and the winning-assured state,
outputting the generated vote to the plurality of computers, and
incrementing the current round number to a next value.

3. The computer according to claim 2 , wherein the operations further comprise generating an initial vote by
generating, when the current round number has an initial value, the generated vote that includes first data, the current order number, the current round number, and the nominated state, and
outputting the generated vote to the plurality of computers, wherein
the first data is data that is received from outside and an order which is not determined, or data included in the vote order number that is identical to the current order number and the round number is the initial value.

4. The computer according to claim 3 , wherein causing the confidence election further comprises
generating, in the second case, the generated vote that includes data included in the vote acquired from each of the first threshold or more of the plurality of computers, the current order number, and a winning state,
outputting the generated vote to the plurality of computers,
incrementing the current order number to a next value, and
setting the current round number back to the initial value.

5. The computer according to claim 4 , wherein the operations further comprise identifying a winning processor that executes instructions to perform additional operations comprising: when the vote order number is identical to the current order number and the selection state is a winning state acquired from any of the plurality of computers, determining data included in the generated vote, wherein the selection state is the winning state, and wherein the data represents data to be processed at the current order number.

6. The computer according to claim 2 , wherein the causing of the second preliminary election further comprises:
when the vote order number is identical to the current order number and the round number is identical to the current round number acquired from each of a second threshold or more of the plurality of computers not in the third case, generating the generated vote that includes data included in any of the acquired votes, the current order number, the round number following the current round number, and a substitution state,
outputting the generated vote to the plurality of computers, and
incrementing the current round number to the next value.

7. The computer according to claim 2 , wherein the operations further comprise causing any one of the first preliminary election, the second preliminary election, and the confidence election to execute processing for each current round number, wherein the causing further comprises:
in response to the confidence election, executing processing when the current round number is a value following a round number at which any of the first preliminary election and the second preliminary election has caused execution of the processing, and
in response to the first preliminary election, executing processing when the current round number has an initial value.

8. The computer according to claim 2 , wherein the operations further comprise causing any one of the first preliminary election, the second preliminary election, and the confidence election to execute processing for each current round number, wherein the causing further comprises
in response to the confidence election, executing processing when the current round number is a value following a round number at which any of the first preliminary election and the second preliminary election has caused execution of the processing, and
in response to the first preliminary election, executing processing when the current round number has an initial value or has a predetermined value at which the confidence election does not cause execution of the processing.

9. The computer according to claim 1 , wherein the causing of the first preliminary election further comprises
when the vote order number is identical to the current order number and the round number is identical to the current round number acquired from each of a second threshold or more of the plurality of computers not in the first case, generating the generated vote that includes data included in any of the acquired votes, the current order number, a round number following the current round number, and a substitution state,
outputting the generated vote to the plurality of computers, and
incrementing the current round number to a next value.

10. The computer according to claim 9 , wherein the second threshold is n−f where n represents the number of the computers and f represents an allowable number of computers in failure.

11. The computer according to claim 1 , wherein the causing of the confidence election further comprises:
in a fourth case in which the vote order number is identical to the current order number and the round number is identical to the current round number acquired from each of a second threshold or more of the plurality of computers not in the second case, generating the generated vote that includes data included in any of the acquired votes, the current order number, a round number following the current round number, and a nominated state,
outputting the gener

Assignees

• Toshiba Kk
• Toshiba Solutions Corp

Inventors

• Endo Kotaro

Classifications

• G06F11/00

  Error detection; Error correction; Monitoring (error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00) · CPC title

• G06F11/1629

  Error detection by comparing the output of redundant processing systems · CPC title

• G06F11/182

  based on mutual exchange of the output between redundant processing components · CPC title

• G06F11/18

  using passive fault-masking of the redundant circuits {(error detection by comparing the output of redundant processing systems with continued operation after detection of the error G06F11/165)} · CPC title

• G06F11/187 Primary

  Voting techniques · CPC title