JP2001256209A - Method and mechanism for fault tolerant consensus for asynchronous shared object system - Google Patents

Abstract

PROBLEM TO BE SOLVED: To solve a fault tolerant consensus problem at much higher speed. SOLUTION: Multiple processors 0, 1 and 2 perform communications 3, 4 and 5 of information while using a shared object 6. The shared object 6 is composed of a multiple-writable and multiple-readable binary variable 7 and a single-writable and multiple-readable binary variable array 8. Each of processors has an initial value and performs the communications 3, 4 and 5 while using the shared object 6. As a result, it is necessary for all non-broken processors to determine the same value. All the processors can equally write the binary variable 7 but the binary variable array 8 is limited in write areas for respective processors. For example, the processor 21 can perform write 4 to y[2][1]9 and y[2][2]10 of the binary variable array 8. Namely, each of all the processors performs write only to the area, where the row number of the binary variable array 8 is equal with the number of the processor.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION In a shared object system comprising a plurality of asynchronous processors transmitting information through a shared object, all non-failed processors obtain an agreement after a finite step without being affected by a stopped processor due to a failure. Methods, methods for solving consensus problems in fault-tolerant asynchronous shared object systems, and their implementation mechanisms.

[0002]

2. Description of the Related Art In a shared object system comprising a plurality of processors, a fault-tolerant agreement problem in an asynchronous shared object system in which all non-failed processors agree on one value regardless of a failed processor has stopped. It has an effective application in synchronization and processor fault detection in asynchronous systems. The asynchronous shared object system includes a shared object which is a set of a plurality of processors and a finite number of shared binary variable arrays. The processors communicate via a shared binary variable array.
Each processor has a port for performing input operation and output operation and interacting with the outside. Let V be a set of values, 1 to n
Consider a shared object system consisting of n processors labeled with natural numbers up to and a set X of shared binary variables. The external input to each processor is init (v). Here, v is an element of the set V. Each processor outputs to the outside in the form of decide (v).

[0003] Each processor may have a special input Stop. The Stop signal is an external input that cannot be specified, and stops operation after receiving the Stop signal of the process. Agreement is reached when the shared object system meets the following three conditions: (1) For any processor, i of that processor
The temporal sequence of nit and decide is a prefix with columns init (v) and decide (w). That is, there is nothing, only init (v), or a sequence of two actions of init (v) and decide (w). (2) All the determined values are the same value. (Agreement condition)
(3) The determined value is an input value of a certain processor. (Va
lidity condition)

[0004] Even if an arbitrary number of processors from 1 to n-1 are stopped in the shared object system upon receiving the Stop signal, when all the remaining non-stopped processors agree, the system will pass a fault-tolerant agreement. Reach.

[0005] This fault-tolerant agreement is assigned to each of the two shared objects.
It shows what methods exist when value variable arrays are typed by applicable operations. Conventionally, a binary variable array of a shared object allows only reading or writing in one instruction. Read-write A binary variable array and a read-modify-writ that can execute both writing and reading in one instruction
e It is roughly divided into a binary variable array. In an asynchronous shared object system, a fault-tolerant agreement cannot be obtained only with a read-write binary variable array. A specific example of an agreement method using a shared binary variable array x whose initial value is unknown will be described.

It is assumed that an external input value is k. Next, read
(x) The value of the shared binary variable array x is received as the return value v by the instruction. If the value v remains unknown,
The value of k is assigned to the shared binary variable array x by the write (x, k) instruction, and agree with the value k by decide (k). Otherwise, deci
Agree on the value v in de (v). In this case, the content of the shared object is read, and the content of the shared object changes before the processor performs writing according to the content, which leads to disagreement.

Therefore, a consensus method having fault tolerance by read-modify-write in which both reading and writing are performed by one instruction is considered. One of the read-modify-write instructions
The compare-and-swap instruction will be described. Compare-and-swap (x, v, k) for shared binary variable array x, value v, value k
The instruction writes a value k to the shared binary variable array x and returns a value w as a return value if the value w of the shared binary variable array x matches v. Otherwise, do nothing and return the value w as the return value. This procedure is executed during one instruction step.

An example of a method of obtaining a fault-tolerant agreement by a compare-and-swap instruction will be described. In a shared binary variable array x whose initial value is unknown, an external input value is initially set to k. Next, if the value w of the shared binary variable array x is unknown by the compare-and-swap (x, unknown, k) instruction, k is written to x and unknown is received as a return value. Otherwise, w
Is received as the return value. If the return value v of the compare-and-swap instruction is unknown, agree with the value k by decide (k). Otherwise, agree value v with decide (v).

In the case of a binary array variable x that allows only a single write without allowing multiple writes of the shared binary variable array contents, r
During execution of the ead-modify-write instruction, the variable x is locked,
All other instructions for variable x become unexecutable.

A plurality of processors simultaneously execute r for a variable x.
When the ead-modify-write instruction is issued, a lock having a length equal to the number of processors is formed. This situation is called a conflict. In addition, the maximum number of locks belonging to a lock sequence that can be performed for one instruction, that is, the length is defined as the contention cost.

[0011]

