检索结果-内蒙古大学图书馆

A token-based distributed group mutual exclusion algorithm with quorums

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2008年第9期19卷 1153-1166页

作者： Kakugawa, Hirotsugu Kamei, Sayaka Masuzawa, Toshimitsu Osaka Univ Grad Sch Informat Sci & Technol Osaka 5608531 Japan Hiroshima Univ Dept Informat Engn Grad Sch Engn Higashi Ku Hiroshima 7398527 Japan

The group mutual exclusion problem is a generalization of mutual exclusion problem such that a set of processes in the same group can enter a critical section simultaneously. In this paper, we propose a distributed algorithm for the group mutual exclusion problem in asynchronous message passing distributed systems. Our algorithm is based on tokens, and a process that obtains a token can enter a critical section. To reduce message complexity, it uses a coterie as a communication structure when a process sends a request messages. Informally, a coterie is a set of quorums, each of which is a subset of the process set, and any two quorums share at least one process. The message complexity of our algorithm is O(vertical bar Q vertical bar) in the worst case, where vertical bar Q vertical bar is a quorum size that the algorithm adopts. Performance of the proposed algorithm is presented by analysis and discrete event simulation. In particular, the proposed algorithm achieves high concurrency, which is a performance measure for the number of processes that can be in a critical section simultaneously.

关键词： distributed systems distributed data structures mutual exclusion synchronization

来源：评论

学校读者我要写书评

暂无评论

Using a distributed quadtree index in peer-to-peer networks

引用

VLDB JOURNAL 2007年第2期16卷 165-178页

作者： Tanin, Egemen Harwood, Aaron Samet, Hanan Univ Melbourne Dept Comp Sci & Software Engn NICTA Victoria Lab Melbourne Vic 3010 Australia Univ Maryland Inst Adv Comp Studies Ctr Automat Res Dept Comp Sci College Pk MD 20742 USA

Peer-to-peer (P2P) networks have become a powerful means for online data exchange. Currently, users are primarily utilizing these networks to perform exact-match queries and retrieve complete files. However, future more data intensive applications, such as P2P auction networks, P2P job-search networks, P2P multiplayer games, will require the capability to respond to more complex queries such as range queries involving numerous data types including those that have a spatial component. In this paper, a distributed quadtree index that adapts the MX-CIF quadtree is described that enables more powerful accesses to data in P2P networks. This index has been implemented for various prototype P2P applications and results of experiments are presented. Our index is easy to use, scalable, and exhibits good load-balancing properties. Similar indices can be constructed for various multidimensional data types with both spatial and non-spatial components.

关键词： quadtrees spatial data structures distributed data structures peer-to-peer networks

来源：评论

学校读者我要写书评

暂无评论

LH*g: A high-availability scalable distributed data structure by record grouping

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND data ENGINEERING 2002年第4期14卷 923-927页

作者： Litwin, W Risch, T Univ Paris 09 F-75775 Paris 16 France Univ Uppsala S-75105 Uppsala Sweden

LH*g is a high-availability extension of the LH* Scalable distributed data Structure. An LH*g file scales up with constant key search and insert performance, while surviving any single-site unavailability (failure). We achieve high-availability through a new principle of record grouping. A group is a logical structure of up to k records, where k is a file parameter. Every group contains a parity record allowing for the reconstruction of an unavailable member. The basic scheme may be generalized to support the unavailability of any number of sites, at the expense of storage and messaging. Other known high-availability schemes are static, or require more storage, or provide worse search performance.

关键词： scalability distributed systems distributed data structures high-availability fault tolerance parallelism multicomputers

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic distributed search trees can be balanced in O(lg² N) time

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2002年第11期62卷 1617-1628页

作者： Barillari, F Nardelli, E Pepe, M Univ Aquila Dipartimento Informat I-67010 Coppito Italy Univ Aquila Dipartimento Matemat Pura & Applicata I-67010 Coppito Italy CNR Ist Analisi Sistemi & Informat I-00185 Rome Italy

In this paper we consider the dictionary problem in a message-passing distributed environment. We introduce a new version, based on AVL-trees, of distributed search trees, the first to be fully scalable, that is, able to both grow and shrink as long as keys are inserted and deleted. We prove that in the worst case a key can be inserted, searched, or deleted with O(lg(2) N) messages. We show that for the introduced distributed search tree this bound is tight. Since the defined structure maintains the relative order of the keys, it can also support queries that refer to the linear order of keys, such as nearest neighbor or range queries. (C) 2002 Published by Elsevier Science (USA).

