sequencer design documentation

2 files changed, 255 insertions, 0 deletions

diff --git a/doc/design.pdf b/doc/design.pdf
new file mode 100644
index 0000000..ad9746c
--- /dev/null
+++ b/doc/design.pdf
diff --git a/doc/design.tex b/doc/design.tex
new file mode 100644
index 0000000..e521306
--- /dev/null
+++ b/doc/design.tex
@@ -0,0 +1,255 @@
+\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}