1 Kademlia 首藤一幸 産業技術総合研究所 グリッド研究センター 2004年 7月 27日(火) 2 資料 IPTPS02 の論文とスライド � “Kademlia: A Peer-topeer Information System Based on the XOR Metric” ウェブページ � http://kademlia.scs.cs.nyu.edu/ 7/26時点では参照できず。 3 Kademlia の位置付け 論文中に現れる比較対象: � Chord � Chord の悪い点: � 経路表が厳格。 � ノードの failure や、経路表の欠損からの復旧が複雑。 � qeury 転送の方向が一方向。 � Incoming traffic を元に経路表を更新できない。 � Kademlia では、2ノード間の関係は symmetric。 � x が y の経路表に載っ
TomP2PTomP2P is a DHT with additional features, such as storing multiple values for a key. Each peer has a table (either disk-based or memory-based) to store its values. A single value can be queried / updated with a secondary key. The underlying communication framework uses Java NIO to handle many concurrent connections. DevelopmentTomP2P uses github for development and issue tracking. In case ca
The explosion of electronically stored data represents the fastest growing segment of IT. Storage media and disk drives are becoming cheaper, and yet many backup services charge thousands of dollars a year to back up an $80 disk drive; Amazon costs close to $250 a month to back up 2 TB, notes Praerit Garg, president of Symform, a new cloud network that uses sharing to offer low-cost storage and ba
Chordアルゴリズムの解説ページです。 掲載コンテンツへのリンク先を変更する可能性があるので、ブックマークやリンクは、このページにお願いします。 Chordは、DHT(Distributed Hash Table)と呼ばれる種類のPeer-to-Peerアルゴリズムです。 特に、構造化オーバレイ(Structured Overlay Network)と呼ばれるルーティング手法に特徴があります。 解説スライドでは、そもそもDHTとは何なのかという初歩的なことから、successorやpredecessor、finger tableと呼ばれるChordの有名な経路表の解説や、多くの解説ではあまり触れられることがないけれどもきわめて重要である、ネットワークの構築方法(join・stabilize)についても詳細に解説しています。 スライドのページ数は多いですが、1ページ当たり平均数秒で読めるは
Skip Graphs James Aspnes, Gauri Shah Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2003, pp. 384-393. Submitted to Journal of Algorithms. Abstract Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where elements are stored in separate nodes that may fail at any time.
About libjingle libjingle is a collection of open-source C++ code and sample applications that enables you to build a peer-to-peer application. The code handles creating a network connection (through NAT and firewall devices, relay servers, and proxies), negotiating session details (codecs, formats, etc.), and exchanging data. It also provides helper tasks such as parsing XML, and handling network
前々から一度じっくり勉強しないとなぁと思っていたDHTまわりの勉強がてらKademliaっぽいものをPythonで実装してみました。 Kademliaはいろいろ実装があるので、ソースを読んじゃうと答えみちゃった感じになるかなーと思って、元論文と 首藤様の資料 くらいしか見ずに実装してみました。ので、いろいろ間違ってるかも知れませんが・・・。 本家Kademliaとの主な違いは UDPではなくTCPを使っている ローカル環境しかもっていないので、UDPパケットがロスしやすい場合(WAN)を想定して実装するのがめんどくさい。 よってRPC-IDをつけていない。 パケットの分割や再送もTCPにおまかせ。 original publisherから一定時間publishを受けなくてもインデックス情報をexpireしていない 実装するのは簡単です。 ノードがネットワークに参加したとき、Index情報を
最近 クラウド という単語が流行していますが、「大規模な計算資源を低コストで提供してくれるトコロがあるらしいので、自前で持っていた計算資源を委託しちゃえば運用する手間も知識も要らないし、そもそもサーバーを買う費用を省けちゃうから嬉しい」という発想に基づいているらしく、しかし技術的には 大規模な計算資源を低コストで構築する技術 がポイントでしょう。 大規模な計算資源をどうやって安く構築するか。 従来は、システムの能力を高めるためには、高性能・高機能(それゆえ高価な)マシンを導入するというスケールアップの手法が採られていたのだが、この手法では10倍に性能を上げるために、たとえば30倍のコストがかかるかもしれない。スケールアップと比べてスケールアウトでは、導入したコストにほぼ比例して、パフォーマンスの向上が見込める。 『UNIX magazine 2009年4月号』 p.31 *1 何百万円もす
Chordは、分散ハッシュテーブルを実現するアルゴリズムの一つ。P2Pネットワークにおいて、サーバを用いることなく高速にコンテンツの検索、ルーティングを行う手法。 アルゴリズム[編集] Chordでは、コンテンツのハッシュ値を求める関数にSHA-1を採用するのが一般的である。ネットワークに参加するノードは、SHA-1のハッシュ値の値域を満たす一意なが割り当てられる。 ここで、という関数を定義する。この関数は、ハッシュ値が与えられたとき、値を増加させる方向で次に存在しているノードのを返す。なお、とは接続されていると考える。 ネットワークで情報を共有する際には、共有したい情報のハッシュ値をとしてを満たすを持つノードが、実際に情報を保持しているノードの位置を示すIPアドレス等の情報を保持する。 また、ネットワークに参加するノードは、自身のをとした場合、 , ただし のをもつノードのIPアドレスを
さて、P2Pでは最近「分散ハッシュテーブル」というキーワードをよく聞きます。分散ハッシュテーブルついては後で紹介しますが、これを用いるとルーティング、検索が高速に、しかもP2Pネットワーク全体に対して適用することができます。例えば既にeMuleと呼ばれるファイル共有システムでは分散ハッシュテーブルの一種であるkademliaが使われています。ではそもそも分散ハッシュテーブルとはどういうものなのでしょうか?それを説明するにはまず検索で使われるハッシュ法を説明する必要があります。 [お知らせ]分散ハッシュテーブル(DHT)についてわかりやすく解説したページを作りました。 DHTに興味のある方はまずこちらをご覧下さい。 分散ハッシュテーブル(DHT)入門〜その1 ハッシュ法 今、あるデータベースを考えてください。ここには人の名前と身長が書いてあるテーブルとしましょう。例えば table_1={
P2P Programming › Overview » Python framework implementation › Java framework implementation › Python P2P File Sharing App On this page › Peer initialization › Main loop › Handling connections › Routing and sending › Other methods › PeerConnection class The P2P Framework Implementation (Python version) This page walks through a Python implementation of the P2P framework library itself. I will assu
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く