Title: An Asynchronous Leader Election Algorithm for Dynamic Networks without Perfect Clocks
Description: Leader election algorithm is one of the most widely used algorithms in networks because of the numerous applications it has as a suboperation of other more complicated algorithms. The purpose of the algorithm is to elect a unique leader in a network and ensure all the other nodes are aware of the current leader and have a directed path to it. The difficulties of devising such an algorithm for a dynamic network come from the fact that nodes are in constant motion which leads to changes in the topology of the network. We are presented with an already existing algorithm for electing a leader in a dynamically changing network with asynchronous message passing, which assumes that the computing nodes in the network have perfect clocks. One of the most suitable applications for such an algorithm would definitely be in a mobile ad-hoc network (MANET) where the intrinsic behavior of the nodes is related to numerous changes in the topology of the network.
My first week of research was generally introductory. I was presented with the problem of choosing a leader in a dynamic network with asynchronous message passing and the open questions related to it. Because the actual topic of my research is related to relaxing the requirement that the nodes have perfect clocks, I first had to become familiar with the case where they do have perfect clocks. Thus, I spent most of the week understanding the already existing algorithm.
Having established a general understanding of the algorithm, I began researching topics related to perfect clocks and clock syncronization. Even from the beginning, there used to be two possible directions in which the research could proceed: either proving that the algorithm still works correctly without perfect clocks or disproving it. Therefore, the most important conclusion during that first week was choosing a direction to start. Fortunately, I was able to come up with a counterexample, showing that the algorithm does not work correctly in the case of non-perfect clocks. This gives us a good idea of what to expect next, that is, the algorithm definitely needs to be modified and proved to be correct for the case of nodes not having perfect clocks.
By the end of the first week and the beginning of the second, we came up with two possible solutions to the problem of electing a leader in an asynchronous dynamic network without perfect clocks:
Instead of trying to prove any of these solutions outright, we would first like to implement them in an already exsting simulator and get a general idea of their correctness. If in the course of those simulations we encounter a counterexample, this would mean that none of these solutions actually achieves the goal of relaxing the perfect clocks requirement.
Currently, the first solution has been implemented in the simulator and we are running simulations of the order of millions of repetitions in order to get a sense of the correnctness of the logical clocks solution.
June 11 was also the deadline for submitting a Research Plan
Having completed a successful simulation for five million repetitions during the second week, we had a good reason to think that the algorithm with logical clocks may be indeed correct and provide a solution to the problem of electing a leader in a dynamic network without perfect clocks. Therefore, during the third week, most of my efforts were geared towards completely understanding the existing proof and trying to find out places where it is no longer true when logical clocks are used instead of global time.
In this process, Dr. Welch and I had interesting discussions about the representation of time in the algorithm (whether it is better to use a discrete notion of time, or a continuous one). After deciding on the basic assumptions, I started modifying parts of the different properties and lemmas in the proof. For some parts, it was fairly easy to switch between the different representations of time. For others, however, it was necessary to restate a whole property and find an alternative proof for it. Moreover, for even trickier proofs, we consider even weakening the statement we need to prove, provided that the rest of the proofs do not require it to be as strong.
Week 4 & 5
During those two weeks, my main goal was to state and prove the basic properties of logical clocks that would replace the ones that use global time in the current algorithm. Even though the ideas behind logical clocks are really simple, it was challenging for me to concisely state them with respect to the variables of the leader-election algorithm. After restating the basic property a number of times and reviewing the proof repeatedly, we finally managed to come up with a property which not only captures all the properties of logical clocks, but can also be used in subsequent proofs the same way the previous property involving global time is used. By using that new property, we hope to reduce the number of changes to the rest of the proofs in the algorithm.
After completing this essential step of the proof, I started reading ahead and trying to make adjustments to subsequent proofs so that they work with our new property. It has been working out well - easier for some of the proofs and a little bit tricky for others.
Keeping up with the different properties and lemmas of the correctness proof was not going so smoothly during this week. We encountered a problem with one of the lemmas, due to the fact that it was relying on comparissons between global times. In the case of logical clocks, however, the situation is more complicated. If one event happened before another, we know that the value of the logical clock of the first one is less than the value of the second one. The reverse relationship, however, is not true. That is, if the value of one logical clock is less than another, we cannot infer anything about the causality of the events. With global time, on the other hand, it is always straightforward to determine the time-ordering of events. This main difference between the two concepts causes a problem in the proof of one of the basic lemmas. Hopefully, the possible solution we have in mind would work out and help us prove the same result for logical clocks, too.
During the seventh week, I was mainly preoccupied with the stability proof of the algorithm. Having finished the correctness proof and having dealt with all the previous difficulties I had with logical clocks, the only part to finish now was the stability proof. What this means is that, eventually, if we have a quiescent leader-oriented DAG, and only one link-down event occurs, no new leader will be elected in the connected component of the old leader. Using the previous stability proof turned out to be unsuccessful because it relies heavily on the concept of events being associated with a global time. We've been considering different approaches to the proof, but nothing has worked out yet. I'm hoping I can finish this last piece of the proof by the end of the program. It may be a hard task, though, considering all the deliverables and deadlines that are coming up in the next 3 weeks. During this week, I also finished the abstract for my paper.
I spent most of the time during this week working on the presentations that I am supposed to give next week. After discussing the slides with the various people around me, I finally managed to finish both presentations. The first one is a longer version, prepared for the weekly meetings that we have in the group. It is supposed to be a half-an-hour talk. The second presentation was targeted towards the other REU students and it was much shorter, about 10 minutes.
My two presentations were scheduled for Wednesday this week, so I spent most of the time before that practicing and giving some finishing touches to the slides. Wednesday was quite a busy day; I attended more than 7-8 presentations and gave 2 myself. I was pretty much satisfied with the way my presentations went, but there are still some details that have to be perfected for the poster presentations next week. I also worked on my poster during this week, and here is the final draft.
The final week of the program was probably the busiest of all, due to all the deadlines and events we had to attend. By Monday, all posters had to be submitted and printed in time for the poster session on Tuesday. I think the poster presentations went very well. I had the chance to meet students from other engineering programs, besides Computer Science.
Week 10 was also the deadline for the final papers, so here is the final version of my research paper.
Having two more days left, I'll probably put some final effort into resolving the last part of the stability proof of the algorithm and try to complete the project before I leave.
Parasol Home | Research | People | General info | Seminars | Resources
Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112
email@example.com Phone 979.458.0722 Fax 979.458.0718
Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU
Web Accessibility Policy and Law - Web Accessibility and Usability Standards - Contact Webmaster