Assignment 5: Exploring Deadlock in Ray

Answer the specific questions and follow instructions in items 1-8. The comments in between that are not numbered are informative.

Deadlock in point-to-point messaging.

We implement paired send and receive between two actors using remote functions. The concept is that the argument to a remote function contains the message. Ray packages the content of the argument and sends it to the remote actor.

1. Complete the TODOs in push_sendrecv.py. Run the program to verify that:
   1. synchronized sends (one at a time) succeed
   2. concurrent sends deadlock
2. Analyzing the deadlock. Because there is a deadlock, we can conclude that Ray actors have a single execution context, i.e. a single process.
   1. Draw a deadlock dependency graph. Label the processes and the resources.
   2. Would there be a deadlock if the receive actors ran each invocation of a remote() function in an independent thread. Explain your answer.

Deadlock in queued messaging.

3. Complete the TODOs in queued_sendrecv.py.

The reference implementation used helper functions _qsend() and _qreceive(). The function prototypes have been left in. You do not need to implement or use these functions.

4. This implementation removes the send/send deadlock of question 1. How? Explain.

You will notice that receive/receive results in a deadlock. This is obvious, synchronous receive means that both parties are waiting to receive and no one sends.

5. Pairing: one sender and one receiver also does not result in deadlock. In paired send and receive, can the messages from two parties be sent concurrently or are they serialized? Explain. Draw a simple diagram/picture that justifies you explanation.

6. If we were to extend this implementation to n parties that all communicate pairwise through queues, how many queues would be needed?

It turns out that scalable messaging among multiple parties, i.e. aysynchronous I/O, is a challenging computer science problem. It requires a lot of state to be maintained somewhere.

Paired Send and Receive

7. Complete the TODOs in paired_sendrecv.py.

Turning it in:

Submit the completed python files and a PDF that contains your answers to Gradescope.

Due date: Monday December 6, 2020 at 5 pm. (Last day of classes.)

But, you may turn it in as late as Wedneday December 8, 2020 at 5 pm with no late penalties.