Correctness of the routing algorithm for distributed key-value store based on order preserving linear hashing and skip graph

Ken Higuchi; Makoto Yoshida; Tatsuo Tsuji; Naoyuki Miyamoto

doi:10.1109/SNPD.2017.8022762

2017 18th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD)

Correctness of the routing algorithm for distributed key-value store based on order preserving linear hashing and skip graph

Year: 2017, Pages: 459-464

DOI Bookmark: 10.1109/SNPD.2017.8022762

Authors

Ken Higuchi, Graduate School of Engineering, University of Fukui, Fukui, Japan
Makoto Yoshida, Graduate School of Engineering, University of Fukui, Fukui, Japan
Tatsuo Tsuji, Graduate School of Engineering, University of Fukui, Fukui, Japan
Naoyuki Miyamoto, Graduate School of Engineering, University of Fukui, Fukui, Japan

Abstract

In this paper, the correctness of the routing algorithm for the distributed key-value store based on order preserving linear hashing and Skip Graph is proved. In this system, data are divided by linear hashing and Skip Graph is used for overlay network. The routing table of this system is very uniform. Then, short detours can exist in the route of forwarding. By using these detours, the number of hops for the query forwarding is reduced.

Like what you’re reading?

Already a member?

Get this article FREE with a new membership!

Self-Refining Skip Graph: A Structured Overlay Approaching to Ideal Skip Graph
2016 IEEE 40th Annual Computer Software and Applications Conference (COMPSAC)
Locally Self-Adjusting Skip Graphs
2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS)
Performance evaluation of routing algorithms for distributed key-value store based on order preserving linear hashing and Skip graph
2016 IEEE/ACIS 15th International Conference on Computer and Information Science (ICIS)
A P2P Sensor Data Stream Delivery System to Accommodate Heterogeneous Cycles Using Skip Graphs
2015 10th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC)
FRT-Skip Graph: A Skip Graph-style structured overlay based on Flexible Routing Tables
2016 IEEE Symposium on Computers and Communication (ISCC)
Guard: Secure routing in skip graph
2017 IFIP Networking Conference (IFIP Networking) and Workshops
Data Structures for Routing Table of the Distributed Key-Value Store Based on Order Preserving Linear Hashing and Skip Graph with the Load Balancing Method
2022 23rd ACIS International Summer Virtual Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD-Summer)
A Load Balancing Method for Distributed Key-Value Store Based on Order Preserving Linear Hashing and Skip Graph
2019 20th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD)
Skip Suffix Array: A Partial Match Retrieval Method on Structured Overlay Networks
2020 International Conference on Information Networking (ICOIN)
Demo: Skip Graph Middleware Implementation
2020 International Symposium on Reliable Distributed Systems (SRDS)

Correctness of the routing algorithm for distributed key-value store based on order preserving linear hashing and skip graph

Authors

Abstract

Related Articles