[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r27244 - gnunet-java/doc
From: |
gnunet |
Subject: |
[GNUnet-SVN] r27244 - gnunet-java/doc |
Date: |
Wed, 22 May 2013 12:15:46 +0200 |
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}
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r27244 - gnunet-java/doc,
gnunet <=