Problems to be Solved by the Invention
With the ad-modify-write instruction, the contention cost increases in proportion to the number of processors in the system. Read-mod in theory
It has been shown that the competitive cost of any fault-tolerant agreement method using ify-write instructions increases in proportion to the number of processors. Read instruction and writ to reduce the contention cost
There is also a method that guarantees the probability that an agreement will fail only with e-commands. In this case, the cost of the competition does not depend on the number of processes, but the number of execution steps of the method is proportional to the square or the cube of the number of processors. The present invention proposes a method and a mechanism for obtaining a consensus efficiently when the contention cost has a fault tolerance independent of the number of processors, and particularly when the processors operate almost synchronously.

[0012]

In order to achieve the above object, in the shared object system according to the present invention, a shared binary variable array x capable of simultaneous reading and writing by all processors and capable of simultaneous reading and writing is provided for each processor. , A single-write-multiple-read binary variable array is set which allows only that processor to write and all other processors to read simultaneously.

Further, the shared object system of the present invention has a new instruction read-and-write (x, y, k). The read-and-write instruction is an instruction for reading the shared binary variable array x and writing the shared binary variable array y in one step. The variable y to be written from the start to the end of the instruction is locked, and other processors read and write. Can not. However, the variable x to be read does not require exclusive control, that is, multiple reading and writing are permitted. Specifically, when the variable x is 1, k is written to the variable y and 1 is returned. When the variable x is not 1, the following procedure of returning 0 without performing anything is executed in one instruction step.

[0014]

DESCRIPTION OF THE PREFERRED EMBODIMENTS At this time, the shared object system is a binary array capable of all multiple writing and multiple reading.
n × 2 two-dimensional binary variable arrays y [n], which is twice as many registers as processor n and single write and multiple read registers
It has [2]. Each processor i can write only elements i [i] [1] and y [i] [2] which are elements in the i-th row in the array y. Initial setting x = 1, all 2n elements of y [n] [2] are NULL
The following protocol is executed in each processor i.

First, let the input value be k. write (y [i] [2],
k) Write the value k to the shared binary variable array y [i] [2] by the instruction. Next, if the value of the shared binary variable array x is 1 by the read-and-write (x, y [i] [1], 1) instruction, the shared variable array y [i] [1]
Write the value 1 to, otherwise do nothing. next
Write 1 to the shared binary variable array x by the write (x, 0) instruction. Then, j is changed from 1 to n until the index j whose return value by the read (y [j] [1]) instruction is 1 is found in the loop indexed by the local variable j.
Increase by one. After exiting the loop, the read (y [j] [2]) instruction is executed to set the value of the shared binary variable array y [j] [2] to v. Finally, agree on the value v by decide (v).

[0016]

According to the invention agreement protocol, even if there is a failed processor in the system, a non-failed processor can terminate the protocol. When the invention mechanism is used in the invention agreement protocol, each processor writes y [i] [2] with a write instruction and y [i] with a read-and-write instruction.
Lock only [1]. The write instruction for x does not require a lock because multiple writing and reading are possible.
Therefore, the lock length for each instruction is at most 1
And the contention cost of the invention agreement protocol is 1.
That is, the contention cost does not depend on the number of processes in the system. Especially in an almost synchronized system, no matter how many processes are performed, the end of the protocol is almost simultaneously completed in a small number of steps.

[Brief description of the drawings]

FIG. 1 is a diagram showing an embodiment of a shared object system.

FIG. 2 is a diagram showing an embodiment of a shared binary variable array.

Claims (4)

[Claims] 1. An asynchronous shared object system comprising a plurality of asynchronous processors, a binary variable array, and a binary variable array group, wherein the binary variable array group has two writable areas for one processor. It is provided with one for writing an input value and the other for writing a value "1" which can be asked for true or false.
A plurality of asynchronous processors having a one-to-one relationship and all regions being disjoint, means for writing a received input value to a shared binary variable array group, and reading true / false of the shared binary variable array; A means for writing a value to the latter area of the group of shared binary variable arrays in a single step time based on the result, a means for writing the value of the shared binary variable array so as to reverse the true / false, An agreement solution method characterized by comprising: means for reading the latter value of a shared binary variable array group in ascending order, and means for determining the read input value. 2. In a shared object system in which a plurality of asynchronous processors transmit information through a shared object, a binary variable array x, a binary variable array y, and a value k of two shared objects are used for the shared binary variable array x. A read-and-write instruction that executes reading and writing of the shared binary variable array y in one instruction step. 3. The shared object system according to claim 2, wherein the plurality of asynchronous processors transmit information through the shared object, wherein the binary variable array x, the binary variable array y, and the value k of the two shared objects are shared binary. The variable y that is written until the reading of the variable array x and the writing of the shared binary variable array y are locked and cannot be read or written by other processors, but the variable x to be read does not require exclusive control, that is, , Multiple read and write procedures are executed in one instruction step
read-and-write instructions. 4. A shared object system in which a plurality of asynchronous processors transmit information through a shared object, in the method for obtaining consensus of claim 1, wherein said processors can write and read at the same time. 4. A read / write binary variable array which is readable by only one processor and readable by all other processors at the same time for each processor. A binary variable array capable of performing the -and-write instruction in the above-described multiple-write multiple-read, and a single-write multiple-read capable in which only the processor can write to each processor and all other processors can simultaneously read each processor. It applies to the value variable array and Mechanism in which all of the processors that do not Razz failure to realize a high-speed fault-tolerant agreement technique to obtain the agreement after a finite step.