[GNUnet-SVN] r27244 - gnunet-java/doc

[gnunet]

Author: dold
Date: 2013-05-22 12:15:45 +0200 (Wed, 22 May 2013)
New Revision: 27244

Added:
   gnunet-java/doc/consensus.pdf
   gnunet-java/doc/consensus.tex
Log:
consensus rounds doc


Added: gnunet-java/doc/consensus.pdf
===================================================================
(Binary files differ)

Index: gnunet-java/doc/consensus.pdf
===================================================================
--- gnunet-java/doc/consensus.pdf       2013-05-22 09:19:03 UTC (rev 27243)
+++ gnunet-java/doc/consensus.pdf       2013-05-22 10:15:45 UTC (rev 27244)

Property changes on: gnunet-java/doc/consensus.pdf
___________________________________________________________________
Added: svn:mime-type
## -0,0 +1 ##
+application/octet-stream
\ No newline at end of property
Added: gnunet-java/doc/consensus.tex
===================================================================
--- gnunet-java/doc/consensus.tex                               (rev 0)
+++ gnunet-java/doc/consensus.tex       2013-05-22 10:15:45 UTC (rev 27244)
@@ -0,0 +1,87 @@
+\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}