From Traditional Fault Tolerance to Blockchain. Wenbing Zhao. Читать онлайн. Newlib. NEWLIB.NET

Автор: Wenbing Zhao
Издательство: John Wiley & Sons Limited
Серия:
Жанр произведения: Зарубежная компьютерная литература
Год издания: 0
isbn: 9781119682110
Скачать книгу
type. It is used for the receiving process is notify the sending process the receiving/execution order of the message. An ORDER message carries the form <ORDER, [m], rsn>, where [m] is the message identifier consisting of a tuple <sender_id, receiver_ id, seq>.

       ◾ ACK message type. It is used for the sending process (of a regular message) to acknowledge the receipt of the ORDER message. It assumes the form <ACK, [m]>.

       2.3.2.2 Normal Operation of the Message Logging Protocol

Schematic illustration of normal operation of the sender-based logging protocol.

      The protocol operates in three steps for each message:

      1 A REGULAR message, <REGULAR,seq,rsn,m>, is sent from one process, e.g., Pi, to another process, e.g., Pj.

      2 Process Pj determines the receiving/execution order, rsn, of the regular message and informs the determinant information to Pi in an ORDER message <ORDER, [m], rsn>.

      3 Process Pj waits until it has received the corresponding acknowledgment message, <ACK, [m]>, before it sends out any REGULAR message.

      Furthermore, in the original sender-based message logging protocol [13] , the regular message and the ordering message must be retransmitted after a timeout before the expected acknowledgment message is received. With the use of reliable channels, such proactive retransmission becomes unnecessary because the only scenario in which a retransmission is necessary is when a process fails, in which case, the retransmission will be triggered by the recovery mechanism (more in section 2.3.2.3).

      The use of a mature reliable communication protocol such as TCP in distributed applications is more desirable because the application developers can focus on the application logic and application-level messaging reliability without worrying about issues such as achieving high throughput and doing congestion control.

      EXAMPLE 2.6

      On receiving the regular message <REGULAR,0,?,m0>, P1 assigns the current rsn counter value, which is 0, to this message indicating its receiving order, increments its rsn counter to 1, and sends P0 an ORDER message <ORDER,[m0],0>. When P0 receives this ORDER message, it updates the entry in its message log to reflect the ordering number for message m0, and sends an sc ack message, <ACK,[m0]>, to P1.

      Once receiving the ACK message, P1 is permitted to send a regular message, <REGULAR,0,?,m1>, to P2. The handling of the message and the corresponding ORDER and ACK messages are similar to the previous ones.

Schematic illustration of an example normal operation of the sender-based logging protocol.

      Subsequently, P0 and P2 send three regular messages m2, m3, m4, nearly concurrently to P0. P1 assigns 1 as the rsn value for the first of the three messages (for m2) and sends an ordering message to P0, and assigns 2 and 3 for the two back-to-back regular messages (for m3 and m4) from P2. For the two messages from P2, P1 can batch the ORDER messages and sends them together to P2, and P2 can batch the corresponding the ACK messages to P1 too. Upon receiving the ACK messages for all three ORDER messages, P1 sends another regular message containing m5 with sequence number 1, updates the seq counter to 2, and log the message.

      On recovering from a failure, a process first restores its state using the latest local checkpoint, and then it must broadcast a request to all other processes in the system to retransmit all their logged messages that were sent to the process.

       ◾ If the entry in the log for a message contains no rsn value, then a REGULAR message is retransmitted because the intended receiving process might not have received this message.

       ◾ If the entry in the log for a message contains a valid rsn value, then an ACK message is sent so that the receiving process can send regular messages.

      When a process receives a regular message, it always sends a corresponding ORDER message in response. There are three scenarios:

       ◾ The message is not a duplicate, in which case, the current rsn counter value is assigned to the message as its receiving order, and the corresponding ORDER message is sent. The process must then wait for the ACK message before it sends any regular message.

       ◾ The message is a duplicate, and the corresponding rsn value is found in its history list, in which case, an ORDER is message is sent and the duplicate message itself is discarded. The process must then wait for the ACK message before it sends any regular message. Note that it is impossible for the process to have received the corresponding ACK message before because otherwise the recovering process must have logged the rsn value for the regular message.

       ◾ The message is a duplicate, and there is no corresponding entry in the history list. In this case, the process must have checkpointed its state after receiving the message and it is no longer needed for recovery. As a result, the process sends an ORDER message with a special constant indicating that the message is no longer needed and the sending processing can safely purge the entry from its message log.