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.
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. Nonetheless, it is still worthwhile to try to construct a lateness queue in order to show that the implementation is possible.
This week I developed an algorithm to represent the k-relaxed lateness queue.
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
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, 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!
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.
My first draft of my proof is now complete! I submitted it to Dr. Welch and Edward
for review. They had many constructive criticisms. My main goal is to clearly define lemmas and
properties of the algorithm and then prove them. The challenge with this is to
find which properties are crucial in proving the correctness of the algorithm.
Some basic crucial properties are the following:
Lateness Property: No more than k dequeues can occur before the element with the earliest timestamp is dequeued.
Time Stamp Order: All operations are locally executed in the order in which they were invoked.
This week we had a very fun barbecue for the fourth of July! All of the students to research projects at Texas A&M for the summer were invited. It was exciting spending time with students passionate about research. Also, we had a workshop on technical writing and poster presentations. This taught me a lot about writing research papers because I am not a strong writer.
This week, we cleaned up and finalized our proof that all events locally execute in timestamp order.
This took a lot of thought. The proof came down to considering different cases of execution
time in a system. More specifically, an operation will either locally execute when either its
local timer expires or another operation with an earlier timestamp's timer expires.
We then showed that this algorithm not only respects timestamp order, but
also respects real time order across all processes.
We also had a talk about work and life balance, which was presented by some professors at Texas A&M. Dr. Welch was one of the presenters. This talk gave me some perspective and a better idea of what my future will look like during and after graduate school.
This week we began our correctness proof. Our main goal is to prove that the algorithm maintains all of the properties of a legal k-relaxed lateness queue, which are the following:
This week, we finished a first draft of the correctness proof. We added some additional lemmas:
This final week was spent wrapping up the project. Firstly, I add the runtime proof to our paper,
show that the average time complexity for any dequeue operation is no more than
d⁄⌊k/n⌋+ε, where all local clocks are within ε of eachother, d is the message delay between processes and u is the uncertainty.
Then I finished the week by creating a poster to present my research. I presented it for graduate students and professors in the computer science department. It made me very nervous at first, and they asked some difficult questions, but it was a very good experience. Now I better know what kind of questions to prepare for and how to clearly and concisely summarize my project.