Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 52 views

    Causal Ordering of Messages: Space P1 Send (M1)

    Uploaded by

    aman
    The document describes three algorithms for maintaining causal message ordering in distributed systems: 1) The BSS algorithm uses vector clocks and broadcast messages to ensure message M1 is received before M2 at all processes. It delivers messages when the preceding message's vector clock is received. 2) The SES algorithm does not require broadcast. Each process maintains a vector of received messages from other processes. It delivers a message when the vector in the message is less than or equal to the local vector. 3) Both algorithms buffer messages that do not satisfy the delivery conditions to ensure causal message delivery.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Causal Ordering of Messages: Space P1 Send (M1)

    Uploaded by

    aman
    52 views8 pages
    The document describes three algorithms for maintaining causal message ordering in distributed systems: 1) The BSS algorithm uses vector clocks and broadcast messages to ensure message M1 is received before M2 at all processes. It delivers messages when the preceding message's vector clock is received. 2) The SES algorithm does not require broadcast. Each process maintains a vector of received messages from other processes. It delivers a message when the vector in the message is less than or equal to the local vector. 3) Both algorithms buffer messages that do not satisfy the delivery conditions to ensure causal message delivery.

    Original Description:

    Original Title

    BSS

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes three algorithms for maintaining causal message ordering in distributed systems: 1) The BSS algorithm uses vector clocks and broadcast messages to ensure message M1 is received before M2 at all processes. It delivers messages when the preceding message's vector clock is received. 2) The SES algorithm does not require broadcast. Each process maintains a vector of received messages from other processes. It delivers a message when the vector in the message is less than or equal to the local vector. 3) Both algorithms buffer messages that do not satisfy the delivery conditions to ensure causal message delivery.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    52 views8 pages

    Causal Ordering of Messages: Space P1 Send (M1)

    Uploaded by

    aman
    The document describes three algorithms for maintaining causal message ordering in distributed systems: 1) The BSS algorithm uses vector clocks and broadcast messages to ensure message M1 is received before M2 at all processes. It delivers messages when the preceding message's vector clock is received. 2) The SES algorithm does not require broadcast. Each process maintains a vector of received messages from other processes. It delivers a message when the vector in the message is less than or equal to the local vector. 3) Both algorithms buffer messages that do not satisfy the delivery conditions to ensure causal message delivery.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 8

    Causal Ordering of Messages

    Space Send(M1)
    P1

    Send(M2)
    P2

    P3 (1)

    (2)
    Time

    1
    Message Ordering
     Not really worry about maintaining clocks.
     Order the messages sent and received among all processes in a
    distributed system.
     (e.g.,) Send(M1) -> Send(M2), M1 should be received ahead of M2
    by all processes.
     This is not guaranteed by the communication network since M1 may
    be from P1 to P2 and M2 may be from P3 to P4.
     Message ordering:
     Deliver a message only if the preceding one has already been
    delivered.
     Otherwise, buffer it up.

    2
    BSS Algorithm
     BSS: Birman-Schiper-Stephenson Protocol
     Broadcast based: a message sent is received by all other
    processes.
     Deliver a message to a process only if the message
    preceding it immediately, has been delivered to the process.
     Otherwise, buffer the message.
     Accomplished by using a vector accompanying the message.

    3
    BSS Algorithm ...

    1. Process Pi increments the vector time


    VTpi[i], time stamps, and broadcasts the
    message m. VTpi[i] - 1 denotes the number
    of messages preceding m.
    2.Pj != Pi receives m. m is delivered when:
    a. VTpj[i] == VTm[i] - 1
    b. VTpj[k] >= VTm[k] for all k in {1,2,..n} - {i}, n is the total
    number of processes. Delayed message are queued in a sorted
    manner.
    c. Concurrent messages are ordered by time of receipt.
    3. When m is delivered at Pj, VTpj updated according Rule 2 of
    vector clocks.

    4
     2(a) : Pj has received all Pi’s messages preceding m.
     2(b): Pj has received all other messages received by
    Pi before sending m.

    5
    SES Algorithm
     SES: Schiper-Eggli-Sandoz Algorithm. No need for broadcast
    messages.
     Each process maintains a vector V_P of size N - 1, N the
    number of processes in the system.
     V_P is a vector of tuple (P’,t): P’ the destination process id and
    t, a vector timestamp.
     Tm: logical time of sending message m
     Tpi: present logical time at pi
     Initially, V_P is empty.

    6
    SES Algorithm
     Sending a Message:
     Send message M, time stamped tm, along with V_P1 to P2.
     Insert (P2, tm) into V_P1. Overwrite the previous value of
    (P2,t), if any.
     (P2,tm) is not sent. Any future message carrying (P2,tm) in
    V_P1 cannot be delivered to P2 until tm < tP2.
     Delivering a message
     If V_M (in the message) does not contain any pair (P2, t), it
    can be delivered.
     /* (P2, t) exists */ If t > Tp2, buffer the message. (Don’t
    deliver).
     else (t < Tp2) deliver it

    7
    SES Algorithm ...
     On delivering the message:
     Merge V_M (in message) with V_P2 as follows.
     If (P,t) is not there in V_P2, merge.
     If (P,t) is present in V_P2, t is updated with max(t in Vm, t in
    V_P2).
     Message cannot be delivered until t in V_M is greater
    than t in V_P2
     Update site P2’s local, logical clock.
     Check buffered messages after local, logical clock update.

    You might also like