\documentstyle[fullpage,multicol]{article}
\parskip = 1em
\parindent = 0pt
\begin{document}
\begin{multicols}{2}
\begin{center}
{\Large Term Project Algorithm\\6.852}\\
{\large Jeremy Brown and Greg Hudson}
\end{center}

\section{General Description}

The problem here is to distribute an article a from a process i where
it is initially posted (via a $\mbox{post}_i$ input action) to all
other processes, preferably with a minimum of communication.  

A brute-force flooding algorithm would have each process which
receives a new article send it to each of its neighbors that hadn't
already sent it that article; as a result, the article would get sent
once over each edge in the network for a message compexity of $Eb_a$,
where $b_a$ is the number of bits in the article a.

In order to reduce the required message complexity, we introduce the
notion of an article unique identifier, a small token which identifies
an article.  An article identifier is composed of the unique
identifier of the process where the article is initially posted and a
sequence number for that process.  Since the sequence number increases
monotonically, no two articles will have the same message ID.  The
size of an article identifier is bounded by the maximum size of a
process identifier plus the logarithm of the largest number of
articles posted to any processor; in general, we assume that $b_u$,
the size of a UID, is literally more than two orders of magnitude
smaller than $b_a$, the size of an article.

Our algorith is, then, a modification of the flooding algorithm in
which, instead of sending an article directly to each neighbor, a
process first asks each neighbor whether it already has the article by
sending it the article's UID, and then sends the article to a neighbor
only if the neighbor responds that it does not yet have it.  As we
will see in the complexity analysis, this algorithm (which is used in
practice on Usenet) does not give us a better theoretical upper bound
on the message complexity, but does give us a much better best-case
and average-case behavior.  In our analysis, we will consider what
modifications or restrictions are necessary to provide a better
theoretical upper bound.

We have two contingencies for failures: first, if a process detects
that a message is dropped, it resends the message.  Second, if a
process stops and restarts, it resends the last message it sent to
each neighbor, since it might have missed a dropped event from the
channel.

\section{Formal Model}

An article is originated at an arbitrary server i by an input action
$post_i(a)$, where a is an article.

We assume that each server has a unique process identifier called a
PID.  We also define a separate unique identifier type UID as a pair
(PID, integer).  UIDs will be used to identify articles.  

\paragraph{Servers:}  

There are two well-formedness requirements for our model: First, no
$post_i$ should take place between a $stop_i$ event and a subsequent
$start_i$; this corresponds to the real-world fact that one cannot
post a message to a news server which has crashed until it has
recovered.  This requirement must be obeyed by users.  Second, no
$receive_{j,i}$ takes place after a $stop_i$ before a $start_i$ is
seen; this corresponds to the fact that a crashed server cannot
receive a message.  This requirement is actually enforced by the
channel model; we mention it here for completeness.

The message alphabet M used by servers and channels consists of UIDs,
and (UID, article), ($accept$, UID), ($reject$, UID), and ($ack$, UID)
pairs.

\begin{tabbing}

In\=puts:\\
  \>$post_i(a)$:\= a an article; represents a user posting a\\
		\>\> new message.\\
  \>$stop_i$: stops the process entirely.  \\
  \>$start_i$:\= starts the process from wherever it was\\ 
	   \>\>last stopped; no state is lost.\\
  \>Fo\=r each neighbor $k$:\\
  \>\>$receive_{k,i}(m)$: \= $m$ in M, a message being\\
	\>\>\> delivered from neighbor k\\
  \>\>$dropped_{i,k}(m)$: \= $m$ in M, represents m failing\\
	\>\>\> to be delivered to k\\
\\  
Outputs:\\
  \>fo\=r each neighbor $k$:\\
  \>\>$send_{i,k}(m)$: $m$ in M\\
\\
Internal:\\
  \>for each neighbor $k$:\\
  \>\>$migrate_{i,k}(u)$: $u$ a UID\\
\end{tabbing}


\begin{tabbing}
{\bf State:}\\
ab\= \kill
$p$, a PID, initially process i's PID\\
$seqno$, an integer, initially 0\\
$stopped$, a boolean, initially false\\
$dbase$, \= a set of pairs \{(u,a)| u is a uid, a is an \\
	\>article\}, initially empty\\

for each neighbor $j$:\\
  \>$sendqueue_j$, \= a queue of messages in M,\\
	\>\> initially empty.\\
  \>$\mbox{\it offerpending}_j$, \= a message in M or $null$,\\
	\>\> initially $null$\\
  \>$\mbox{\it replypending}_j$, \= a message in M or $null$,\\
	\>\> initially $null$\\
  \>$new_j$, a set of UIDs, initially empty.\\

\end{tabbing}

\begin{tabbing}
ab\= \kill
{\bf Transitions:}\\
$post_i(a)$:\\
  \>Ef\=fect:\\
        \>\>Let $u = (i, seqno)$\\
	\>\>$seqno := seqno + 1$\\
 	\>\>$dbase := dbase \cup (u,a)$\\
	\>\>add $u$ to $new_j$ for all neighbors j\\

$stop_i$:\\
  \>Effect:\\
	\>\>$stopped := true$\\

