構造化オーバーレイネットワークに適した分散双方向連結リストDDLL

提供: Research

DDLL-color.png

目次

書誌情報

安倍広多,吉田幹,構造化オーバーレイネットワークに適した分散双方向連結リストDDLL,情報処理学会研究報告,Vol. 2010-DPS-144, No. 1, pp. 1--8, (2010-9)

Abstract

分散双方向連結リスト(双方向リング)は構造化オーバーレイネットワークでしばしば用いられる基本的な分散データ構造の一つである.本稿では,分散双方向連結リストを構築・維持するための自律分散アルゴリズムDDLLを提案する.DDLLでは,複数のノードが並行して挿入・削除する場合でも連結リストの構造は常に維持される.また,分散排他制御を用いないため,ノード故障からの修復が容易である.本稿では障害回復を含むアルゴリズムの詳細と形式的な記述を示す.

A distributed doubly-linked list (or bidirectional ring) is a fundamental distributed data structure often used in structured overlay networks. In this paper, we propose a novel decentralized algorithm, called DDLL, for constructing and maintaining distributed doubly-linked lists. DDLL consistently maintains the structure of a linked list even if multiple nodes are simultaneously inserted or deleted. In addition, because DDLL does not require distributed mutual exclusion, it can easily recover the data structure when a node fails. In this paper, we give a detailed explanation and formal description of the algorithm.

論文

ここに掲載した著作物の利用に関する注意 本著作物の著作権は(社)情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。

Notice for the use of this material The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof.

備考: この論文の国際会議版は Constructing Distributed Doubly Linked Lists without Distributed Locking です.参照される場合はこちらをお勧めします.

プレゼンテーション

DPS研究会で使ったものを少し修正しています.

デモ

DDLLの動作を可視化するJavaFXのアプレットです.

MieruDDLL.png



個人用ツール