Alyssa Byrnes

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
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, 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:

- Every argument to an instance of
*Enqueue*is unique. - Every non-⊥ return value of an instance of
*Dequeue*is unique. - Every non-⊥ value which an instance of
*Dequeue*returns is the argument to a previous instance of*Enqueue*. - If ρ is a legal sequence of operation instances, then ρ •
Dequeue(-,val)$ is legal iff every
*Enqueue(val',-)*preceding*Enqueue(val,-)*has a matching $Dequeue(-,val')$ in ρ or there are fewer than*k*instances*Dequeue(-,val')*that follow the first*Enqueue(val'',-)*which does not have a matching*Dequeue(-,val'')*in ρ.

- For all processes p
_{i}and p_{j}and every prefix π' of π, lQueue_{i}at time t(π',i) is the same as lQueue_{j}at time t(π',j).

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

- At t(π' i), if lQueue
_{i}.size() ≥ 1, lQueue_{i}.head.available==false for every prefix π' of π and every i ∈ [0, n-1]. - Two slow dequeues will not both return the same value.
- A slow dequeue
*deq*from some process p_{i}will not return the value x identified as the local head on behalf of another slow dequeue with an earlier timestamp removing x from lQueue_{i}in between*deq*'s invocation and local execution.

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.

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.