[ / / / / / / / / / / / / / ] [ dir / random / 93 / biohzrd / hkacade / hkpnd / tct / utd / uy / yebalnia ]

/prog/ - Programming

Programming

Name
Email
Subject
REC
STOP
Comment *
File
Password (Randomized for file and post deletion; you may also set your own.)
Archive
* = required field[▶Show post options & limits]
Confused? See the FAQ.
Options

Allowed file types:jpg, jpeg, gif, png, webp,webm, mp4, mov
Max filesize is16 MB.
Max image dimensions are15000 x15000.
You may upload5 per post.


c1cff6 No.5299

Can someone help me understand DHTs with Byzantine fault tolerance? I read the wikipedia pages but they it didn't quite click for me. I'm also new to writing P2P stuff.

What is the algorithm, exactly? So I write a bunch of servers that all store some values with some keys and listen on a port. Then I want to query a key.

1. Do I send that key to every server and see which one replies? That sounds very inefficient if I have millions of servers all retrieving values frequently.

2. Is there a way to make it so that the server can't see the information it stores? I suppose I could somehow break up the file but now every query requires many more connections. Would it work if I encrypt the file and break it up into a small number of pieces, say 2, and store each piece on a different server? Even if an individual knew the key it couldn't decrypt even the part that it has.

3. How do I know the IPs of the servers without having a centralized directory?

4. What if the servers sometimes go offline? Is it enough to just store the same key-value on multiple peers and hope that at least one will be up?

____________________________
Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

c12183 No.5476

File: 246d5ce36eee8e4⋯.png (4.86 KB,225x224,225:224,images.png)

https://www.youtube.com/playlist?list=PLfTHgzgSsUiRbuCTkkA8O4ADz17jf6aY3

The first three videos are what you want.

Also the specifications of Kademlia, the DHT algorithm used in Bittorrent Mainnet DHT.

http://xlattice.sourceforge.net/components/protocol/kademlia/specs.html

Here's my take on it.

A DHT is a key value store where the key-value pairs are not stored in a central computer but distributed among many forming a network.

When a node joins the network it can query the network for a key and will receive a value associated with that key.

Also each node is assigned a portion of the key-value pairs to store. This is a black-box look at DHTs.

The interesting part is how to implement this without a central server that keeps track of which node stores which keys.

This is done using a decentralised or "P2P" algorithm outlined next.

Each node is assigned an id, which is typically the hash of its ip (and port I think). The nodes organize themselves in a ring, where each

node connects to its successor and predecessor in the id space. That is, node 6 connects to nodes 5 and 7. If let's say, node 5 is not available,

then it connects to the next available node in that direction.

The key-value pairs are distributed such that node with id n stores the pair such that the hash of the key is n. Since the space of a modern

hash function is huge, a node stores the keys that would be assigned to the previous nodes that are not pressent in the network.

In other words, the same space is used for keys and ndoe ids, and a node stores the keys closest to it in this space. This is the distance metric.

The most important concept to make this all work is how you route messages in this ring, That is, how do you find the contact information (ip,port)

of a node in this space.

If you're a node in the network and need

to find a key-value pair you need to locate the ip of the closest node to that key. You can do this by quering your neighbour to ask them

if they have the pair, if they don't, they give you the details of their neighbour so that you can ask them and so on walking thorugh the ring.

This is called an iterative traversal since you keep asking till you find the node that stores the pair you want. If instead your neighbour takes the burden of locating the node

that stores the pair you want, it is called a recursive traversal. This is done by your neighbour relaying your query along the ring and you wait

till you get a response. This query is recursively relaying along the ring by the nodes until the query messages reaches the target node.

Now this is not scalable, since at most n steps needs to be performed to do a query, where n is the number of nodes in the network.

You can reduce this to log(n) steps by using a finger table like kademlia, I think this is explained in the videos.

When a node joins the network, it needs to contact any existing node and perform the same routing algorithm used for queries, in order to find

the ip of its successor and predecessor in the network. Then it contacts its successor to take ownership of the key-value pairs that are

now assigned to it and that were previously kept by the successor.

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

820a30 No.5499

File: 798dc12699dd73f⋯.jpg (66.08 KB,640x640,1:1,1571041169699.jpg)

hi anon,

you should check out something like this : https://docs.rs/libp2p/0.37.1/libp2p/tutorial/index.html

I'd use this to write any new P2P stuff.

cheers,

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

f3e476 No.5505

Thank you guys so much for posting these amazing resources. I'm gonna get cracking on building a nice project using the info you've all given me.

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.



[Return][Go to top][Catalog][Nerve Center][Random][Post a Reply]
Delete Post [ ]
[]
[ / / / / / / / / / / / / / ] [ dir / random / 93 / biohzrd / hkacade / hkpnd / tct / utd / uy / yebalnia ]