\documentclass{article}
\usepackage{inputenc}
\usepackage{makeidx,amsmath,amssymb,exscale,multicol,epsfig,graphics,verbatim,ulem}
\usepackage{epsfig,geometry,url,listings,boxedminipage}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}


\title{Consensus Protocol}

\author{Florian Dold}

\begin{document}

\maketitle

\section{Rounds}

\begin{enumerate}
\item Distribution of elements with the exponential scheme
\item Agreement on the inventory\footnote{The set of all element hashes.} of each peer.
  The final inventory only contains values that are known by at least $t+1$ peers.
\item Completion of each peer's consensus set, by using all-to-all set reconciliation,
  only accept elements in the final inventory.
\end{enumerate}

\section{Exponential Dispersion}
TBD

\section{Gradecast}
Notation:
\begin{itemize}
  \item $n$: The number of peers $P_1,\ldots,P_n$
  \item $t$: The number of faulty peers, $ t < \frac{1}{3}n$
  \item $P_h$: The originating peer for the broadcast message $v_h$
  \item $V_k[i \rightarrow j]$: the value received by $P_j$ from $P_i$ in step $k$
  \item $m_k[i]$: The value most often received by $P_i$ in step $k$
  \item $\#m_k[i]$: The number of received occurences of $m_k[i]$ in step $k$
  \item $v_i$: The final value of $P_i$
  \item $c_i$: The confidence of $P_i$ regarding the value sent by $P_h$
\end{itemize}

\begin{algorithm}[H]
\caption{Gradecast}\label{gradecast}
\begin{algorithmic}[1]
\Statex \textit{Step 1}
\State The origin peer $P_h$ broadcasts $v_h$
\State Every other peer $P_i$ receives $V_1[h \rightarrow i]$
\Statex
\Statex \textit{Step 2}
\State Every peer $P_i$ re-broadcasts $V_1[h \rightarrow i]$
\State Every other peer $P_j$ receives $V_2[i \rightarrow j]$
\Statex
\Statex \textit{Step 3}
\If{$\#m_2[i] \ge n-t$}
  \State Peer $P_i$ broadcasts $m_2[i]$
  \State Every other peer $P_j$ receives $V_3[i \rightarrow j]$ or $\bot$
\EndIf
\Statex
\Statex \textit{Grading}
\If{$\#m_3[i] \ge n-t$}
  \State $v_i = m_3[i], c_i = 2$
\ElsIf{$\#m_3[i] \ge t+1$}
  \State $v_i = m_3[i], c_i = 1$
\Else
  \State $v_i = \bot, c_i = 0$
\EndIf
\end{algorithmic}
\end{algorithm}

\noindent
Properties for a pair of non-faulty Peers $P_i, P_j$:
\begin{enumerate}
  \item If the broadcaster $P_h$ is non-faulty, then $v_i=v_h$ and $c_i=2$
  \item If $c_i > 0$ and $c_j > 0$, then $v_i = v_j$
  \item $|c_i - c_j| \le 1$
\end{enumerate}

\noindent
For gnunet-consensus, the protocol is executed by every peer in the inventory round;
instead of broadcasting values, a set reconciliation is performed with every other peer.
If a peer grade-casts with a confidence other than $2$ it is marked as faulty, its inventory
is excluded from the final inventory.


\end{document}