关键词： scalability distributed data structures distributed memory machines

来源：评论

学校读者我要写书评

暂无评论

SPARSE-MATRIX COMPUTATIONS ON PARALLEL PROCESSOR ARRAYS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 1993年第3期14卷 519-530页

作者： OGIELSKI, AT AIELLO, W

This paper investigates the balancing of distributed compressed storage of large sparse matrices on a massively parallel computer. For fast computation of matrix-vector and matrix-matrix products on a rectangular processor array with efficient communications along its rows and columns it is required that the nonzero elements of each matrix row or column be distributed among the processors located within the same array row or column, respectively. Randomized packing algorithms are constructed with such properties, and it is proved that with high probability the algorithms produce well-balanced storage for sufficiently large matrices with bounded number of nonzeros in each row and column, but no other restrictions on structure. Then basic matrix-vector multiplication routines are described with fully parallel interprocessor communications and intraprocessor gather and scatter operations. Their efficiency is demonstrated on the 16,384-processor MasPar computer.

关键词： distributed data structures LINEAR ALGEBRA LOAD BALANCING PARALLEL ALGORITHMS RANDOMIZED ALGORITHMS SPARSE MATRICES

来源：评论

学校读者我要写书评

暂无评论

Index Recommendation Tool for Optimized Information Discovery over distributed Hash Tables

Index Recommendation Tool for Optimized Information Discover...

引用

35th Annual IEEE Conference on Local Computer Network (LCN)

作者： Memon, Faraz Duerr, Frank Rothermel, Kurt Univ Stuttgart IPVS Distributed Syst Dept Univ Str 38 D-70569 Stuttgart Germany

ISBN: (纸本)9781424483891

Peer-to-peer (P2P) networks allow for efficient information discovery in large-scale distributed systems. Although point queries are well supported by current P2P systems -in particular systems based on distributed hash tables (DHTs) -, providing efficient support for more complex queries remains a challenge. Our research focuses on the efficient support for multi-attribute range (MAR) queries over DHT-based information discovery systems. Traditionally, the support for MAR queries over DHTs has been provided either by creating an individual index for each data attribute or by creating a single index using the combination of all data attributes. In contrast to these approaches, we propose to create a set of indices over selected attribute combinations. In order to limit the overhead induced by index maintenance, the total number of created indices has to be limited. Thus, the resulting problem is to create a limited number of indices such that the overall system performance is optimal for MAR queries. In this paper, we propose an index recommendation tool that implements heuristic solutions to this NP-hard problem. Our evaluations show that these heuristics lead to a close-to-optimal system performance for MAR queries.

关键词： distributed networks Indexing methods distributed data structures Hash-table representations

来源：评论

学校读者我要写书评

暂无评论

A hierarchy-based fault-local stabilizing algorithm for tracking in sensor networks

引用

8th International Conference on Principles of distributed Systems (OPODIS 2004)

作者： Demirbas, M Arora, A Nolte, T Lynch, N Ohio State Univ Columbus OH 43210 USA MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

ISBN: (纸本)3540273247

In this paper, we introduce the concept of hierarchy-based fault-local stabilization and a novel self-healing/fault-containment technique and apply them in STALK. STALK is an algorithm for tracking in sensor networks that maintains a data structure on top of an underlying hierarchical partitioning of the network. Starting from an arbitrarily corrupted state, STALK satisfies its specification within time and communication cost proportional to the size of the faulty region, defined in terms of levels of the hierarchy where faults have occurred. This local stabilization is achieved by slowing propagation of information as the levels of the hierarchy underlying STALK increase, enabling more recent information propagated by lower levels to override misinformation at higher levels before the misinformation is propagated more than a constant number of levels. In addition, this stabilization is achieved without reducing the efficiency or availability of the data structure when faults don't occur: 1) Operations to find the mobile object distance d away take 0(d) time and communication to complete, 2) Updates to the tracking structure after the object has moved a total of d distance take O(d*log network diameter) amortized time and communication to complete, 3) The tracked object may relocate without waiting for STALK to complete updates resulting from prior moves, and 4) The mobile object can move while a find is in progress.

