Obsidian + 🪴 Quartz 4.0

IoT2 - Midterm Exercise - Distributed Control Algorithms (MIDTERM Exercise)

6 min read

IoT2 - Midterm Exercise - Distributed Control Algorithms

Exercises

P0 T=4 CS=4, T=9 CS=3
P1
P2 T=7 CS=3
 
 
Ricart Agrawala
P1 T=7 CS=3
P2
P3 T=4 CS=3
P4 T=8 CS=3
P5
P6 T=6 CS=3
P7
 
Maekawa
S1={P1, P2, P3}
S2={P2, P5, P7}
S3={P3, P4, P7}
S4={P4, P1, P5}
S5={P5, P3, P6}
S6={P6, P2, P4}
S7={P7, P1, P6}
 
P3 T=4 CS=3
P5 T=6 CS=2
 
Ring
P1 T=7 CS=3
P2
P3 T=4 CS=3
P4 T=8 CS=3
P5
P6 T=6 CS=3
P7
 
Raymond
P1 T=7 CS=3
P2
P3 T=4 CS=3
P4 T=8 CS=3
P5
P6 T=6 CS=3
P7
 
Suzuki Kasami
P1 T=7 CS=3
P2
P3 T=4 CS=3
P4 T=8 CS=3
P5
P6 T=6 CS=3
P7

Ricart-Agrawala Algorithm

P1 T=7 CS=3
P2
P3 T=4 CS=3
P4 T=8 CS=3
P5
P6 T=6 CS=3
P7
  • Seven processes
  • The process ,, and wants to enter in the critical section at different timestamp
  • The critical section of each process lasts for 3 units of time

Solution:

Note, there is a small error in this exercise

If a process enter CS at time 4 and it takes 3, then he will be free at 4+3+1. I.e at T=7 it will still be busy, after that time unit finish, so the time becomes T=8, then the process exit the CS and the algorithm can proceed.

In the following exercises, regarding other algorithms, the time are correct

Maekawa Algorithm

Maekawa
S1={P1, P2, P3}
S2={P2, P5, P7}
S3={P3, P4, P7}
S4={P4, P1, P5}
S5={P5, P3, P6}
S6={P6, P2, P4}
S7={P7, P1, P6}
 
P3 T=4 CS=3
P5 T=6 CS=2
  • Maekawa is based on quorum and coterie.
  • Each process appartains to a quorum, i.e P3 appartains to quorum S3 ={P3,P4,P7} but also to S5 and S1

For example, quorums where P3 is present: Now, back to the exercise:

Ring Algorithm

Ring
P1 T=7 CS=3
P2
P3 T=4 CS=3
P4 T=8 CS=3
P5
P6 T=6 CS=3
P7

Exercise: Assuming P3 is the owner of the token in an initial state of the system for convenience At T=6, P6 makes the request, it is passed to P3

At T=7, P1 make the request, it send the request towards its outgoing edges At T=8, two things happens:

  • P4 make a request
  • P3 quit the critical section, dequeue himself from the token and releases it

  • Then P6 enters the CS and stay there until T= 8+3+1 = 11
  • At T=11, P6 quit the critical section, removes himself from the queue and pass it to P1
  • At T=15, P1 quit the critical section and pass the token to P4

Raymond Algorithm (Inverse Tree)

Raymond
P1 T=7 CS=3
P2
P3 T=4 CS=3
P4 T=8 CS=3
P5
P6 T=6 CS=3
P7

The initial configuration of the tree can be as we want, for convenience, let be the root at T=4, and this is the configuration: When P3 receives the token, it removes himself!!

At T=6, P6 make a request to his father (P4) that make a request to his father (P3, the root), that is in CS so it just insert the id of his son (P4) in the queue At T=7, P1 make a request to his father (P2) that make a request to his father (P3, the root) that is in CS, so it just insert the id of his son (P2) in the queue. Also important,

At T=8, two events happens:

  • P4 make a request to enter the CS
  • P3 quit the critical section.

Now, this is an interesting situation because P4 already made a request, but for his son, so. Now, still at T=8, P4 see that at the top of his queue, P6, made the request before, so he just passes the token to his son, switch the edge, and make himself a request since the queue (of P4) is not empty.

At T=12, P6 finishes, dequeue P4 and passess the token to P4, and switch the edge, then P4 enters the CS, ad finishes at T=12+3+1 = 16

At t=12+3+1=16, P4 finishes, and pass the token to P3, that pass it to P2 that pass it to P1, they all remove the queue and switch the edges.

P1 finishes at T=19

Suzuki-Kasami Algorithm (Token Based distributed)

Suzuki Kasami
P1 T=7 CS=3
P2
P3 T=4 CS=3
P4 T=8 CS=3
P5
P6 T=6 CS=3
P7

Leader Election - Bully Algorithm

T=1 P7 crashes
T=2 P2 detects failure and starts new elections
T=3 P5 crashes
T=7 P7 is up and running again

Leader Election - Ring Topology Algorithm

T=0 P8 crash
T=2 P7 crash

(assuming, when a process crash, the ring reform himself i.e, if . Then upon crash, connects to )

Variant 1

Variant 2 - Highest id

Graph View