共查询到20条相似文献,搜索用时 609 毫秒
1.
Synchronous Byzantine quorum systems 总被引:2,自引:0,他引:2
Rida A. Bazzi 《Distributed Computing》2000,13(1):45-52
Summary. Quorum systems have been used to implement many coordination problems in distributed systems such as mutual exclusion, data
replication, distributed consensus, and commit protocols. Malkhi and Reiter recently proposed quorum systems that can tolerate
Byzantine failures; they called these systems Byzantine quorum systems and gave some examples of such quorum systems. In this
paper, we propose a new definition of Byzantine quorums that is appropriate for synchronous systems. We show how these quorums
can be used for data replication and propose a general construction of synchronous Byzantine quorums using standard quorum
systems. We prove tight lower bounds on the load of synchronous Byzantine quorums for various patterns of failures and we
present synchronous Byzantine quorums that have optimal loads that match the lower bounds for two failure patterns.
Received: June 1998 / Accepted: August 1999 相似文献
2.
Byzantine quorum systems 总被引:12,自引:0,他引:12
Summary. Quorum systems are well-known tools for ensuring the consistency and availability of replicated data despite the benign failure
of data repositories. In this paper we consider the arbitrary (Byzantine) failure of data repositories and present the first
study of quorum system requirements and constructions that ensure data availability and consistency despite these failures.
We also consider the load associated with our quorum systems, i.e., the minimal access probability of the busiest server.
For services subject to arbitrary failures, we demonstrate quorum systems over servers with a load of , thus meeting the lower bound on load for benignly fault-tolerant quorum systems. We explore several variations of our quorum
systems and extend our constructions to cope with arbitrary client failures.
Received: October 1996 / Accepted June 1998 相似文献
3.
纠错码拜占庭容错Quorum中错误检测机制 总被引:3,自引:0,他引:3
摘要在大规模存储系统中,拜占庭存储节点的容错显得越来越重要。传统拜占庭Quorum通过复制可以容忍拜占庭失效,但是它们有两个主要缺点:低的存储空间利用率和静态quorum参数。我们提出纠错码拜占庭容错Quorum(Erasure-code Byzantine Fault-tolerance Quorum, E-BFQ),E-BFQ采用纠错码作为冗余策略,可以提供高可靠性,同时比复制占用更少存储空间。通过客户端读/写操作和管理器诊断操作,E-BFQ可以检测拜占庭节点,动态调整系统规模和故障闽值。结果显示本文方法可以达到动态调整的目的。 相似文献
4.
Yuh-Jzer Joung 《Distributed Computing》2002,15(3):155-175
Summary. Group mutual exclusion occurs naturally in situations where a resource can be shared by processes of the same group, but
not by processes of different groups. For example, suppose data is stored in a CD-jukebox. Then when a disc is loaded for
access, users that need data on the disc can concurrently access the disc, while users that need data on a different disc
have to wait until the current disc is unloaded.
The design issues for group mutual exclusion have been modeled as the Congenial Talking Philosophers problem, and solutions for shared-memory models have been proposed [12,14]. As in ordinary mutual exclusion and many other
problems in distributed systems, however, techniques developed for shared memory do not necessary apply to message passing
(and vice versa). So in this paper we investigate solutions for Congenial Talking Philosophers in computer networks where
processes communicate by asynchronous message passing. We first present a solution that is a straightforward adaptation from
Ricart and Agrawala's algorithm for ordinary mutual exclusion. Then we show that the simple modification suffers a severe
performance degradation that could cause the system to behave as though only one process of a group can be in the critical
section at a time. We then present a more efficient and highly concurrent distributed algorithm for the problem, the first
such solution in computer networks.
Received: August 2000 / Accepted: November 2001 相似文献
5.
Yu-Chen Kuo 《Computer Networks》2010,54(11):1911-1922
The asynchronous PS (Power-Saving) unicast protocol was designed for two PS wireless hosts to transmit the unicast message in the ad hoc network even their clocks are asynchronous. However, as regard to transmit a multicast message among more than two PS hosts, the protocol could not guarantee that all PS hosts can wake up at the same time. Some PS hosts may be in the PS mode when the multicast message is transmitted. Thus, the multicast message should be retransmitted again and again until all PS hosts receive the message. It will increase the energy consumption and the usage of the bandwidth. In this paper, we propose quorum-based PS multicast protocols for PS hosts to transmit multicast messages in the asynchronous ad hoc network. In those protocols, PS hosts use quorums to indicate their wakeup patterns. We introduce the rotation m-closure property to guarantee that m different quorums have the intersection even quorums are rotated due to asynchronous clocks. Thus, m PS hosts adopting m quorums satisfying the rotation m-closure property could wake up simultaneously and receive the multicast message even their clocks are asynchronous. We propose two quorum systems named the uniform k-arbiter and the CRT (Chinese Remainder Theorem) quorum system, which satisfy the rotation m-closure property. As shown in our analysis results, our quorum-based PS multicast protocols adopting those quorum systems can save more energy to transmit multicast messages. 相似文献
6.
Summary. A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the
area of distributed systems, including mutual exclusion, data replication and dissemination of information. In this paper
we introduce a general class of quorum systems called Crumbling Walls and study its properties. The elements (processors) of a wall are logically arranged in rows of varying widths. A quorum in a wall is the union of one full row and a representative from every row below the full row. This class considerably
generalizes a number of known quorum system constructions. The best crumbling wall is the CWlog quorum system. It has small
quorums, of size O(lg n), and structural simplicity. The CWlog has optimal availability and optimal load among systems with such small quorum size.
It manifests its high quality for all universe sizes, so it is a good choice not only for systems with thousands or millions of processors but also for systems
with as few as 3 or 5 processors. Moreover, our analysis shows that the availability will increase and the load will decrease
at the optimal rates as the system increases in size.
Received: August 1995 / Accepted: August 1996 相似文献
7.
It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of
asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is
no contention. This paper initiates the first study of quorum systems that help design such implementations by encompassing,
at the same time, optimal resilience, as well as optimal best-case complexity. We introduce the notion of a refined quorum system (RQS) of some set S as a set of three classes of subsets (quorums) of S: first class quorums are also second class quorums, themselves being also third class quorums. First class quorums have large
intersections with all other quorums, second class quorums typically have smaller intersections with those of the third class,
the latter simply correspond to traditional quorums. Intuitively, under uncontended and synchronous conditions, a distributed
object implementation would expedite an operation if a quorum of the first class is accessed, then degrade gracefully depending
on whether a quorum of the second or the third class is accessed. Our notion of refined quorum system is devised assuming
a general adversary structure, and this basically allows algorithms relying on refined quorum systems to relax the assumption
of independent process failures, often questioned in practice. We illustrate the power of refined quorums by introducing two
new optimal Byzantine-resilient distributed object implementations: an atomic storage and a consensus algorithm. Both match
previously established resilience and best-case complexity lower bounds, closing open gaps, as well as new complexity bounds
we establish here. Each of our algorithms is representative of a different class of architectures, highlighting the generality
of the refined quorum abstraction. 相似文献
8.
Stefan Manegold Peter A. Boncz Martin L. Kersten 《The VLDB Journal The International Journal on Very Large Data Bases》2000,9(3):231-246
In the past decade, advances in the speed of commodity CPUs have far out-paced advances in memory latency. Main-memory access
is therefore increasingly a performance bottleneck for many computer applications, including database systems. In this article,
we use a simple scan test to show the severe impact of this bottleneck. The insights gained are translated into guidelines
for database architecture, in terms of both data structures and algorithms. We discuss how vertically fragmented data structures
optimize cache performance on sequential data access. We then focus on equi-join, typically a random-access operation, and
introduce radix algorithms for partitioned hash-join. The performance of these algorithms is quantified using a detailed analytical
model that incorporates memory access cost. Experiments that validate this model were performed on the Monet database system.
We obtained exact statistics on events such as TLB misses and L1 and L2 cache misses by using hardware performance counters
found in modern CPUs. Using our cost model, we show how the carefully tuned memory access pattern of our radix algorithms
makes them perform well, which is confirmed by experimental results.
Received April 20, 2000 / Accepted June 23, 2000 相似文献
9.
Abstract. In this paper we study the ability of shared object types to implement Consensus in asynchronous shared-memory systems where
at most one process may crash. More specifically, we consider the following question: Let and be a set of object types that can be used to solve one-resilient Consensus among n processes. Can always be used to solve one-resilient Consensus among n - 1 processes? We prove that for n = 3 the answer is negative, even if consists only ofdeterministic types. (This strengthens an earlier result by the first author proving the same fact for nondeterministic types.) We also prove that, in contrast, for the answer to the above question is affirmative.
Received: July 1997 / Accepted: May 2000 相似文献
10.
Failure detection and consensus in the crash-recovery model 总被引:2,自引:0,他引:2
Summary. We study the problems of failure detection and consensus in asynchronous systems in which processes may crash and recover,
and links may lose messages. We first propose new failure detectors that are particularly suitable to the crash-recovery model.
We next determine under what conditions stable storage is necessary to solve consensus in this model. Using the new failure
detectors, we give two consensus algorithms that match these conditions: one requires stable storage and the other does not.
Both algorithms tolerate link failures and are particularly efficient in the runs that are most likely in practice – those
with no failures or failure detector mistakes. In such runs, consensus is achieved within time and with 4 n messages, where is the maximum message delay and n is the number of processes in the system.
Received: May 1998 / Accepted: November 1999 相似文献
11.
Munetoshi Ishikawa Koji Hasebe Akiyoshi Sugiki Kazuhiko Kato 《Service Oriented Computing and Applications》2010,4(4):245-260
Power-saving has become a central issue for well-configured SOC platforms. In particular, as a high percentage of the total
energy is used by the storage systems, the cost effectiveness of data management is equally as important as reliability and
availability. To address this issue, we propose the dynamic grid quorum as a method for reducing the power consumption of
large-scale distributed storage systems. The basic principle of our approach is to skew the workload toward a small number
of quorums. This can be realized using the following three techniques. First, our system allows reconfiguration by exchanging
nodes without any data migration, so that high-capacity nodes can be reallocated to busier quorums. Second, for more effective
skewing of the workload, we introduce the notion of dual allocation, which makes it possible to consider two distinct allocations
in the same grid for write and read quorums. Finally, we present an optimization algorithm to find a pair of a strategy and
an allocation of nodes, which minimizes power for a given system setting and its workload. We also demonstrate that the dynamic
grid quorum saves, on average, 14–25% energy compared with static configurations, when the intensity of the total workload
changes. 相似文献
12.
The GMAP: a versatile tool for physical data independence 总被引:1,自引:0,他引:1
Odysseas G. Tsatalos Marvin H. Solomon Yannis E. Ioannidis 《The VLDB Journal The International Journal on Very Large Data Bases》1996,5(2):101-118
Physical data independence is touted as a central feature of modern
database systems. It allows users to frame queries in terms of the logical
structure of the data, letting a query processor automatically translate
them into optimal plans that access physical storage structures. Both
relational and object-oriented systems, however, force users to frame their
queries in terms of a logical schema that is directly tied to physical
structures. We present an approach that eliminates this dependence. All
storage structures are defined in a declarative language based on
relational algebra as functions of a logical schema. We present an
algorithm, integrated with a conventional query optimizer, that translates
queries over this logical schema into plans that access the storage
structures. We also show how to compile update requests into plans that
update all relevant storage structures consistently and optimally.
Finally, we report on experiments with a prototype implementation of our
approach that demonstrate how it allows storage structures to be tuned to
the expected or observed workload to achieve significantly better
performance than is possible with conventional techniques.
Edited by
Matthias Jarke, Jorge Bocca, Carlo Zaniolo. Received
September 15, 1994 / Accepted September 1, 1995 相似文献
13.
Asynchronous group mutual exclusion 总被引:1,自引:1,他引:0
Yuh-Jzer Joung 《Distributed Computing》2000,13(4):189-206
Abstract. Mutual exclusion and concurrency are two fundamental and essentially opposite features in distributed systems. However, in
some applications such as Computer Supported Cooperative Work (CSCW) we have found it necessary to impose mutual exclusion
on different groups of processes in accessing a resource, while allowing processes of the same group to share the resource.
To our knowledge, no such design issue has been previously raised in the literature. In this paper we address this issue by
presenting a new problem, called Congenial Talking Philosophers, to model group mutual exclusion. We also propose several criteria to evaluate solutions of the problem and to measure their
performance. Finally, we provide an efficient and highly concurrent distributed algorithm for the problem in a shared-memory
model where processes communicate by reading from and writing to shared variables. The distributed algorithm meets the proposed
criteria, and has performance similar to some naive but centralized solutions to the problem.
Received: November 1998 / Accepted: April 2000 相似文献
14.
The goal of decentralized consensus protocols is to exchange information among nodes so that each node acquires the information
held by every other node in the system. This paper presents a quorum-based, self-stabilizing maxima finding protocol which
is based on a decentralized consensus protocol. The protocol exchanges information with less delay than existing ring-based,
self-stablizing protocols. Furthermore, quorums can be composed, and the resulting composite quorums can be used to efficiently
obtain a solution for any internetwork.
Received: October 1999 / Accepted: June 2001 相似文献
15.
Efficient similarity search for market basket data 总被引:2,自引:0,他引:2
Alexandros Nanopoulos Yannis Manolopoulos 《The VLDB Journal The International Journal on Very Large Data Bases》2002,11(2):138-152
Several organizations have developed very large market basket databases for the maintenance of customer transactions. New
applications, e.g., Web recommendation systems, present the requirement for processing similarity queries in market basket
databases. In this paper, we propose a novel scheme for similarity search queries in basket data. We develop a new representation
method, which, in contrast to existing approaches, is proven to provide correct results. New algorithms are proposed for the
processing of similarity queries. Extensive experimental results, for a variety of factors, illustrate the superiority of
the proposed scheme over the state-of-the-art method.
Edited by R. Ng. Received: August 6, 2001 / Accepted: May 21, 2002 Published online: September 25, 2002 相似文献
16.
We suggest a method of controlling the access to a secure database via quorum systems. A quorum system is a collection of sets (quorums) every two of which have a nonempty intersection. Quorum systems have been used for a number of applications in the area of distributed systems. We propose a separation between access servers, which are protected and trustworthy, but may be outdated, and the data servers, which may all be compromised. The main paradigm is that only the servers in a complete quorum can collectively grant (or revoke) access permission. The method we suggest ensures that, after authorization is revoked, a cheating user Alice will not be able to access the data even if many access servers still consider her authorized and even if the complete raw database is available to her. The method has a low overhead in terms of communication and computation. It can also be converted into a distributed system for issuing secure signatures. An important building block in our method is the use of secret sharing schemes that realize the access structures of quorum systems. We provide several efficient constructions of such schemes which may be of interest in their own right 相似文献
17.
Jan Friso Groote Wim H. Hesselink Sjouke Mauw Rogier Vermeulen 《Distributed Computing》2001,14(2):75-81
Summary. The problem of using P processes to write a given value to all positions of a shared array of size N is called the Write-All problem. We present and analyze an asynchronous algorithm with work complexity , where (assuming and ). Our algorithm is a generalization of the naive two-processor algorithm where the two processes each start at one side of
the array and walk towards each other until they collide.
Received: October 1999 / Accepted: September 2000 相似文献
18.
Xiaohua Kong Radu Negulescu Larry Weidong Ying 《International Journal on Software Tools for Technology Transfer (STTT)》2003,4(3):359-370
In this paper we propose a refinement-based technique to formally verify data transfer in a heterogeneous timing framework.
Novel data transfer models are proposed to represent data communication between two locally independent clock domains via
an asynchronous handshake environment. As a case study, we apply our technique to automatically verify data transfer in a
previously published architecture for globally asynchronous locally synchronous on-chip systems. In this case study, we find
several race conditions, hazards, and other dangers that were not mentioned in the original publication, and we find additional
delay constraints that avoid some of the detected dangers.
Published online: 17 December 2002 相似文献
19.
Laura M. Haas Michael J. Carey Miron Livny Amit Shukla 《The VLDB Journal The International Journal on Very Large Data Bases》1997,6(3):241-256
In this paper, we re-examine the results of prior work on methods for computing ad hoc joins. We develop a detailed cost model for predicting join algorithm performance, and we use the model to develop cost formulas
for the major ad hoc join methods found in the relational database literature. We show that various pieces of “common wisdom” about join algorithm
performance fail to hold up when analyzed carefully, and we use our detailed cost model to derive op
timal buffer allocation schemes for each of the join methods examined here. We show that optimizing their buffer allocations
can lead to large performance improvements, e.g., as much as a 400% improvement in some cases. We also validate our cost model's
predictions by measuring an actual implementation of each join algorithm considered. The results of this work should be directly
useful to implementors of relational query optimizers and query processing systems.
Edited by M. Adiba. Received May 1993 / Accepted April 1996 相似文献
20.
Gerd Schürmann 《Multimedia Systems》1996,4(5):281-295
Electronic mail for traditional text exchange as asynchronous communication means between computer users is widely built upon
in many application areas. Whereas Multimedia-Mail systems – including text, graphics, still images, audio, video and documents
– were limited to isolated communities – at least two very promising approaches are being under development: the MIME (Multipurpose
Internet Mail Extension), an extension of Internet Mail as well as the Multimedia Teleservice based on CCITT Recommendation
X.400(88) being under development within the BERKOM project funded by the German TELEKOM. The store-and-forward mechanism
inherent to electronic mail is complemented in the later one by an additional exchange mechanism allowing the resolution of
references to message content, e.g. video. Such references may be put into a message in place of the content itself. Internet/MIME
and OSI/X.400, their interworking, asynchronous information server access via Multimedia-Mail, as well as possible future
developments especially in the area of asynchronous Computer Supported Cooperative Work (CSCW) are discussed. 相似文献