diff options
author | Julius Bünger <buenger@mytum.de> | 2019-06-22 01:56:10 +0200 |
---|---|---|
committer | Julius Bünger <buenger@mytum.de> | 2019-06-22 01:56:10 +0200 |
commit | 50de5483528687312e90f29178f716c9d868d55c (patch) | |
tree | ea12748e5ecb81c98ccb46d24619bc906f237cc5 /doc | |
parent | f031f34d3f523985cbecc13f276c879d35707683 (diff) | |
download | gnunet-50de5483528687312e90f29178f716c9d868d55c.tar.gz gnunet-50de5483528687312e90f29178f716c9d868d55c.zip |
Doc RPS: Add high-level subsection on Brahms
Diffstat (limited to 'doc')
-rw-r--r-- | doc/handbook/chapters/developer.texi | 26 |
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 | |||
8907 | connected peers. | 8907 | connected peers. |
8908 | The adapted sampler makes sure that each request for random peers is | 8908 | The adapted sampler makes sure that each request for random peers is |
8909 | independent from the others. | 8909 | independent from the others. |
8910 | |||
8911 | @node Brahms | ||
8912 | @subsection Brahms | ||
8913 | The high-level concept of Brahms is two-fold: Combining push-pull gossip | ||
8914 | with locally fixing a assumed bias using cryptographic min-wise | ||
8915 | permutations. | ||
8916 | The central data structure is the view - a peer's current local sample. | ||
8917 | This view is used to select peers to push to and pull from. | ||
8918 | This simple mechanism can be biased easily. For this reason Brahms | ||
8919 | 'fixes' the bias by using the so-called sampler. A data structure that | ||
8920 | takes a list of elements as input and outputs a random one of them | ||
8921 | independently of the frequency in the input set. Both an element that | ||
8922 | was put into the sampler a single time and an element that was put into | ||
8923 | it a million times have the same probability of being the output. | ||
8924 | This is achieved this is achieved with exploiting min-wise independent | ||
8925 | permutations. In rps we use HMACs: On the initialisation of a sampler | ||
8926 | element, a key is chosen at random. On each input the HMAC with the | ||
8927 | random key is computed. The sampler element keeps the element with the | ||
8928 | minimal HMAC. | ||
8929 | |||
8930 | In order to fix the bias in the view, a fraction of the elements in the | ||
8931 | view are sampled through the sampler from the random stream of peer IDs. | ||
8932 | |||
8933 | According to the theoretical analysis of Bortnikov et al. this suffices | ||
8934 | to keep the network connected and having random peers in the view. | ||
8935 | |||