%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  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 I
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\pagestyle{plain} % No headers, just page numbers
\pagenumbering{arabic} % Arabic numerals
\setcounter{page}{1}

\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\raTrans}{\overset{*}{\ra}}
\newcommand{\prop}{\rightsquigarrow}
\newcommand{\Rcover}{R_\text{cover}}
\newcommand{\msg}[1]{\langle#1\rangle}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\falsum}{\perp}
\newcommand{\func}[1]{\text{\textup{\texttt{#1}}}}
\newcommand{\Location}{\func{Location}}
\newcommand{\differ}{\func{differ}}
\newcommand{\oldMessage}{\func{oldMessage}}
\newcommand{\Round}{\text{Round}}
\newcommand{\EnteredSinceEndOfLastRound}{\func{EnteredSinceLastRound}}
\newcommand{\stopAllTimers}{\func{stopAllTimers}}
\newcommand{\startInstance}{\func{startInstance}}
\newcommand{\startTimer}{\func{startTimer}}
\newcommand{\running}{\func{running}}
\newcommand{\disposeOldMessages}{\func{disposeOldMessages}}
\newcommand{\update}{\func{incTimeStamps}}
\newcommand{\expired}{\text{expired}}
\newcommand{\recvBuf}{recBu\!f}
\newcommand{\leaderT}{{leaderT}}
\newcommand{\electT}{{electT}}
\newcommand{\waitT}{{waitT}}
\newcommand{\roundsLeft}{roundsLe\!ft}
\newcommand{\msgBuf}{msgBu\!f}
\newcommand{\Link}{\text{Link}}
\newcommand{\Env}{\text{Env}}
\newcommand{\true}{\textsc{true}}
\newcommand{\false}{\textsc{false}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\nullMsg}{nullM\!sg}

\newconstruct{\PROC}{\textbf{procedure}}{}{\ENDPROC}{\textbf{end procedure}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{observation}[theorem]{Observation}


\chapter{\uppercase {Introduction}}

A distributed system is a collection of computing entities that communicate with each other to solve some problem.  Distributed systems impact almost every aspect of daily life (e.g., cellular networks and the Internet); however, it is hard to develop services on top of distributed systems due to the unreliable nature of computing entities and communication; node and link failures might occur due to hardware deterioration and message transmissions might be delayed due to message collisions and interference.  As handheld devices with wireless communication capabilities become increasingly popular, the task of providing services becomes even more challenging since dynamics, such as mobility, may cause the network topology to change frequently.  One way to ease this task is to develop collections of \emph{information infrastructures} which can serve as building blocks to design more complicated services and can be analyzed independently.

%A distributed system (or network) is a collection of computing entities (or nodes, or processes) where each computing entity can communicate with each other by establishing wired or wireless communication links.  We can easily find distributed systems that we use everyday (e.g., cellular networks and the Internet), however, it is still hard to develop useful services on top of distributed systems due to the unreliable nature of computing entities and communication links; node and link failures might occur due to hardware deterioration and message transmissions might get delayed due to message collisions and interference. In addition, as handheld devices with wireless communication capabilities are becoming more popular these days, the task of providing useful services on distributed systems becomes more challenging since dynamics, such as mobility, may cause the network topology to change frequently.   One way to provided useful services in this challenging environment is to have collections of \emph{information infrastructures} which can serve as building blocks to design more complicated services.

%In this dissertation, we focus on providing \emph{information infrastructures} that can serve as building blocks to help solve interesting and important problems, and provide useful services in distributed systems.  

This dissertation is divided into two parts based on the dynamicity of the system. The first part presents information infrastructures for static networks and second part presents information infrastructures for mobile ad hoc networks --- networks in which nodes are mobile and no fixed physical infrastructures, such as base stations, exist.  

In the remainder of this section, we discuss the motivation, research goal, and the novelty of the information infrastructures considered in this dissertation.  We also provide the organization of this dissertation.

\section{Motivation and Research Goal}

Our goal is to provide useful information infrastructures that serve as building blocks for other problems to utilize.  In particular, we consider the the following information infrastructures in this dissertation:
\begin{compactitem}
\item Dining philosophers (generalized mutual exclusion),
\item Maintaining neighbor knowledge,
\item Neighbor detection, and
\item Leader election.
\end{compactitem}

We consider the dining philosophers problem in a network where nodes are static.  Maintaining neighbor knowledge, neighbor detection, and leader election are considered in a mobile ad hoc environment.
%We consider leader election, maintaining neighbor knowledge, and neighbor detection in a mobile ad hoc environment.% where nodes are mobile and there is no fixed infrastructure, such as base stations, in the network.  
%The dining philosophers problem is considered in a network where nodes are static.

An algorithm that solves the dining philosophers problem can be utilized when there is a need to prevent multiple nodes from accessing some shared resource simultaneously.  Services such as neighbor detection and maintaining neighbor knowledge can serve as building blocks for applications that require point-to-point communication.  A solution to the leader election problem can be used whenever there is a need for a unique coordinator in the system to perform a special task.  

We examine each information infrastructure in more detail in the remainder of this section.

\subsection{Fault-Tolerant Dining Philosophers}
\label{sec:intro:ftdp}

The dining philosophers problem \cite{dijk:71:hosp, Lynch80}, or simply dining, is a distributed resource allocation problem, in which each node repeatedly needs simultaneous exclusive access to a set of shared resources in order to enter a special part of its code, called the critical section.  The sharing pattern is described by an arbitrary ``conflict'' graph, each edge of which represents a resource shared by the two nodes corresponding to the endpoints of the edge.  

In large scale and long-lived systems, the likelihood of some node failing at some point is high, thus sparking interest in fault-tolerant versions of the dining problem.  The ideal case would be for the dining algorithm to isolate each crashed node such that it does not impact any other correct nodes in the system.  If the ideal case is impossible to achieve, restricting the impact of the crash failure to a local neighborhood would still be desirable.  \emph{Failure locality} \cite{choy:eftafd, choy:lfids} is a metric that realizes this concept; it is the maximum distance in the conflict graph between a crashed node $p$ and any other node that is blocked from entering its critical section.

In this dissertation, we provide two problem definitions that extend the classical dining philosophers problem in asynchronous systems --- systems in which no bounds on message delivery time and relative process speed exist.  The first problem definition considers failure locality 1 and fairness in accessing shared resources in an asynchronous message passing model.  The second definition also considers failure locality 1, however, instead of fairness, it considers the presence of transient failures (unexpected corruptions to the system state) in an asynchronous shared memory model.
%\begin{compactitem}
%\item the dining philosophers problem that considers both failure locality 1 and fairness in accessing shared resources in an asynchronous message passing model, and
%\item the dining philosophers problem that considers both failure locality 1 and the presence of transient failures (unexpected corruptions to the system state) in an asynchronous shared memory %model. 
%\end{compactitem}
In the asynchronous message passing model, nodes communicate by sending and receiving messages through communication links.  However, in the asynchronous shared memory model, nodes communicate via performing read/write operations on shared memory objects.

We also present two novel distributed algorithms, each algorithm solving each one of the above mentioned problems.  Each of the two algorithms is the first algorithm for its corresponding problem.   

Choy and Singh \cite{choy:lfids} showed that any dining algorithm implemented on an asynchronous system must have failure locality at least 2.
To circumvent this lowerbound, our algorithms utilize failure detectors --- system services that provide some information about crash failures in the system --- to achieve failure locality 1.  The failure detectors that we use are at most as powerful as the ones that are used to solve failure-locality-0 dining \cite{SP07,SPS07,PSS08,SSW09}; we are trading off failure locality to use failure detectors that seemingly provide less information regarding crash failures in the system.    

%we provide two dining algorithms that achieve failure locality 1 on asynchronous systems --- systems in which no bounds on message delivery time and relative process speed exist.  The first algorithm considers an asynchronous message passing model while the second one considers an asynchronous shared memory model.  In the asynchronous message passing model, nodes communicate by sending and receiving messages through communication links.  However, in the asynchronous shared memory model, nodes communicate via performing read/write operations on shared memory objects.  In addition to crash fault-tolerance, the first algorithm provides fairness in accessing shared resources and the second algorithm tolerates transient failures (unexpected corruptions to the system state).

%Choy and Singh \cite{choy:lfids} showed that any dining algorithm implemented on an asynchronous system must have failure locality at least 2.
%To circumvent this lowerbound, our algorithms utilize failure detectors --- system services that provide some information about crash failures in the system --- to achieve failure locality 1.  The failure detectors that we use are as most as powerful as the ones that are used to solve failure-locality-0 dining \cite{SP07,SPS07,PSS08,SSW09}; we are trading off failure locality to use failure detectors that seemingly provide less information regarding crash failures in the system.     

Considering the message passing model, we also provide a reduction such that given a crash fault-tolerant solution to our dining philosophers problem, we implement the failure detector that we have utilized to solve our dining philosophers problem.  This reduction serves as the first step towards identifying the minimum information regarding crash failures that is required to solve the dining philosophers problem at hand.

%Considering the message passing model, we also provide a reduction such that given any solution to failure-locality-1 dining with fairness, we implement the failure detector that was originally used to solve failure-locality-1 dining with fairness.  This reduction serves as the first step towards identifying the minimum information regarding crash failures that is required to solve the dining philosophers problem at hand.

%\subsubsection{Dining with Failure Locality 1 in Message Passing Systems}

%\subsubsection{Stabilizing Dining with Failure Locality 1 in Shared Memory Systems}

\subsection{Maintaining Neighbor Knowledge and Neighbor Detection}

In wireless ad hoc networks, a fundamental problem for a node is to keep track of its set of nearby nodes (neighbors).  In this case, the challenge is to deal with wireless broadcast interference and collisions.  Difficulties are added when nodes are mobile since frequent change of network topology requires the process of identifying nearby neighbors to be ongoing.  This problem of identifying nearby nodes serves as a basis of distributed primitives such as routing (\cite{PC97,RRPSS03}), location services (\cite{ADM04}), and distributed token circulation (\cite{MCVW05}).  

In this dissertation, we present two solutions to the problem of identifying nearby nodes.  Each of the two solutions is the first solution for its corresponding system model.

\subsubsection{Maintaining Neighbor Knowledge in Road Networks}

Assuming that, initially, each node knows its neighbors, we consider the problem of maintaining neighbor knowledge where node mobility is restricted to a two-dimensional road network.  A road network is a collection of one-dimensional lines that may intersect each other.  We can view vehicular ad hoc networks as nodes (vehicles) with wireless communication capabilities moving on a road network.
%A reasonable application of nodes moving on a road network would be vehicular ad hoc networks.

For nodes to exchange neighbor information, we construct a deterministic collision-free broadcast schedule which utilizes time division multiplexing and geographical segmentation.  Under certain constraints, our broadcast schedule tolerates node movement on the road network while providing deterministic guarantees for each node to maintain its dynamically changing set of neighbors. 
%By setting up a specific broadcast schedule and sufficient constraints on the structure of the road network and node mobility, we show that nodes learn about each other before they become too close to each other.  In this way, nodes can maintain its dynamically changing set of nearby nodes.

We also provide a bound on how fast messages can travel in the road network given our broadcast schedule.  If nodes broadcast timestamped messages periodically, then this bound is particularly useful when some node $p$ needs to estimate the distance between itself and another node $q$ on the road network: when node $p$ receives a message $m$ from $q$ at time $t$, it can calculate an upper bound on the distance between itself and $q$ using time $t$, the timestamp value in $m$, message broadcast period, and the bound on speed of message propagation.

Considering vehicular networks, we often observe that vehicles move in clusters (due to, for instance, traffic lights).  To this matter, we consider grouping nodes on the road network into clusters and show that, under certain conditions, neighbor knowledge is maintained when two different clusters move close to each other.

Our solution is an extension of the one-dimensional case in \cite{ESW06} and \cite{S06} to two-dimensional space.  One might think that extending the results in \cite{ESW06} and \cite{S06} would be trivial since a road network is a collection of straight lines.  However, since we consider that the segmentation of each individual line is independent from each other and there is no restriction on where lines intersect, providing analysis with respect to intersection points becomes non-trivial.  We perform a rigorous case-by-case analysis whenever there is a need to consider intersection points in our analysis. 

The material regarding maintaining neighbor knowledge in road networks has been published in \cite{CVW12}.

\subsubsection{Neighbor Detection in Mobile Ad Hoc Networks}

Discovering neighboring nodes in mobile ad hoc networks becomes fully meaningful when nodes identify neighbors that they can actually communicate with.  We provide a solution where, for any given node $p$, nodes that are identified as neighbors of $p$ can perform reliable point-to-point communication with $p$.

We build our solution on top of the abstract MAC layer \cite{Kuhn2011} which handles the scheduling of wireless transmissions (collision detection and contention management) and provides message delay bounds for our solution to utilize.  In this way, we can focus on the algorithmic aspects of our solution without dealing with the scheduling of wireless transmissions.

Our solution is based on nodes generating periodic hello messages where each hello message contains sufficient information to help nodes to identify neighbors with which they can communicate in a point-to-point manner.  To make the problem more suitable for a wider variety of situations, we consider clocks with bounded drift rates.

To the best of our knowledge, our solution and the algorithm in \cite{Cornejo2012} are the only neighbor detection algorithms that consider the use of the abstract MAC layer.  The neighbor detection algorithm in \cite{Cornejo2012} relies on geographical segmentation and each mobile node to have future knowledge on joining or leaving a geographical segment.  However, our solution does not rely on geographical segmentation and does not require mobile nodes to know their future whereabouts.   

\subsection{Leader Election in Mobile Ad Hoc Networks}  

Leader election is a process of identifying a unique existing node in the system.  In this dissertation, we consider the problem of electing a leader within a fixed region where (1) nodes are mobile, (2) nodes communicate via wireless broadcast, and (3) clocks are synchronized.  The advantage of considering a region is that leader election can be performed by nodes that are relatively close to each other.  If we consider performing leader election among nodes that are connected but far apart from each other, the amount of time that it takes to elect a leader and knowing which node became the leader can be significant.

We assume that a message broadcast in the region is relayed through at most a fixed number of hops to nodes that stayed in the region for a sufficiently long period of time (in this case, we say that the region has a bounded communication diameter).  By having this assumption, any pair of mobile nodes in the region are not required to be connected at all times (network partitions are allowed within the region) which is a better fit for mobile ad hoc networks

We provide a novel problem definition, called the Regional Consecutive Leader Election (RCLE) problem, by extending the classical leader election problem to the ever changing environment of mobile ad hoc networks.

We prove that any algorithm in our model requires $\Omega(Dn)$ synchronous rounds to solve the RCLE problem, where $D$ is the communication diameter of the network and $n$ is the total number of nodes.  We then present the first asymptotically optimal fault-tolerant RCLE algorithm that elects a new leader whenever no leader is present in the region and there exists at least  one node in the region.  Since our leader election algorithm assumes that the region has a bounded communication diameter, the question arises how to ensure that the region has a bounded communication diameter?  To answer this question, we provide a novel condition on node mobility that ensures the existence of a bounded communication diameter within the region.

The material regarding regional consecutive leader election has been published in \cite{Chung10, CRW:10, CRW:11}.

%\section{Research Goal}

\begin{figure}[th]
\centering
\includegraphics[scale=0.9]{figures/organization.pdf}
\caption{Dissertation organization: Sections \ref{chap:dp-fair} to \ref{chap:conclusion}.}
\label{fig:intro:organization}
\end{figure}

\section{Organization}

Figure \ref{fig:intro:organization} shows how the remaining sections are organized. The first part of this dissertation considers distributed resource allocation algorithms for static networks and it consists of Sections \ref{chap:dp-fair} and \ref{chap:dp-stable}.   Sections \ref{chap:rcle}, \ref{chap:nk}, and \ref{chap:nd} constitutes the second part in which distributed algorithms for mobile ad hoc networks are dealt with.    The outline of each section is as follows:

The dining philosophers problem with crash fault-tolerance and fairness in accessing the shared resource for message passing is considered in Section \ref{chap:dp-fair}.  The system model and problem specification are given in Section \ref{sec:fl1dining:sysmodel}.  Utilizing a certain failure detector, a dining algorithm with failure locality 1 and fairness along with its proof of correctness is presented in Section \ref{sec:fl1dining:solveproblem}.  In Section \ref{sec:fl1dining:ExtractB}, we implement and prove correct the failure detector that was originally used to solve our dining problem.  Section \ref{sec:fl1dining:discuss} discusses how our result relates to other variations of dining problems and failure detectors.

Section \ref{chap:dp-stable} considers both crash and transient fault-tolerant dining for shared memory systems.  Background and related work is provided in Section \ref{sec:fl1stable:related}.  The system model and problem specification is provided in Section \ref{sec:fl1stable:sysmodel}.  Again, utilizing failure detectors, a transient fault-tolerant failure-locality-1 dining algorithm is presented in Section \ref{sec:fl1stable:ada-ss-fl1-dining}.  The correctness proof of our dining algorithm is also included in Section \ref{sec:fl1stable:ada-ss-fl1-dining}.

Maintaining neighbor knowledge of mobile nodes in a road network is considered in Section \ref{chap:nk}.  Related work and the system model are presented in Sections \ref{sec:nk:related} and \ref{sec:nk:sysmodel}, respectively.  In Section \ref{sec:nk:schedule}, a deterministic collision-free broadcast schedule is presented.  Section \ref{sec:nk:constraints} explains how the parameters used in Section \ref{chap:nk} relate to one another and then we show, in Section \ref{sec:nk:maintainNeighborKnowledge}, that neighbor knowledge is maintained throughout the execution of our broadcast schedule under the assumption that initial neighbor knowledge is given.  Given any two points $A$ and $B$ on the road network, a lower bound on the speed of message propagation from $A$ to $B$ is obtained in Section \ref{sec:nk:speed}.  In Section \ref{sec:nk:cluster}, we define clusters on the road network and show that, under certain conditions, neighbor knowledge is maintained when two clusters merge to form a new cluster.  Section \ref{sec:nk:discuss} discusses how initial neighbor knowledge can be obtained and presents practical values for the parameters.

Section \ref{chap:nd} considers the problem of each mobile node detecting neighboring mobile nodes with which it can perform reliable point-to-point communication.  Related work is presented in \ref{sec:nd:related}.  The system model is given in Section \ref{sec:nd:sysmodel} and the problem specification is described in Section \ref{sec:nd:probspec}.  Section \ref{sec:nd:algorithm} presents a periodic hello-based neighbor detection algorithm and its proof of correctness is given in Section \ref{sec:nd:proofCorrect}. In Section \ref{sec:nd:discussion}, we apply parameter values to obtain the maximum distance between any two nodes that guarantees them to perform reliable point-to-point communication and compare the results of different parameter values.

Section \ref{chap:rcle} considers a problem of electing a leader among mobile nodes within a fixed region, called Regional Consecutive Leader Election (RCLE).  In Section \ref{sec:rcle:related}, we present related work that deals with leader election on mobile ad hoc networks.  The system model and the RCLE problem definition is given in Section \ref{sec:rcle:sysmodel}.  We provide, in Section \ref{sec:rcle:lowerbound}, a lower bound on the time it takes to elect a leader and subsequently, in Section \ref{sec:rcle:algorithm}, we provide and prove correct an asymptotically optimal RCLE algorithm.  A condition on mobility, which guarantees the existence of a bounded communication diameter, is presented in Section \ref{sec:rcle:mobility}. 
  
Finally, Section \ref{chap:conclusion} concludes this dissertation by summarizing contributions and providing future work. 


%\section{This is a Very Long Section Title This is a Very Long Section Title This is a Very Long Section Title }

%A landscape figure should be shown below. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{sidewaysfigure}[H]
%\centering
%\includegraphics[scale=.50]{figures/Penguins.jpg}
%\caption{TAMU figure - This is an example of a long figure title with a landscape figure.  Figure titles need to be single-spaced within and double spaced between in the list of figures.}
%\label{fig:tamu-fig1-1}
%\end{sidewaysfigure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%More text here goes here.


%Lorem ipsum dolor sit amet, consectetur adipiscing elit. Morbi augue urna, varius quis facilisis ac, imperdiet et nunc. Vestibulum ante ipsum primis in faucibus. 

%\section{Testing the Top of the Page}
%Maecenas accumsan lobortis dui fringilla suscipit. Quisque congue fringilla dui, sed eleifend sapien fringilla euismod. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Maecenas venenatis posuere magna quis tempus. Cras at leo massa, eu ultricies tellus. Nunc nec dictum augue. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Phasellus purus felis, mollis id scelerisque in, viverra in elit. Nulla iaculis ultrices justo, ac pharetra nisl rhoncus pulvinar. Duis vitae mauris velit, in congue massa.

%Donec lectus orci, bibendum ut blandit dignissim, molestie non eros. Praesent aliquet feugiat dignissim. Morbi porttitor sollicitudin nisl, non mollis quam ultrices sit amet. Cras feugiat lacinia diam ut convallis. Nam nec varius ante. Nunc a ultrices felis. Quisque luctus sapien et ligula ornare quis consequat urna aliquet. Vestibulum vulputate lorem a tellus auctor id commodo risus sodales. Suspendisse quis tortor a felis molestie laoreet ut a nunc. Donec gravida sapien eget mauris condimentum lacinia. Proin eu purus libero. Nullam augue mi, vestibulum in convallis eu, adipiscing ac arcu. Donec nisi libero, egestas et molestie in, mollis quis ipsum. Sed gravida quam sit amet ante tempus rutrum non in mi. Cras viverra facilisis eros, id vestibulum sapien malesuada eget. Maecenas imperdiet luctus nisi vitae suscipit.



%Aliquam erat volutpat. Integer ut mauris elit. Nam et lectus vel neque vehicula commodo. Integer at risus ligula. Fusce mollis mauris sed lorem aliquam bibendum porttitor tellus blandit. Curabitur enim nibh, accumsan eu elementum id, rutrum a ipsum. Vivamus ultricies, elit id ornare iaculis, metus justo posuere quam, sit amet bibendum arcu dolor a eros. Sed in nisl nibh. Aenean egestas est ut tortor volutpat vehicula. Maecenas aliquet placerat nunc hendrerit dictum. In et nisi massa. Pellentesque luctus, sapien quis dignissim vulputate, sapien libero bibendum velit, vitae auctor ipsum nulla at augue. Nulla ac eros vitae tortor elementum vehicula.

%Morbi tristique egestas placerat. Cras faucibus eleifend porta. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Ut a pellentesque neque. Donec sollicitudin metus varius nulla egestas laoreet. Duis non mauris ut nunc adipiscing volutpat. Nam vitae est sed turpis tristique varius. 

%\subsection{This is a Very Long Subsection Title This is a Very Long Subsection Title}

%More text
%\subsection{Subsection}

%Subsection text

%\section{Another Section}

%Section text
