Fast Neural Network for Distributed Systems of Data
Birman-Schipher-Stephenson (BSS) protocol
Ø When a process broadcasts a message it also broadcasts how many messages it has received from each of the other processes.
Ø When a process receives a message from another process it checks whether it has received all previous messages from that same process and also whether it knows about at least as many messages in the system as the sender process does. If both checks are true, the recipient process executes the message, otherwise it puts the message on hold and waits.
Example
Let a distributed system have 3 agents a, b and c. Suppose they have broadcast messages according to the following space-time diagram (Figure).
At point 1 the message from a (say a1) is received by b. Since this is the first message from a and a did not know of any other messages from any other process while sending it, b can execute this message according to the protocol. However at point 2, where the message from b (say b1) is received by c, c gets to know that b knows a1. But since c does not know about a1, it keeps b1 on hold and waits for a1 to arrive.
Lamport’s Mutual Exclusion
(Index of a message). Index of a message generated by a pro- cess is 1 if the process has not sent or received any other message before. Otherwise it is 1 more than the highest indexed message received or sent by the process.
Lamport’s Mutual Exclusion
Requesting the Critical Section
1. When a process wants to access the critical section, it generates a REQUEST and a timestamp for that REQUEST. The process keeps this REQUEST in its own REQUEST queue sorted according to timestamps and then broadcasts it to all other processes along with the timestamp.
2. When a process receives a timestamped REQUEST, it keeps the REQUEST in its own REQUEST queue sorted according to timestamps. Then it generates a timestamped REPLY corresponding to the REQUEST and sends the REPLY to the sender of the REQUEST.
Accessing the Critical Section
When a process observes
3. its REQUEST is at the top of its own REQUEST queue, and
4. it has received at least one message (REQUEST or REPLY or RELEASE) with higher timestamp than its REQUEST from all other processes,
the process enters the critical section.
Releasing the Critical Section
5. When a process exits the critical section, it generates a timestamped RE- LEASE message and broadcasts it to all other processes. It deletes its own REQUEST from its REQUEST queue.
6. Upon receiving a RELEASE message, a process removes the REQUEST of the sender process from its own REQUEST queue.
Lamport’s Mutual Exclusion
Example
Let us suppose a, b and c are 3 agents of a distributed system with ID(a) < ID(b) < ID(c). Assume that they have generated critical section REQUESTs Ra,1, Rb,1 and Rc,1 respectively according to the following space-time diagram (Figure). Here REQUESTs are color coded RED and REPLYs are color coded BLUE.
Observe that the REQUEST Ra,1 has the timestamp 1; ID(a). At the point marked 6, a has already heard a REPLY from b of timestamp 2; ID(b) (point 2) and a REQUEST Rc,1 from c of timestamp 1; ID(c). Thus at point 6, Ra,1 is at the top of a’s REQUEST queue and a has heard at least one message of higher timestamp from both b and c. So at point 6, a can access the critical section. However for b and c, both conditions do not hold simultaneously. Observe that at point 3, the REQUEST Rc,1 is at the top of c’s REQUEST queue and c has already received the REQUEST Rb,1 of timestamp 3; ID(b)(> 1; ID(c)). However, c has not yet received a message of higher timestamp from a. When c finally receives a message of higher timestamp from a at point 12 (the REPLY of a corresponding to Rc,1 has timestamp 6; ID(a) > 1; ID(c)), Rc,1 is no longer at the top of c’s REQUEST queue since c has already received a REQUEST Ra,1 of lower timestamp (1; ID(a)) at an earlier point (8). Similarly, we can check the case of b as well.