关键词： sensor networks self-stabilization fault-containment tracking distributed data structures

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Sublinear-Space Distance Labeling Using Hubs 16

Brief Announcement: Sublinear-Space Distance Labeling Using ...

引用

35th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing (PODC)

作者： Gawrychowski, Pawel Kosowski, Adrian Uznanski, Przemyslaw Univ Warsaw Inst Informat PL-00325 Warsaw Poland Paris Diderot Univ Inria Paris France Paris Diderot Univ IRIF Paris France Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Aalto Univ Espoo Finland

ISBN: (纸本)9781450339643

A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. We propose a series of new labeling schemes within the framework of so-called hub labeling (HL, also known as landmark labeling or 2-hop-cover labeling), in which each node u stores its distance to all nodes from an appropriately chosen set of hubs S(u) subset of V. For a queried pair of nodes (u, v), the length of a shortest u v-path passing through a hub node from S(u)boolean AND S(v) is then used as an upper bound on the distance between u and v. We present a hub labeling which allows us to decode exact distances in sparse graphs using labels of size sublinear in the number of nodes. For graphs with at most n nodes and average degree Delta, the tradeoff between label bit size L and query decoding time T for our approach is given by L = O(n log logo(Delta) T/ log(Delta) T), for any T <= n. Our simple approach is thus the first sublinear-space distance labeling for sparse graphs that simultaneously admits small decoding time (for constant A, we can achieve any T = omega(1) while maintaining L = o(n)), and it also provides an improvement in terms of label size with respect to previous slower approaches. By using similar techniques, we then present a 2-additive labeling scheme for general graphs, i.e., one in which the decoder provides a 2-additive-approximation of the distance between any pair of nodes. We achieve the same label size time tradeoff L = O(n log(2) log T/log T), for any T <= n. To our knowledge, this is the first additive scheme with constant absolute error to use labels of sublinear size. The corresponding decoding time is then small (any T = omega(1) is sufficient).

关键词： distributed data structures Graphs Distance Labeling Distance Oracles Algorithms

来源：评论

学校读者我要写书评

暂无评论

SKUEUE: A Scalable and Sequentially Consistent distributed Queue 32

SKUEUE: A Scalable and Sequentially Consistent Distributed Q...

引用

32nd IEEE International Parallel and distributed Processing Symposium (IPDPS)

作者： Feldmann, Michael Scheideler, Christian Setzer, Alexander Paderborn Univ Dept Comp Sci Paderborn Germany

ISBN: (纸本)9781538643686

We propose a distributed protocol for a queue, called SKUEUE, which spreads its data fairly onto multiple processes, avoiding bottlenecks in high throughput scenarios. SKUEUE can be used in highly dynamic environments, through the addition of JOIN() and LEAVE() requests to the standard queue operations ENQUEUE() and DEQUEUE(). Furthermore SKUEUE satisfies sequential consistency in the asynchronous message passing model. Scalability is achieved by aggregating multiple requests to a batch, which can then be processed in a distributed fashion without hurting the queue semantics. Operations in SKUEUE need a logarithmic number of rounds w.h.p. until they are processed, even under a high rate of incoming requests.

关键词： distributed Systems distributed data structures distributed Queue Queue Semantics

来源：评论

学校读者我要写书评

暂无评论

Privacy-Preserving Protocols for Perceptron Learning Algorithm in Neural Networks

Privacy-Preserving Protocols for Perceptron Learning Algorit...

引用

4th International IEEE Conference Intelligent Systems

作者： Samet, Saeed Miri, Ali Univ Ottawa Sch Informat Technol & Engn Ottawa ON K1N 6N5 Canada

ISBN: (纸本)9781424417391

Neural networks have become increasingly important in areas such as medical diagnosis, bio-informatics, intrusion detection, and homeland security. In most of these applications, one major issue is preserving privacy of individual's private information and sensitive data. In this paper, we propose two secure protocols for perceptron learning algorithm when input data is horizontally and vertically partitioned among the parties. These protocols can be applied in both linearly separable and non-separable datasets, while not only data belonging to each party remains private, but the final learning model is also securely shared among those parties. Parties then can jointly and securely apply the constructed model to predict the output corresponding to their target data. Also, these protocols can be used incrementally, i.e. they process new coming data, adjusting the previously constructed network.

关键词： Security and Privacy Preserving Neural Networks data Mining and Machine Learning distributed data structures

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：