%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  New template code for TAMU Theses and Dissertations starting Fall 2012.  
%  For more info about this template or the 
%  TAMU LaTeX User's Group, see http://www.howdy.me/.
%
%  Author: Wendy Lynn Turner 
%	 Version 1.0 
%  Last updated 8/5/2012
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                           SECTION VII
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\chapter{\uppercase{Conclusion: Summary and Future Work}}
\label{chap:conclusion}

In this section, we summarize our contributions and provide future work.

\section{Distributed Resource Allocation Algorithms for Static Networks}

We have provided two distributed resource allocation algorithms for static networks, specifically, two distributed algorithms that solve the dining philosophers problem with failure locality 1.  Since it is impossible to design any failure-locality-1 dining algorithm in asynchronous systems \cite{choy:lfids}, we utilized failure detectors to design our algorithms. 

\subsection{Dining with Bounded Waiting and Failure Locality 1}

In Section \ref{chap:dp-fair}, we provided the formal problem definition of perpetual strong exclusion with bounded waiting and failure locality 1 ($BW$-$\square SX$-$FL1$) and presented a message-passing algorithm that solves $BW$-$\square SX$-$FL1$ using the local version of the eventually perfect failure detector ($\Diamond P^1$).  

Our algorithm carefully combines the doorway technique presented in \cite{SP07} and the concept of skepticism in \cite{pike:dpwcl}.  The exclusion property is ensured by a fork/request protocol and the progress property is guaranteed by preventing each node $p$ from entering its doorway if their exists a neighboring node of $p$ that is already in its doorway.  The fairness property is ensured by blocking each node $p$ from entering its doorway if any neighbor $q$ of $p$, while continously trying to access its critical section,  gave permission to $p$ to enter its doorway more than a bounded number of times.

In addition to solving $BW$-$\square SX$-$FL1$, we provided the first step towards identifying a weakest failure detector for $BW$-$\square SX$-$FL1$ by implementing failure detector $\Diamond P^1$ using multiple instances of $BW$-$\square SX$-$FL1$.  

Our mutual reduction does not necessarily preserve the underlying conflict graph topology; the conflict graph topology considered in one direction of the reduction is not necessarily the same in the other direction.  For future work, we would like to identify the weakest failure detector $X$ for solving  $BW$-$\square SX$-$FL1$ by showing that $X$ and $BW$-$\square SX$-$FL1$ are mutually reducible to each other while preserving the underlying conflict graph topology.  In addition, we would like to identify weakest failure detectors for variations of the dining philosophers problem that consider failure locality 1.
  
\subsection{Stabilizing Dining with Failure Locality 1}

In Section \ref{chap:dp-stable}, we presented a solution for stabilizing (transient fault-tolerant) failure-locality-1 dining considering shared memory systems with regular registers.  We utilized the anonymous local eventually perfect failure detector ($?\Diamond P^1$) to obtain our results.  Our algorithm borrowed the concept of asynchronous doorways from \cite{choy:eftafd}, however, instead of implementing the doorway using a ping/ack protocol (as done in Section \ref{chap:dp-fair}), we implemented the doorways using stabilizing mutual exclusion subroutines.  We also used stabilizing mutual exclusion subroutines to handle fork activities instead of handling it with a fork/request protocol (as done in Section \ref{chap:dp-fair}).  The use of mutual exclusion subroutines makes our algorithm modular.

Notice, in Section \ref{chap:dp-stable}, we did not specify any $?\Diamond P^1$ implementation.  For future work, it will be interesting to seek for an implementation of $?\Diamond P^1$ on partially synchronous shared memory systems using regular registers.  In fact, finding an implementation of $\Diamond P^1$ will suffice since $\Diamond P^1$ implies $?\Diamond P^1$.  One idea would be to simulate the message passing protocol used for implementing $\Diamond P^1$ in \cite{beau:ftass, hutl:05:pimsfd} with read/write operations on shared regular registers.

Our algorithm has the following liveness guarantee: each correct hungry process $p$ that is at least two hops away from any crashed process eventually eats.  This property still allows a hungry neighbor of $p$ to overtake $p$ unboundedly many times in accessing the shared resource (the algorithm presented in Section \ref{chap:dp-stable} does not have a fairness property as in the algorithm in Section \ref{chap:dp-fair}).  An interesting future work would be to design a stabilizing failure-locality-1 dining algorithm that satisfies bounded waiting: the algorithm should guarantee that is a correct process $p$ only has correct neighbors, then eventually, for any interval in which $p$ is continuously hungry, no neighbor of $p$ eats more than a bounded number of times.

\section{Distributed Algorithms for Mobile Ad Hoc Networks}

We have provided three distributed algorithms for mobile ad hoc networks that can serve as building blocks in designing other useful applications.  Specifically, we have presented algorithms for (1) maintaining neighbor knowledge, (2) neighbor detection, and (3) leader election.

