The Experts below are selected from a list of 4395 Experts worldwide ranked by ideXlab platform
Manolis Koubarakis - One of the best experts on this subject based on the ideXlab platform.
-
Distributed RDFS Reasoning Over Structured Overlay Networks
Journal on Data Semantics, 2013Co-Authors: Zoi Kaoudi, Manolis KoubarakisAbstract:In this paper, we study the problem of distributed RDFS reasoning over Structured Overlay networks. Distributed RDFS reasoning is essential for providing the functionality that Semantic Web and Linked Data applications require. Our goal is to present various inference techniques for RDFS reasoning in a distributed environment, and analyze them both theoretically and experimentally. The reasoning methods we present are based on bottom-up and top-down techniques and have been implemented on top of the distributed hash table Bamboo. Our algorithms range from forward and backward chaining ones to rewriting algorithms based on magic sets. We formally prove the correctness of the algorithms and study the time-space trade-off they exhibit analytically and experimentally in a local cluster.
-
xml data dissemination using automata on top of Structured Overlay networks
The Web Conference, 2008Co-Authors: Iris Miliaraki, Zoi Kaoudi, Manolis KoubarakisAbstract:We present a novel approach for filtering XML documents using nondeterministic finite automata and distributed hash tables. Our approach differs architecturally from recent proposals that deal with distributed XML filtering; they assume an XML broker architecture, whereas our solution is built on top of distributed hash tables. The essence of our work is a distributed implementation of YFilter, a state-of-the-art automata-based XML filtering system on top of Chord. We experimentally evaluate our approach and demonstrate that our algorithms can scale to millions of XPath queries under various filtering scenarios, and also exhibit very good load balancing properties.
-
evaluating conjunctive triple pattern queries over large Structured Overlay networks
International Semantic Web Conference, 2006Co-Authors: Erietta Liarou, Stratos Idreos, Manolis KoubarakisAbstract:We study the problem of evaluating conjunctive queries composed of triple patterns over RDF data stored in distributed hash tables. Our goal is to develop algorithms that scale to large amounts of RDF data, distribute the query processing load evenly and incur little network traffic. We present and evaluate two novel query processing algorithms with these possibly conflicting goals in mind. We discuss the various tradeoffs that occur in our setting through a detailed experimental evaluation of the proposed algorithms.
-
distributed evaluation of continuous equi join queries over large Structured Overlay networks
International Conference on Data Engineering, 2006Co-Authors: Stratos Idreos, Christos Tryfonopoulos, Manolis KoubarakisAbstract:We study the problem of continuous relational query processing in Internet-scale Overlay networks realized by distributed hash tables. We concentrate on the case of continuous two-way equi-join queries. Joins are hard to evaluate in a distributed continuous query environment because data from more than one relations is needed, and this data is inserted in the network asynchronously. Each time a new tuple is inserted, the network nodes have to cooperate to check if this tuple can contribute to the satisfaction of a query when combined with previously inserted tuples. We propose a series of algorithms that initially index queries at network nodes using hashing. Then, they exploit the values of join attributes in incoming tuples to rewrite the given queries into simpler ones, and reindex them in the network where they might be satisfied by existing or future tuples. We present a detailed experimental evaluation in a simulated environment and we show that our algorithms are scalable, balance the storage and query processing load and keep the network traffic low.
-
publish subscribe with rdf data over large Structured Overlay networks
Databases Information Systems and Peer-to-Peer Computing, 2005Co-Authors: Erietta Liarou, Stratos Idreos, Manolis KoubarakisAbstract:We study the problem of evaluating RDF queries over Structured Overlay networks.We consider the publish/subscribe scenario where nodes subscribewith long-standing queries and receive notifications whenever triples matching their queries are inserted in the network. In this paper we focus on conjunctive multi-predicate queries. We demonstrate that these queries are useful in various modern applications e.g., distributed digital libraries or Grid resource discovery. Conjunctive multipredicate queries are hard to answer since multiple triples are necessary for their evaluation, and these triples will usually be inserted in the network asynchronously. We present and evaluate query processing algorithms that are scalable and distribute the query processing load evenly.
Seif Haridi - One of the best experts on this subject based on the ideXlab platform.
-
dealing with bootstrapping maintenance and network partitions and mergers in Structured Overlay networks
Self-Adaptive and Self-Organizing Systems, 2012Co-Authors: Tallat M. Shafaat, Ali Ghodsi, Seif HaridiAbstract:In the last decade, numerous Structured Overlay networks were proposed as a scalable infrastructure to build large-scale distributed systems under dynamic environments. These Overlays were touted to be fault-tolerant and self-managing, yet, as we show in this paper, they fall short of handling some extreme scenarios they envision. These scenarios include bootstrapping, and underlying network partitions and mergers. We argue that handling such extreme scenarios is fundamental to providing a fault-tolerant and self-managing system, and thus, Structured Overlay networks should intrinsically be able to handle them. In this paper, we present ReCircle, an Overlay algorithm that apart from performing periodic maintenance to handle churn like any other Overlay, can merge multiple Structured Overlay networks. We show how such an algorithm can be used for decentralized bootstrapping. ReCircle does not have any extra cost during normal maintenance compared to an isolated Overlay maintenance algorithm. Furthermore, the algorithm is tunable to tradeoff between bandwidth consumption and time to convergence during extreme events like bootstrapping and handling network partitions and mergers. We evaluate the algorithm extensively under various scenarios through simulation and experimentation on Planet Lab.
-
Dealing with network partitions in Structured Overlay networks
Peer-to-Peer Networking and Applications, 2009Co-Authors: Tallat M. Shafaat, Ali Ghodsi, Seif HaridiAbstract:Structured Overlay networks form a major class of peer-to-peer systems, which are touted for their abilities to scale, tolerate failures, and self-manage. Any long-lived Internet-scale distributed system is destined to face network partitions. Although the problem of network partitions and mergers is highly related to fault-tolerance and self-management in large-scale systems, it has hardly been studied in the context of Structured peer-to-peer systems. These systems have mainly been studied under churn (frequent joins/failures), which as a side effect solves the problem of network partitions, as it is similar to massive node failures. Yet, the crucial aspect of network mergers has been ignored. In fact, it has been claimed that ring-based Structured Overlay networks, which constitute the majority of the Structured Overlays, are intrinsically ill-suited for merging rings. In this paper, we present an algorithm for merging multiple similar ring-based Overlays when the underlying network merges. We examine the solution in dynamic conditions, showing how our solution is resilient to churn during the merger, something widely believed to be difficult or impossible. We evaluate the algorithm for various scenarios and show that even when falsely detecting a merger, the algorithm quickly terminates and does not clutter the network with many messages. The algorithm is flexible as the tradeoff between message complexity and time complexity can be adjusted by a parameter.
-
key based consistency and availability in Structured Overlay networks
High Performance Distributed Computing, 2008Co-Authors: Tallat M. Shafaat, Ali Ghodsi, Seif Haridi, Thorsten Schutt, Monika Moser, Alexander ReinefeldAbstract:Structured Overlay Networks (SONs) provide a promising platform for high performance applications since they are scalable, fault-tolerant and self-managing. SONs provide lookup services that map keys to nodes that can be used as processing or storage resources. In SONs, lookups for a key may return inconsistent results. Consequently, it is difficult to provide consistent data services on top of SONs that build on key-based search. In this paper, we study the frequency of occurrence of inconsistent lookups. We show that the affect of lookup inconsistencies can be reduced by using node responsibilities. We present our results as a trade-off between consistency and availability of keys.
-
on consistency of data in Structured Overlay networks
CoreGRID Integration Workshop 2008 Hersonissos GREECE APR 02-04 2008, 2008Co-Authors: Tallat M. Shafaat, Ali Ghodsi, Seif Haridi, Thorsten Schutt, Monika Moser, Alexander ReinefeldAbstract:Data consistency can be violated in Distributed Hash Tables (DHTs) due to inconsistent lookups. In this paper, we identify the events leading to inconsistent lookups and inconsistent responsibilities for a key. We find the inaccuracy of failure detectors as the main reason for inconsistencies. By simulations with inaccurate failure detectors, we study the probability of reaching a system configuration which may lead to inconsistent data. We analyze majority-based algorithms for operations on replicated data. To ensure that concurrent operations do not violate consistency, they have to use non-disjoint sets of replicas. We analytically derive the probability of concurrent operations including disjoint replica sets. By combining the simulation and analytical results, we show that the probability for a violation of data consistency is negligibly low for majority-based algorithms in DHTs.
-
an analytical study of a Structured Overlay in the presence of dynamic membership
arXiv: Networking and Internet Architecture, 2007Co-Authors: Supriya Krishnamurthy, Sameh Elansary, Erik Aurell, Seif HaridiAbstract:In this paper we present an analytical study of dynamic membership (aka churn) in Structured peer-to-peer networks. We use a fluid model approach to describe steady-state or transient phenomena, and apply it to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately account for the functional form of the probability of network disconnection as well as the fraction of failed or incorrect successor and finger pointers. We show how we can use these quantities to predict both the performance and consistency of lookups under churn. All theoretical predictions match simulation results. The analysis includes both features that are generic to Structured Overlays deploying a ring as well as Chord-specific details, and opens the door to a systematic comparative analysis of, at least, ring-based Structured Overlay systems under churn.
Kazuyuki Shudo - One of the best experts on this subject based on the ideXlab platform.
-
detouring skip graph a Structured Overlay utilizing detour routes
Consumer Communications and Networking Conference, 2020Co-Authors: Takeshi Kaneko, Yusuke Aoki, Kazuyuki Shudo, Ryohei Banno, Kota Abe, Yuuichi TeranishiAbstract:Skip Graph, one of the Structured Overlays, provides a scalable network owing to the routing path lengths of O (log n), where $n$ denotes the total number of nodes. However, there is a problem that most of the routing paths are quite longer than the shortest paths because each node in the network knows only its neighbors, rather than the global topology. In general, long routing paths lead to long delay times and low fault tolerance. Herein, we propose Detouring Skip Graph, which shortens the path lengths through the use of detour routes. It does not require construction of extra links or modification of its topology; thereby, it can succeed in shortening them while maintaining the advantages of Skip Graph. The evaluation experiments show that the average path length was shortened by approximately 20%-30% in comparison with Skip Graph.
-
skip suffix array a partial match retrieval method on Structured Overlay networks
International Conference on Information Networking, 2020Co-Authors: Ryohei Banno, Kazuyuki ShudoAbstract:Structured Overlay networks provide superior scalability and robustness suitable for large scale distributed systems. However, typical algorithms’ ability to handle complex queries is limited; consequently, their range of applications is also limited. We propose a partial match retrieval method for Structured Overlay networks that we refer to as Skip Suffix Array (SSA). SSA integrates the concept of suffix arrays with Skip Graph, which is a distributed range-queriable data structure. In addition, we introduce a unique routing method for delivering partial match queries. SSA achieves lower communication cost and better load balancing compared to some existing methods for partial match retrieval, as well as its search time is suppressed to O(log N) where N is the number of nodes. Experimental results demonstrate that SSA can reduce the average path length and the average number of messages by more than 85% compared to existing methods, under experimental conditions with 10, 000 nodes and search words of length 8.
-
ballistic skip graph a skip graph style constant degree Structured Overlay
International Symposium on Computers and Communications, 2018Co-Authors: Yusuke Aoki, Masaaki Ohnishi, Kazuyuki ShudoAbstract:Structured Overlays enable the construction of application-level networks from multiple nodes, and the decentralized searching of data in the network. One such Structured Overlay is the skip graph, which supports range queries. Each node in a skip graph has multi-level shortcut links. The degree of each node is O(log N) on a network with N nodes. The paper, proposes Ballistic Skip Graph, a Structured Overlay that reduces the degree of each node to O(1) by limiting the number of shortcut links to a randomly selected single level while supporting range queries. Because the nodes are not grouped, the proposed method requires no extensive reconfiguration of the network when nodes join or leave. An evaluation experiment confirmed that the average routing table size is confined to a small constant.
-
frt skip graph a skip graph style Structured Overlay based on flexible routing tables
International Symposium on Computers and Communications, 2016Co-Authors: Masashi Hojo, Ryohei Banno, Kazuyuki ShudoAbstract:Structured Overlays enable a number of nodes to construct a logical network autonomously and search each other. Skip Graph, one of the Structured Overlays, constructs an Overlay network based on Skip List structure and supports range queries for keys. Skip Graph manages routing tables based on random digits; therefore, the deviation of them disturbs effective utilization of the routing table entries and increases path length than the ideal value. We therefore propose FRT-Skip Graph, a novel Structured Overlay that solves the issues of Skip Graph and provides desirable features not in Skip Graph. FRT-Skip Graph is designed based on Flexible Routing Tables and supports range queries similarly to Skip Graph. Furthermore, it provides features derived from FRT, namely, dynamic routing table size and high extensibility.
-
self refining skip graph a Structured Overlay approaching to ideal skip graph
COMPSAC Workshops, 2016Co-Authors: Takafumi Kawaguchi, Ryohei Banno, Masashi Hojo, Kazuyuki ShudoAbstract:In Skip Graph, each node constructs its routing table by choosing neighbor nodes based on its membership vector when a node joins or leaves. However, membership vectors are determined randomly, so nodes do not always compose an ideal topology of Skip Graph. This causes route length to be long. Therefore, we propose Self-Refining Skip Graph, a Structured Overlay where each node refines its routing table for an ideal topology of Skip Graph. Our proposed method shows shorter route length as approaching to an ideal topology while keeping the robustness caused by membership vectors. We confirmed in the evaluation that the topology approaches to an ideal one and the route length becomes shorter than Skip Graph.
Dongsheng Wang - One of the best experts on this subject based on the ideXlab platform.
-
twins 2 hop Structured Overlay with high scalability
International Conference on Computational Science, 2004Co-Authors: Haitao Dong, Weimin Zheng, Dongsheng WangAbstract:How to build an efficient P2P Overlay network on a large-scale system is still in the air. Pastry-like p2p Overlays have low maintenance costs because of their log(N)-sized routing tables. However their lookup efficiency is quite low. One-hop Overlays, although having high routing efficiency, can not scale to large systems because of its high maintenance cost. In this paper, we present a novel Structured Overlay network, Twins. Routing in Twins can be accomplished in 2 hops in very high probability. With a report-based multicast maintenance algorithm, the Overlay network consumes very low maintenance cost in presence of large-scale and highly dynamic network environments. The experimental results indicate that, when the system running over a network of 5,000,000 peers, each peer consumes only 6 messages per second for maintenance, and the routing latency is only 2 hops in a very high probability of 0.99.
-
janus build gnutella like file sharing system over Structured Overlay
Lecture Notes in Computer Science, 2004Co-Authors: Haitao Dong, Weimin Zheng, Dongsheng WangAbstract:How to build an efficient and scalable p2p file sharing system is still an open question. Structured systems obtain O(log(N)) lookup upper bound by associating content with node, But they can not supporting complex queries. On the other hand, Gnutella-like unStructured systems support complex queries, but because of its random-graph topology and its flooding content discovery mechanism, it can not scale to large network systems. In this paper, we present Janus, which build unStructured file sharing system over Structured Overlay. Different from previous approaches, Janus keeps bidirectional links in its routing table. And with one-hop replication and biased random walk Janus make it possible to implement complex queries in the scalable manner. The experimental results indicate that, when the system running over a network of 10,000 peers, it only needs 100 hops to search half of the total system.
-
gemini probabilistic routing algorithm in Structured p2p Overlay
Lecture Notes in Computer Science, 2004Co-Authors: Haitao Dong, Dongsheng Wang, Weimin ZhengAbstract:In this paper, we propose a new Structured Overlay protocol, which is more efficient and scalable than previous ones. We call it Gemini, because its routing table consists of two parts, one containing nodes with common prefix and the other containing nodes with common suffix. Gemini routes messages to their destinations in just 2 hops, with a very high probability of 0.99. When running in a p2p network of 5,000,000 peers, each Gemini node consumes only 6 messages per second for maintenance. This cost, as well as routing table size, varies as a O (N) function to the Overlay scale, so Gemini can also run well in an even larger environment.
Haitao Dong - One of the best experts on this subject based on the ideXlab platform.
-
twins 2 hop Structured Overlay with high scalability
International Conference on Computational Science, 2004Co-Authors: Haitao Dong, Weimin Zheng, Dongsheng WangAbstract:How to build an efficient P2P Overlay network on a large-scale system is still in the air. Pastry-like p2p Overlays have low maintenance costs because of their log(N)-sized routing tables. However their lookup efficiency is quite low. One-hop Overlays, although having high routing efficiency, can not scale to large systems because of its high maintenance cost. In this paper, we present a novel Structured Overlay network, Twins. Routing in Twins can be accomplished in 2 hops in very high probability. With a report-based multicast maintenance algorithm, the Overlay network consumes very low maintenance cost in presence of large-scale and highly dynamic network environments. The experimental results indicate that, when the system running over a network of 5,000,000 peers, each peer consumes only 6 messages per second for maintenance, and the routing latency is only 2 hops in a very high probability of 0.99.
-
janus build gnutella like file sharing system over Structured Overlay
Lecture Notes in Computer Science, 2004Co-Authors: Haitao Dong, Weimin Zheng, Dongsheng WangAbstract:How to build an efficient and scalable p2p file sharing system is still an open question. Structured systems obtain O(log(N)) lookup upper bound by associating content with node, But they can not supporting complex queries. On the other hand, Gnutella-like unStructured systems support complex queries, but because of its random-graph topology and its flooding content discovery mechanism, it can not scale to large network systems. In this paper, we present Janus, which build unStructured file sharing system over Structured Overlay. Different from previous approaches, Janus keeps bidirectional links in its routing table. And with one-hop replication and biased random walk Janus make it possible to implement complex queries in the scalable manner. The experimental results indicate that, when the system running over a network of 10,000 peers, it only needs 100 hops to search half of the total system.
-
gemini probabilistic routing algorithm in Structured p2p Overlay
Lecture Notes in Computer Science, 2004Co-Authors: Haitao Dong, Dongsheng Wang, Weimin ZhengAbstract:In this paper, we propose a new Structured Overlay protocol, which is more efficient and scalable than previous ones. We call it Gemini, because its routing table consists of two parts, one containing nodes with common prefix and the other containing nodes with common suffix. Gemini routes messages to their destinations in just 2 hops, with a very high probability of 0.99. When running in a p2p network of 5,000,000 peers, each Gemini node consumes only 6 messages per second for maintenance. This cost, as well as routing table size, varies as a O (N) function to the Overlay scale, so Gemini can also run well in an even larger environment.