$start_i$:\\
  \>Effect:\\
	\>\>$stopped := false$\\
	\>\>for \= all $j \in nbrs$\\
	\>\>\> if \= $\mbox{\it offerpending}_j \neq null$ and\\
	\>\>\>\> ab\=\kill
	\>\>\>\>\> $\mbox{\it offerpending}_j$ is not in $sendqueue_j$\\
	\>\>\>\> add $\mbox{\it offerpending}_j$ to end of $sendqueue_j$\\
	\>\>\> if \= $\mbox{\it replypending}_j \neq null$ and\\
	\>\>\>\> ab\=\kill
	\>\>\>\>\> $\mbox{\it replypending}_j$ is not in $sendqueue_j$\\
	\>\>\>\> add $\mbox{\it replypending}_j$ to end of $sendqueue_j$\\

$receive_{j,i}(m)$:\\
  \>Effect:\\
	\>\>if \= ($m = (u,a)$) then\\
	\>\>\> if \= $(u,a) \not \in dbase$\\
	\>\>\>\> $dbase := dbase \cup (u,a)$\\
	\>\>\>\> add $u$ to $new_j$ for all neighbors j\\
	\>\>\> add $(ack,u)$ to end of $sendqueue_j$\\
	\>\>\> $\mbox{\it replypending}_j := (ack,u)$\\
	\>\>if ($m = u$)\\
	\>\>\> if \= there exists an $a$ such that $(u,a) \in dbase$\\
	\>\>\>\> add $(reject,u)$ to end of $sendqueue_j$\\
	\>\>\>\> $\mbox{\it replypending}_j := (reject,u)$\\
	\>\>\> else\\
	\>\>\>\> add $(accept,u)$ to end of $sendqueue_j$\\
	\>\>\>\> $\mbox{\it replypending}_j := (accept,u)$\\
	\>\>if $m = (reject,u)$ and $\mbox{\it offerpending}_j = u$\\
	\>\>\> $\mbox{\it offerpending}_j := null$\\
  	\>\>if $m = (accept,u)$ and $\mbox{\it offerpending}_j = u$\\
	\>\>\> if \= there exists an $a$ such that $(u,a) \in dbase$\\
	\>\>\>\> add $(u,a)$ to end of $sendqueue_j$\\
	\>\>\>\> $\mbox{\it offerpending}_j := (u,a)$\\
	\>\>if $m = (ack,u)$ and $\mbox{\it offerpending}_j = (u,a)$\\
	\>\>\> $\mbox{\it offerpending}_j := null$\\

$send_{i,j}(m)$: \\
  \>Precondition:\\
	\>\> $stopped = false$\\
	\>\> $m$ is the first message in $sendqueue_j$\\
  \>Ef\=fect:\\
	\>\>remove $m$ from $sendqueue_j$\\

$migrate_{i,j}(u)$: \\
  \>Precondition:\\
	\>\> $stopped = false$\\
	\>\> $\mbox{\it offerpending}_j = null$\\
	\>\> $u$ in $new_j$\\
  \>Ef\=fect:\\
	\>\>remove $u$ from $new_j$\\
	\>\>add $u$ to end of $sendqueue_j$\\
	\>\>$\mbox{\it offerpending}_j := u$\\

$dropped_{i,j}(m)$: m in M\\
  \>Effect:\\
	\>\>if $stopped = false$ then\\
	\>\>\> add $m$ to end of $sendqueue_j$\\

\end{tabbing}

\begin{tabbing}
${\bf Tasks}$:\\
ab\= \kill
For each neighbor j:\\
\>\{$migrate_{i,j}(u)$\}\\
\>\{$send_{i,j}(u)$\}\\
\end{tabbing}

For purposes of algorithm analysis, we assume that a server task is
guaranteed to get a chance to act in at most time $d_h$; we also
assume that it completes {\em at most} one task in time $d_l$.

Some explanation: $post, stop, start,$ and $send$ are all fairly
straightforward.  $dropped$ just resends any message that fails to be
delivered.  $receive_{j,i}$ is where most of the interesting work gets done,
with some assistance from $migrate_i$.

The idea behind $receive_{j,i}$ and $migrate_{j,i}$ is that for a
given neighbor j, process i only offers one potentially new article at
a time.  So, a new article is offered to j in the form of its
associated UID; j either accepts or rejects the article.  If the
article is rejected, i can try again with another potentially new
article; if the article is accepted, i sends the entire article to j,
then waits to receive an ack before trying another new article.

$\mbox{\it offerpending}_j$ and $\mbox{\it replypending}_j$ keep track
of the last offered and replied-to message $i$ sent to $j$.
$\mbox{\it offerpending}_j$ is only cleared by rejections or acks, and
$\mbox{\it replypending}_j$ is only changed by a new reply (and
process $j$ would not have sent a new message to be replied to unless
it had already received the previous reply).  If $i$ stops and
restarts, it will resend the messages in $\mbox{\it offerpending}$ and
$\mbox{\it replypending}$ to each neighbor, avoiding any potential
problems arising from messages to its neighbors having possibly gotten
dropped while $i$ was stopped.

\end{multicols}
\end{document}