\subsection{Maintaining Neighbor Knowledge in a Road Network}

We have presented, in Section \ref{chap:nk}, a deterministic solution for nodes to maintain neighbor knowledge where nodes communicate via wireless broadcast and are restricted move on a two-dimensional road network.  Our solution includes geographical segmentation and constructing a deterministic collision-free broadcast schedule for nodes to exchange neighbor information  Considering our broadcast schedule, we have provided a lower bound on the speed of message propagation on a road network.  

We relaxed the density requirement and considered dynamic clusters on a road network.  We showed that, under a certain condition, neighbor knowledge is maintained when clusters move close to each other.  We discussed how we could obtain initial neighbor knowledge using the gossiping algorithm in \cite{GPPR07}.  We also presented practical values for the parameters that satisfy all constraints in Section \ref{chap:nk}; this indirectly shows that the assumptions and constraints in Section \ref{chap:nk} do not contradict each other.

Our definition of a road network does not contain any restriction on the intersecting angle between any two lines.  This makes our setting applicable to not only urban vehicular networks, where the network topology resembles a perfect grid network, but also suburban vehicular networks.

For future work, it will be interesting to seek for different broadcast schedules that are suitable on two-dimensional space and provide better lower bounds on the speed of message propagation.  Another topic for future work would be to provide a definition of two-dimensional cluster (recall that one-dimensional clusters were considered in Section \ref{chap:nk}) and see if neighbor knowledge can be maintained when two (or more) two-dimensional clusters merge. 

\subsection{Hello-based Neighbor Detection Using the Abstract MAC Layer}

In Section \ref{chap:nd}, we have presented a periodic hello-based neighbor detection algorithm that tolerates bounded clock drift using the abstract MAC layer \cite{Kuhn2011}.   The main challenges were to develop a handshaking mechanism between hello message broadcasts and application message broadcasts.  Our neighbor detection algorithm generated and broadcast hello messages at the right time by defining pre-hello intervals and blocking application messages to be sent to the abstract MAC layer during each of these intervals.  Our neighbor detection algorithm also guaranteed reliable point-to-point communication of application messages by taking into account the following time durations in becoming link up with a nearby node: (1) the time it takes to flush all of the message out of the $k$-bounded send buffer without any interference, (2) the sum of pre-hello intervals that appear during the course of flushing the $k$-bounded send buffer, and (3) the bounded message delay for each hello message that was broadcast during the course of flushing the $k$-bounded send buffer.

Our algorithm has an advantage of not requiring trajectory information (notice that trajectory functions are used in Section \ref{chap:nk}).  However, there is a trade-off in which the distance between two nodes must be somewhat closer than their communication radius for them to become link up with each other. 

For future work, it will be interesting to explore variations of hello message based approaches such as event-based hello (where upper layer messages affect the transmission time of the hello message) and adaptive hello (where hello messages are broadcast depending on the movement speed of a node) \cite{GS05} instead of periodic hello and compare their performance when used with the abstract MAC layer for neighbor detection. 

\subsection{Regional Consecutive Leader Election} 

In Section \ref{chap:rcle}, we formally stated the Regional Consecutive Leader Election (RCLE) problem and proved that any algorithm requires $\Omega(Dn)$ synchronous rounds for solving the RCLE problem in the worst case where $D$ is the bounded communication diameter and $n$ is the total number of nodes in the system.   Then, we presented and proved correct a fault-tolerant algorithm that solves the RCLE problem.  Our algorithm is proven to be asymptotically optimal with respect to the $\Omega(Dn)$ lower bound.  In addition, our algorithm solves the RCLE problem with a low message bit complexity per node per round compared to the previous work in \cite{CRW:10}.  We also introduced a novel condition on the mobility of nodes that ensures appropriate information propagation among the nodes in the region of interest.

By considering a fixed region, leader election is performed among nodes that are relatively close to each other.  This is an advantage over other leader election algorithms that consider an arbitrary network diameter.  Our system model in Section \ref{chap:rcle} allows nodes in the region to be temporarily partitioned.  This is an advantage over other leader election algorithms that require continuous connectivity.

As mentioned in Section \ref{chap:rcle}, our algorithm is crash fault-tolerant; periodic leader messages enables the detection of a crashed leader.  An important open question is how to deal with malicious nodes in our setting; what if a non-leader node generates leader messages to pretend that it is the leader?, what if a non-leader node pretends that it has entered the region the earliest to become the next leader?, etc.  

If nodes move in the region in accordance with our condition on mobility, then it is shown that a bounded communication diameter exists.  Future work on this topic involves exploring different mobility conditions that are restrictive enough to guarantee a bounded communication diameter while, on the other hand, being flexible enough for real world applications.
   