aboutsummaryrefslogtreecommitdiff
path: root/doc/handbook/chapters/developer.texi
diff options
context:
space:
mode:
Diffstat (limited to 'doc/handbook/chapters/developer.texi')
-rw-r--r--doc/handbook/chapters/developer.texi26
1 files changed, 26 insertions, 0 deletions
diff --git a/doc/handbook/chapters/developer.texi b/doc/handbook/chapters/developer.texi
index e101b06bd..a43bd7b37 100644
--- a/doc/handbook/chapters/developer.texi
+++ b/doc/handbook/chapters/developer.texi
@@ -8907,3 +8907,29 @@ client requests independently random, they cannot be drawn from the
8907connected peers. 8907connected peers.
8908The adapted sampler makes sure that each request for random peers is 8908The adapted sampler makes sure that each request for random peers is
8909independent from the others. 8909independent from the others.
8910
8911@node Brahms
8912@subsection Brahms
8913The high-level concept of Brahms is two-fold: Combining push-pull gossip
8914with locally fixing a assumed bias using cryptographic min-wise
8915permutations.
8916The central data structure is the view - a peer's current local sample.
8917This view is used to select peers to push to and pull from.
8918This simple mechanism can be biased easily. For this reason Brahms
8919'fixes' the bias by using the so-called sampler. A data structure that
8920takes a list of elements as input and outputs a random one of them
8921independently of the frequency in the input set. Both an element that
8922was put into the sampler a single time and an element that was put into
8923it a million times have the same probability of being the output.
8924This is achieved this is achieved with exploiting min-wise independent
8925permutations. In rps we use HMACs: On the initialisation of a sampler
8926element, a key is chosen at random. On each input the HMAC with the
8927random key is computed. The sampler element keeps the element with the
8928minimal HMAC.
8929
8930In order to fix the bias in the view, a fraction of the elements in the
8931view are sampled through the sampler from the random stream of peer IDs.
8932
8933According to the theoretical analysis of Bortnikov et al. this suffices
8934to keep the network connected and having random peers in the view.
8935