path: root/doc/design.tex

\documentclass{article}
\usepackage[backend=biber]{biblatex}
\usepackage{listings}
\usepackage{xcolor}

\definecolor{bgcolor}{rgb}{0.97, 0.97, 0.95}

\lstdefinestyle{lststyle}{
	backgroundcolor=\color{bgcolor},
	tabsize=2,
}
\lstset{style=lststyle}
\lstset{language=C}

\title{Software-Failure-Tolerant and Highly-Available Design of the Distributed Emergency Response Management System}

\addbibresource{references.bib}

\author{}

\begin{document}

\maketitle

\begin{center}
\begin{tabular}{l l l}
	\textbf{Name} & \textbf{Student ID} & \textbf{Module} \\ \hline\hline
	Shaza Ahmed & TODO & TODO \\ \hline
	Sam Anthony & 40271987 & Sequencer \\ \hline
	Bence Matajsz & TODO & Testing \\ \hline
	Vijaykumar Patel & TODO & Front end \\ \hline
\end{tabular}
\end{center}


\section{Introduction}

TODO


\section{Architecture}

TODO

\section{Front end}

TODO


\section{Replica manager}

TODO


\section{Sequencer}

The purpose of the sequencer is to ensure that requests are delivered to all of the replicas in the same (total) order.
This ensures sequential consistency of the system because all replicas perform the same computations in the same order.

\paragraph{}

The FE delivers requests to the RMs via \emph{totally ordered reliable multicast}.
When the FE receives a request from a client, it sends the request to the multicast group.
All of the RMs, as well as the sequencer, are members of the group, so they receive the request.

When a RM receives a request, it does not deliver it to the replica immediately.
Rather, it adds the message to a \emph{holdback queue} and waits to receive an \emph{order message} from the sequencer.

The sequencer is also a member of the multicast group, but it has a special function.
When it receives a message, it multicasts an \emph{order message} containing the ID of the message it has just received.

When a RM receives an order message, it inspects the ID attached to it and removes the associated message from the holdback queue and delivers it to the replica.

\paragraph{}

The FE and RMs need not be aware of any of this behavior because it is encapsulated in the totally-ordered reliable multicast class.
As far as the FE knows, it is just ``sending a request to all of the RMs."
And from the perspective of an RM, it is just ``receiving a request from the FE."
They can be sure that they are reliably sending and receiving requests in the proper order, without worrying about the implementation details, or even knowing of the existence of the sequencer.

\paragraph{}

The totally ordered multicast protocol is built on top of a reliable multicast mechanism---an implementation of the Trans Protocol, ``[which] uses a combination of positive and negative acknowledgement strategies to achieve efficient reliable broadcast or multicast communication" \cite{melliar-smith-trans}.

\paragraph{}

\textbf{Sequencer pseudocode:}
\begin{lstlisting}
type dataMsg struct {
	id int
	data
}

type orderMsg struct {
	id int
	seq int
}

class groupMember {
	seq := 0
	holdback := new Queue[dataMsg]
	deliver := new Queue[dataMsg]
	rMulticast := new Trans

	multicast(m dataMsg) {
		rMulticast.send(m)
	}

	on rMulticast.recv(m dataMsg) {
		holdback.enqueue(m)
	}

	on rMulticast.recv(m orderMsg) {
		wait until m.id in holdback && seq == m.seq
		data := delete(m.id, holdback)
		deliver.enqueue(data)
		seq++
	}
}

// Sequencer is also a member of the multicast group.
class sequencer {
	seq := 0
	rMulticast := new  Trans

	on rMulticast.recv(m dataMsg) {
		order := orderMsg{m.id, seq}
		rMulticast.send(order)
		seq++
	}
}
\end{lstlisting}

\textbf{Reliable multicast (Trans) pseudocode:}
\begin{lstlisting}
// message
type m struct {
	id mid
	sender pid
	seq int // sequence number
	positiveAcks []mid
	negativeAcks []mid
	data
}

type mid "message ID"
type pid "process ID"

var (
	positiveAcks []mid
	negativeAcks []mid
	received []m
	retransmissions []mid
	lastSend time
)

send(m) {
	pkt := (m, positiveAcks, negativeAcks)
	multicast(pkt)
	positiveAcks = []
	go timeout(m)
	lastSend = now()
}

timeout(m) {
	sleep until timeout

	if m not in positiveAcks {
		insert(m, retransmissions)
	}
}

recv(m) {
	insert(m.id, positiveAcks)
	insert(m, received)

	if m.id in negativeAcks {
		delete(m.id, negativeAcks)
	}
	if m.id in retransmissions {
		delete(m.id, retransmissions
	}

	for each mid in m.positiveAcks {
		delete(mid, positiveAcks)
		if mid not in received {
			insert(mid, negativeAcks)
		}
	}

	for each mid in m.negativeAcks {
		if mid in received {
			insert(mid, retransmissions)
		} else {
			insert(mid, negativeAcks)
		}
	}

	acks := union(positiveAcks, negativeAcks)
	for each ack in acks s.t.
			sender(ack) == sender(m)
			&& m.seq > ack.seq+1 {
		insert(m.id, negativeAcks)
	}
}

retransmit() {
	forever {
		wait until
			timeSince(lastSend) > threshold
			&& len(retransmissions) > 0

		mid := pop(retransmissions)
		m := received[mid]
		send(m)
	}
}

// Observable Predicate for Delivery.
// The process that broadcast c has received and acked
// message a at the time of broadcasting c.
// All assertions must hold in order to return true.
OPD(a, c m) bool {
	assert (t.e. sequence [a, ..., c])
	for each i, m in sequence, except a {
		predecessor := sequence[i-1]
		assert (
			predecessor in m.positiveAcks
			|| m.sender == precessor.sender)
		assert (m not in c.negativeAcks)
	}
}

// Partial order.
// All assertions must hold in order to return true.
(c m) follows(b m) bool {
	assert OPD(b, c)
	for all a in received {
		if OPD(a, b) {
			assert OPD(a, c)
		}
	}
}
\end{lstlisting}


\section{Testing}

TODO


\printbibliography


\end{document}