My Project Journal

Alyssa Byrnes

Week One - 6/1/2015

Project Description

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.

Week Two - 6/8/2015

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.

Week Three - 6/15/2015

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 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.

Week Four - 6/22/2015

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!

Week Five - 6/29/2015

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.

Week Six - 7/6/2015

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.

Week Seven - 7/13/2015

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.

Week Eight - 7/20/2015

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:

In order to prove these properties, we defined some smaller properties, including the following: Here, π represents the permutation of operation instances in a complete, admissible run of the algorithm and t(π',i) is the real time when process pi has just finished locally executing the last operation in π'.

Week Nine - 7/27/2015

This week, we finished a first draft of the correctness proof. We added some additional lemmas:

The most extensive part of the correctness proof was proving that every instance of Dequeue was unique. We had to break the proof up into different cases of consecutive dequeues and prove that no combination would cause the same element to be dequeued twice.
We also had a talk on resumes & interviews. The main focus of this was learning how to create an impressive resume for a job, but I was able to apply these skills to create an academic resume to apply for graduate school.

Week Ten - 8/3/2015

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.

Final Report

Final Report