From efca72147ae8b90c75e722ebc393e7883aaaa4a6 Mon Sep 17 00:00:00 2001
From: rtrimana <rtrimana@uci.edu>
Date: Wed, 6 Jul 2016 10:37:53 -0700
Subject: [PATCH] Adding server algorithm

---
 doc/iotcloud.tex | 98 +++++++++++++++++++++---------------------------
 1 file changed, 43 insertions(+), 55 deletions(-)

diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex
index a571c06..c0aaf1b 100644
--- a/doc/iotcloud.tex
+++ b/doc/iotcloud.tex
@@ -2,6 +2,7 @@
 \newcommand{\tuple}[1]{\ensuremath \langle #1 \rangle}
 \usepackage{color}
 \usepackage{amsthm}
+\usepackage{algpseudocode}
 \newtheorem{theorem}{Theorem}
 \newtheorem{defn}{Definition}
 \newcommand{\note}[1]{{\color{red} \bf [[#1]]}}
@@ -22,61 +23,6 @@ hash2(user id | password)
 Server has finite length queue of entries + max\_entry\_identifier +
 server login key
 
-\textbf{Login}
-\note{Look at formal algorithm descriptions elsewhere, this is just informal prose...  It really needs to be more precise...}
-
-\begin{enumerate}
-\item In the beginning, there are $d$ devices. Each of the 
-devices has a randomly/user-chosen self-generated $m$-bit user 
-identification $i$ and $n$-bit password $p$.\note{All devices being known in the beginning seems unreasonable...How about 1 device initially, and devices can be added at any time...}
-\item Each device registers these $i$ and $p$ with the server. 
-The server appends ‘salt’ values, $k$-bit random strings $s1$ 
-and $s2$, and generate hash values $j=h(i+s1)$ and 
-$o=h(p+s2)$ for each $i$ and $p$. All $s1$, $s2$, $j$ and $o$ 
-are then stored in the database.\note{Are these the same $i$ and $p$ as below, if so, you just gave away the password}
-\item Device to server validation is done by checking the hash values 
-$j\textsc{\char13}$ and $o\textsc{\char13}$ from $i\textsc{\char13}$ and 
-$p\textsc{\char13}$ that are given by users at login time against 
-$i$ and $p$ that are stored in the database.
-\end{enumerate}
-
-\textbf{Symmetric Keys}
-\note{The user uses the same username/key to log into all devices}
-\begin{enumerate}
-\item In the beginning, there are $d$ devices. Each of the 
-devices has a randomly/user-chosen self-generated $m$-bit user 
-identification $i$ and $n$-bit password $p$. These $i$ and $p$ 
-are used for device login on server.
-\item All of $d$ agree on a hash function $h$ that is not known by 
-the server.\note{Doesn't make sense to agree on a hash function...People have a shared key.}
-\item A symmetric key for each device is generated by applying $h$
-to the value $(i + p)$ that gives $SK=h(i + p)$.
-\item This value $SK$ is pre-known and pre-stored by all other 
-devices prior to operation of the data structure.
-\end{enumerate}
-
-\textbf{Data Structure on Server}
-\note{Define server state as an appropriate tuple and then give pseudocode here for updating that tuple...}
-\begin{enumerate}
-\item Server maintains a finite length $q$-entry FIFO queue 
-$Q=\{0, 1, …, q-1\}$. It has a head and a tail pointers that keep track 
-of head and tail slots.
-\item Server records a max entry identifier $max$ as a limit for $q$. 
-It keeps track that $q \leq max$ at all times. When $q=max$, the queue 
-mechanism allows this sequence of events when there is a new slot added:
-\begin{enumerate}
-\item Pointer for entry $0$ now points to entry $1$, making it the new 
-entry $0$.
-\item Entry $0$ is expunged from the queue.
-\item New entry is added to the end of the queue, making it entry $q$.
-\item Pointer for entry $q-1$ is advanced to entry $q$, making it the new 
-entry $q-1$.
-\end{enumerate}
-\item For client login, server maintains a table with values $i$, $p$,
-$s1$, and $s2$ that are generated when device registers itself on server 
-for the first time.
-\end{enumerate}
-
 \subsection{Entry layout}
 Each entry has:
 \begin{enumerate}
@@ -177,6 +123,48 @@ Client can make a request to resize the queue. This is done as a write that comb
   (a) a slot with the message, and
 	(b) a request to the server
 
+\subsection{Server Algorithm}
+\begin{algorithmic}[1]
+\Function{Server}{$m$,$max$,$s$,$Data*$}
+\textit{
+\newline{// m = client message (read/write/resize)}
+\newline{// max = maximum number of slots (input only for resize message)}
+\newline{// n = number of slots}
+\newline{// s = sequence number}
+\newline{// t = latest sequence number on server}
+\newline{// d = sequence number difference (1 by default)}
+\newline{// Data = array of slots written/read (input only for write)}
+\newline{// Q = queue of slots on server}
+\newline{// Resize() returns the old last slot in the queue}
+\newline{// Append() updates Q and latest s after appending the new slot}
+\newline{// Append() returns the latest Slot written with its correct s}
+}
+\If{$m = read$}
+\If{$s \in T = \{t_1, t_2, \dots, t_n\}$}
+\State $Data := \{Slot_{s}, Slot_{s+1}, \dots, Slot_{t_n}\} \forall Slot_i \in Q$
+\Else
+\State $Data := \emptyset$
+\EndIf
+\ElsIf{$m = write$}
+\If{$s = t_n + d$ \textbf{and} $n \leq max$ \textbf{and} $Data.length = 1$}
+\State $newSlot := Data[1]$
+\If{$n = max$}
+\State $DeleteFirst(Q)$
+\Else
+\State // $n < max$
+\State $n := n + 1$
+\EndIf
+\State $Data := Append(newSlot,Q)$
+\Else
+\State $Data := \emptyset$
+\EndIf
+\ElsIf{$m = resize$}
+\State $Data := Resize(max)$
+\EndIf
+\State \Return{$Data$}
+\EndFunction
+\end{algorithmic}
+
 \subsection{Formal Guarantees}
 
 \textit{To be completed ...}
-- 
2.34.1