Living Will for Resilient Structured Overlay Networks

Kimihiro MIZUTANI; Takeru INOUE; Toru MANO; Osamu AKASHI; Satoshi MATSUURA; Kazutoshi FUJIKAWA

doi:10.1587/transcom.2015ADP0011

Living Will for Resilient Structured Overlay Networks

Kimihiro MIZUTANI, Takeru INOUE, Toru MANO, Osamu AKASHI, Satoshi MATSUURA, Kazutoshi FUJIKAWA

Full Text Views

0

Cite this

Summary :

The routing efficiency of structured overlay networks depends on the consistency of pointers between nodes, where a pointer maps a node identifier to the corresponding address. This consistency can, however, break temporarily when some overlay nodes fail, since it takes time to repair the broken pointers in a distributed manner. Conventional solutions utilize “backpointers” to quickly discover any failure among the pointing nodes, which allow them to fix the pointers in a short time. Overlay nodes are, however, required to maintain backpointers for every pointing node, which incurs significant memory and consistency check overhead. This paper proposes a novel light-weight protocol; an overlay node gives a “living will” containing its acquaintances (backpointers) only to its successor, thus other nodes are freed from the need to maintain it. Our carefully-designed protocol guarantees that all acquaintances are registered via the living will, even in the presence of churn, and the successor notifies the acquaintances for the deceased. Even if the successor passes away and the living will is lost, the successor to the successor can identify the acquaintances with a high success ratio. Simulations show that our protocol greatly reduces memory overhead as well as the detection time for node failure with the cost being a slight increase in messaging load.

Publication: IEICE TRANSACTIONS on Communications Vol.E99-B No.4 pp.830-840

Publication Date: 2016/04/01

Publicized

Online ISSN: 1745-1345

DOI: 10.1587/transcom.2015ADP0011

Type of Manuscript: Special Section PAPER (Special Section on Autonomous Decentralized Systems Technologies and Applications for Next-Generation Social Infrastructure)

Category

Authors

Kimihiro MIZUTANI
  NTT Corporation
Takeru INOUE
  NTT Corporation
Toru MANO
  NTT Corporation
Osamu AKASHI
  NTT Corporation
Satoshi MATSUURA
  Tokyo Institute of Technology
Kazutoshi FUJIKAWA
  Nara Institute of Science and Technology

Keyword

fault tolerance, churn, structured overlay network, peer to peer

Cite this

Copy

Kimihiro MIZUTANI, Takeru INOUE, Toru MANO, Osamu AKASHI, Satoshi MATSUURA, Kazutoshi FUJIKAWA, "Living Will for Resilient Structured Overlay Networks" in IEICE TRANSACTIONS on Communications, vol. E99-B, no. 4, pp. 830-840, April 2016, doi: 10.1587/transcom.2015ADP0011.
Abstract: The routing efficiency of structured overlay networks depends on the consistency of pointers between nodes, where a pointer maps a node identifier to the corresponding address. This consistency can, however, break temporarily when some overlay nodes fail, since it takes time to repair the broken pointers in a distributed manner. Conventional solutions utilize “backpointers” to quickly discover any failure among the pointing nodes, which allow them to fix the pointers in a short time. Overlay nodes are, however, required to maintain backpointers for every pointing node, which incurs significant memory and consistency check overhead. This paper proposes a novel light-weight protocol; an overlay node gives a “living will” containing its acquaintances (backpointers) only to its successor, thus other nodes are freed from the need to maintain it. Our carefully-designed protocol guarantees that all acquaintances are registered via the living will, even in the presence of churn, and the successor notifies the acquaintances for the deceased. Even if the successor passes away and the living will is lost, the successor to the successor can identify the acquaintances with a high success ratio. Simulations show that our protocol greatly reduces memory overhead as well as the detection time for node failure with the cost being a slight increase in messaging load.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2015ADP0011/_p

Copy

@ARTICLE{e99-b_4_830,
author={Kimihiro MIZUTANI, Takeru INOUE, Toru MANO, Osamu AKASHI, Satoshi MATSUURA, Kazutoshi FUJIKAWA, },
journal={IEICE TRANSACTIONS on Communications},
title={Living Will for Resilient Structured Overlay Networks},
year={2016},
volume={E99-B},
number={4},
pages={830-840},
abstract={The routing efficiency of structured overlay networks depends on the consistency of pointers between nodes, where a pointer maps a node identifier to the corresponding address. This consistency can, however, break temporarily when some overlay nodes fail, since it takes time to repair the broken pointers in a distributed manner. Conventional solutions utilize “backpointers” to quickly discover any failure among the pointing nodes, which allow them to fix the pointers in a short time. Overlay nodes are, however, required to maintain backpointers for every pointing node, which incurs significant memory and consistency check overhead. This paper proposes a novel light-weight protocol; an overlay node gives a “living will” containing its acquaintances (backpointers) only to its successor, thus other nodes are freed from the need to maintain it. Our carefully-designed protocol guarantees that all acquaintances are registered via the living will, even in the presence of churn, and the successor notifies the acquaintances for the deceased. Even if the successor passes away and the living will is lost, the successor to the successor can identify the acquaintances with a high success ratio. Simulations show that our protocol greatly reduces memory overhead as well as the detection time for node failure with the cost being a slight increase in messaging load.},
keywords={},
doi={10.1587/transcom.2015ADP0011},
ISSN={1745-1345},
month={April},}

Copy

TY - JOUR
TI - Living Will for Resilient Structured Overlay Networks
T2 - IEICE TRANSACTIONS on Communications
SP - 830
EP - 840
AU - Kimihiro MIZUTANI
AU - Takeru INOUE
AU - Toru MANO
AU - Osamu AKASHI
AU - Satoshi MATSUURA
AU - Kazutoshi FUJIKAWA
PY - 2016
DO - 10.1587/transcom.2015ADP0011
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E99-B
IS - 4
JA - IEICE TRANSACTIONS on Communications
Y1 - April 2016
AB - The routing efficiency of structured overlay networks depends on the consistency of pointers between nodes, where a pointer maps a node identifier to the corresponding address. This consistency can, however, break temporarily when some overlay nodes fail, since it takes time to repair the broken pointers in a distributed manner. Conventional solutions utilize “backpointers” to quickly discover any failure among the pointing nodes, which allow them to fix the pointers in a short time. Overlay nodes are, however, required to maintain backpointers for every pointing node, which incurs significant memory and consistency check overhead. This paper proposes a novel light-weight protocol; an overlay node gives a “living will” containing its acquaintances (backpointers) only to its successor, thus other nodes are freed from the need to maintain it. Our carefully-designed protocol guarantees that all acquaintances are registered via the living will, even in the presence of churn, and the successor notifies the acquaintances for the deceased. Even if the successor passes away and the living will is lost, the successor to the successor can identify the acquaintances with a high success ratio. Simulations show that our protocol greatly reduces memory overhead as well as the detection time for node failure with the cost being a slight increase in messaging load.
ER -