Bam! Your New Horizons X spacecraft has just suffered a massive strike from an asteroid! Alarms...

Transcribed Image Text:

Bam! Your New Horizons X spacecraft has just suffered a massive strike from an asteroid! Alarms are going off all around you. And a dog can be heard yelping and a cat can be heard welping in agony, somewhere inside the spacecraft. You talk to Commander Brand and your colleague on board Pilot Rheya Cooper about this, and they counsel you that the animals are your imagination. Anyway, back to work... Commander Amelia Brand, Pilot Rheya Cooper, and you quickly figure out that the alarms are because of the mutual exclusion algorithm implemented in the system - if you can fix it, the spacecraft will return to normal operations. You see that the datacenter uses the Ricart-Agrawala algorithm for mutual exclusion but instead of using the usual and boring (Lamport timestamp, process id) pair, the algorithm instead uses (Lamport timestamp, FIFO local sequence number) pair, where FIFO local sequence number is the local sequence number of that event at that process. The rest of the Ricart-Agrawala algorithm remains unchanged. Your fellow astronaut says this algorithm, even without failures: a) violates safety, b) violates liveness, and c) does not satisfy causal ordering. Is he right on any of these counts (which ones)? Give a proof or counter-example. Bam! Your New Horizons X spacecraft has just suffered a massive strike from an asteroid! Alarms are going off all around you. And a dog can be heard yelping and a cat can be heard welping in agony, somewhere inside the spacecraft. You talk to Commander Brand and your colleague on board Pilot Rheya Cooper about this, and they counsel you that the animals are your imagination. Anyway, back to work... Commander Amelia Brand, Pilot Rheya Cooper, and you quickly figure out that the alarms are because of the mutual exclusion algorithm implemented in the system - if you can fix it, the spacecraft will return to normal operations. You see that the datacenter uses the Ricart-Agrawala algorithm for mutual exclusion but instead of using the usual and boring (Lamport timestamp, process id) pair, the algorithm instead uses (Lamport timestamp, FIFO local sequence number) pair, where FIFO local sequence number is the local sequence number of that event at that process. The rest of the Ricart-Agrawala algorithm remains unchanged. Your fellow astronaut says this algorithm, even without failures: a) violates safety, b) violates liveness, and c) does not satisfy causal ordering. Is he right on any of these counts (which ones)? Give a proof or counter-example.

Answer rating: 100% (QA)

A A Violates Safety The RicartAgrawala algorithm does not violate safety as it guarantees that only one process at a time can enter the critical section This is achieved by having each process broadca... View the full answer