[Top][All Lists]

[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

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 ##
\ 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 @@
+\title{Consensus Protocol}
+\author{Florian Dold}
+\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$ 
+\item Completion of each peer's consensus set, by using all-to-all set 
+  only accept elements in the final inventory.
+\section{Exponential Dispersion}
+  \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 
+  \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$
+\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 \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 \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$
+\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$
+  \State $v_i = \bot, c_i = 0$
+Properties for a pair of non-faulty Peers $P_i, P_j$:
+  \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$
+For gnunet-consensus, the protocol is executed by every peer in the inventory 
+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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]