This week, I started writing the proof of correctness for my algorithm. Dr. Welch is very focused on making this a thorough proof, so I have made many drafts already. The biggest challenge in my opinion is organizing the proof well and being descriptive enough. Also we had a nice ice cream social with a lot of the computer science students, which was a great opportunity to hear about other projects that are going on.
If you would like to view my proof as I work on it, view here: https://www.overleaf.com/read/rpdfhwhddhzt
This week, we cleaned up the pseudo code meant to represent a k-lateness queue in a message passing system. Now that it is believed to be correct, the next step would be to prove it. The benefit of this algorithm is that it seems simple and relatively efficient.
The challenge of this algorithm was mainly checking it for correctness. We met almost every day that week and found new errors in the code. Some issues were simply typos, but a lot of the more technical issues were hard to weed out mostly because of the intricacies of tracing the code. Also, we had to consider many different cases in terms of different permutations of enqueues/dequeues. However, hopefully any potential issues we might have missed will be discovered and fixed during the proof process. There were also many fun events last week with other REU participants. One special quality of this program is that there is a group of students doing many different REUs at Texas A&M and we have the opportunities to spend time with a large, diverse group of people. We have spent a lot of time getting to know each other at our apartments. Also, there was a graduate student panel for computer science undergraduates to ask questions about graduate applications and programs. I asked a lot of questions, and it was very helpful! As seen in the previous post, I constructed a pseudocode that loosely models a lateness queue in a message passing system. This code was written to be very similar in format to the code presented by Talmage and Welch for restricted out of order and out of order queues in order to maintain consistency.
The main idea of this code has many similarities to the previous ones. This model also represents a system where fast dequeueing and fast enqueueing are utilized primarily, and the slow dequeueing is only used as needed. The slow dequeue is utilized to make sure the top element (the oldest element) has been removed. The idea of labeling is still used here to assign different resources to processes in a round-robin style, but the data structure maintained by each process is much simpler than that of the one used for restricted out of order queues. Essentially, each process stores their own local copy of the queue being simulated as well as an array of the oldest element assigned to each process. In order to maintain lateness, each process can only do k/n fast dequeues before having to implement a slow dequeue. Here is an idea of what each operation would do: Fast Dequeue - Dequeue an item that is labeled for you. Send a notification to everyone that you dequeued it. Add 1 to your counter to keep track of the amount of dequeues. Slow Dequeue - Send a message for every process to set their counters back to 0. Consult every processor and remove the oldest item from the queue. Fast Enqueue - Enqueue an item to the queue. Send out a notification with a time stamp so processes can correctly order the amount of queued objects. There are inherent issues with this setup already, however. Firstly, there needs to be a way to redistribute resources. The resources are distributed at the end of the enqueues, but if we have a large amount of initial enqueues and each process is evenly distributed resources, then one process dequeues a lot more than the rest, there will be an issue. Some measure will be added to account for this. The largest issue is the fact that processes might execute slow dequeues in close proximity to one another, there might be some miscommunication about what is in fact the oldest element in the queue. My plan for the next few days is to clean up this pseudocode and alleviate these issues. This week, the main issue I was facing was to find an algorithm that effectively represents a lateness queue in a message-passing system. The idea was that because restricted out-of-order queues maintain lateness and out of order queues, there must be a way to simplify the algorithm that Edward Talmage and Dr. Jennifer Welch produced to meet only the lateness requirement. However, the out of order property depends on "labeling" different items in the queue, which essentially assigns resources to each process whenever resources are needed. The restricted out of order queue elaborates on the labeling process, giving processes the ability to reassign resources when needed to maintain the lateness property. It then becomes clear that the method to maintain lateness directly builds off of the method to maintain the k-relaxation of the out of order queue, and therefore it isn't possible to just simplify the restricted out of order pseudo code to get a model that only maintains lateness. However, that does not mean that there aren't other ways to implement a lateness queue efficiently.
Lateness seems to be more costly to implement than the standard k-relaxed out of order queue, and the reason is because processes need to communicate even more. Each process must make sure that the head of the queue is dequeued within k dequeue operations. This means that processes need to find a way to efficiently communicate so that every process is aware when they are about to perform the kth dequeue. This fact makes us less optimistic that a model that maintains lateness would be more efficient than a restricted out of order model. However, it is still worthwhile to try to construct a lateness queue in order to show that the implementation is possible.
Core Concepts
Kirsch, Christoph M., Hannes Payer, Harald Röck, and Ana Sokolova. "Performance, Scalability, and Semantics of Concurrent FIFO Queues."Algorithms and Architectures for Parallel Processing Lecture Notes in Computer Science (2012): 273-87. Web. This project is based on the premise of using relaxed data structures to improve the speed of message passing between different processes on a computer.
An algorithm has been written for out-of-order queues and restricted out of order queues. A an average lower bound and upper bound was found for dequeueing in Restricted Out-of-Order and Out-of-Order k-relaxed queues. Because Restricted Out-of-Order queues maintain lateness, lateness queues are bounded by the average upper bound of these. The idea is that Out-of-Order queues have a smaller average runtime then Rest. O-o-O ones because they have fewer requirements. Therefore, intuitively there should be a way to implement lateness queues faster that R-O-o-O ones. A stuttering k-relaxed queue could probably be implemented similarly to the O-o-O relaxed queue, with an improved run time due to the extra resources offered. |