共查询到20条相似文献,搜索用时 15 毫秒
1.
Summary. The Consensus problem is a fundamental paradigm for fault-tolerant asynchronous systems. It abstracts a family of problems
known as Agreement (or Coordination) problems. Any solution to consensus can serve as a basic building block for solving such
problems (e.g., atomic commitment or atomic broadcast). Solving consensus in an asynchronous system is not a trivial task: it has been proven
(1985) by Fischer, Lynch and Paterson that there is no deterministic solution in asynchronous systems which are subject to
even a single crash failure. To circumvent this impossibility result, Chandra and Toueg have introduced the concept of unreliable
failure detectors (1991), and have studied how these failure detectors can be used to solve consensus in asynchronous systems
with crash failures. This paper presents a new consensus protocol that uses a failure detector of the class . Like previous protocols, it is based on the rotating coordinator paradigm and proceeds in asynchronous rounds. Simplicity
and efficiency are the main characteristics of this protocol. From a performance point of view, the protocol is particularly
efficient when, whether failures occur or not, the underlying failure detector makes no mistake (a common case in practice).
From a design point of view, the protocol is based on the combination of three simple mechanisms: a voting mechanism, a small
finite state automaton which manages the behavior of each process, and the possibility for a process to change its mind during
a round.
Received: August 1997 / Accepted: March 1999 相似文献
2.
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 相似文献
3.
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 相似文献
4.
Rida A. Bazzi 《Distributed Computing》2001,14(1):41-48
Summary. Quorum systems have been used to implement many coordination problems in distributed systems. In this paper, we study the
cost of accessing quorums in asynchronous systems. We formally define the asynchronous access cost of quorum systems and argue
that the asynchronous access cost and not the size of a quorum is the right measure of message complexity of protocols using
quorums in asynchronous systems. We show that previous quorum systems proposed in the literature have a very high asynchronous
access cost. We propose a reformulation of the definition of Byzantine quorum systems that captures the requirement for non-blocking
access to quorums in asynchronous systems. We present new Byzantine quorum systems with low asynchronous access cost whose
other performance parameters match those of the best Byzantine quorum systems proposed in the literature. In particular, we
present a construction for the disjoint failure pattern that outperforms previously proposed systems for that pattern.
Received: September 1999 / Accepted: September 2000 相似文献
5.
Summary. For data consistency in distributed information systems, it is often necessary to compare remotely located copies of a file.
We develop several protocols for the efficient detection of differing pages in a replicated file in different communication
and failure models. The first set of protocols assumes a restricted but practical communication model. In this case, the minimum
amount of communication necessary to identify any given number of differing pages is determined and a technique to attain
this minimum is presented. For the more general communication model and for more refined failure models, we show that more
efficient protocols can be derived. Our approach is based on the theory of Galois fields.
Received: February 1996 / Accepted: September 1997 相似文献
6.
André Schiper 《Distributed Computing》1997,10(3):149-157
Summary. Consensus is one of the most fundamental problems in the context of fault-tolerant distributed computing. The problem consists,
given a set Ω of processes having each an initial value v
i
, in deciding among Ω on a common value v. In 1985, Fischer, Lynch and Paterson proved that the consensus problem is not solvable in an asynchronous system subject
to a single process crash. In 1991, Chandra and Toueg showed that, by augmenting the asynchronous system model with a well
defined unreliable failure detector, consensus becomes solvable. They also give an algorithm that solves consensus using the ◊? failure detector.
In this paper we propose a new consensus algorithm, also using the ◊? failure detector, that is more efficient than the Chandra-Toueg
consensus algorithm. We measure efficiency by introducing the notion of latency degree, which defines the minimal number of communication steps needed to solve consensus. The Chandra-Toueg algorithm has a latency
degree of 3 (it requires at least three communication steps), whereas our early consensus algorithm requires only two communication
steps (latency degree of 2). We believe that this is an interesting result, which adds to our current understanding of the
cost of consensus algorithms based on ◊?.
Received: April 1995 / Accepted: October 1996 相似文献
7.
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 相似文献
8.
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 相似文献
9.
Constraint-based deductive model checking 总被引:2,自引:0,他引:2
Giorgio Delzanno Andreas Podelski 《International Journal on Software Tools for Technology Transfer (STTT)》2001,3(3):250-270
We show that constraint logic programming (CLP) can serve as a conceptual basis and as a practical implementation platform
for the model checking of infinite-state systems. CLP programs are logical formulas (built up from constraints) that have
both a logical interpretation and an operational semantics. Our contributions are: (1) a translation of concurrent systems
(imperative programs) into CLP programs with the same operational semantics; and (2) a deductive method for verifying safety
and liveness properties of the systems which is based on the logical interpretation of the CLP programs produced by the translation.
We have implemented the method in a CLP system and verified well-known examples of infinite-state programs over integers,
using linear constraints here as opposed to Presburger arithmetic as in previous solutions.
Published online: 18 July 2001 相似文献
10.
Linguistic Problems with Requirements and Knowledge Elicitation 总被引:1,自引:0,他引:1
David C. Sutton 《Requirements Engineering》2000,5(2):114-124
Human and conversational aspects of requirements and knowledge identification are employed to show that requirements ‘engineering’
is not the same as civil engineering or scientific problem solving. Not only can requirements not be made fully explicit at
the start of a project, they cannot be made fully explicit at all. A need is identified to enhance computer-based information
systems (CBIS) development methods to accommodate: plurality of incommensurable perspectives, languages and agendas; dynamic
representations of system features that can be experienced rather than abstracted and forced into an abstract paper-based
representation; recognition that CBIS development is in general a continuous process where users changing their minds is a
natural and necessary indication or organisational vitality.
It is suggested that prototyping and rapid application development go some way to addressing these requirements but that
they require further development in the light of the theoretical light thrown on the nature of the problem. 相似文献
11.
A new adaptive thresholding algorithm concerning extraction of targets from the background in a given image sequence is proposed.
The conventional histogram-based or fixed-value thresholdings are deficient in detecting targets due to the poor contrast
between targets and the background, or to the change of illumination. This research solves the problems mentioned above by
learning the characteristics of the background from the given images and determines the proper thresholds based on this information.
Experiments show that the proposed algorithm is superior to the optimal layering algorithm in target detection and tracking.
Received: 28 December 1999 / Accepted: 8 August 2000 相似文献
12.
Integration – supporting multiple application classes with heterogeneous performance requirements – is an emerging trend
in networks, file systems, and operating systems. We evaluate two architectural alternatives – partitioned and integrated
– for designing next-generation file systems. Whereas a partitioned server employs a separate file system for each application
class, an integrated file server multiplexes its resources among all application classes; we evaluate the performance of the
two architectures with respect to sharing of disk bandwidth among the application classes. We show that although the problem
of sharing disk bandwidth in integrated file systems is conceptually similar to that of sharing network link bandwidth in
integrated services networks, the arguments that demonstrate the superiority of integrated services networks over separate
networks are not applicable to file systems. Furthermore, we show that: an integrated server outperforms the partitioned server
in a large operating region and has slightly worse performance in the remaining region; the capacity of an integrated server
is larger than that of the partitioned server; and an integrated server outperforms the partitioned server by a factor of
up to 6 in the presence of bursty workloads. 相似文献
13.
Extending the Unified Modeling Language for ontology development 总被引:3,自引:0,他引:3
Kenneth Baclawski Mieczyslaw K. Kokar Paul A. Kogut Lewis Hart Jeffrey Smith Jerzy Letkowski Pat Emery 《Software and Systems Modeling》2002,1(2):142-156
There is rapidly growing momentum for web enabled agents that reason about and dynamically integrate the appropriate knowledge
and services at run-time. The dynamic integration of knowledge and services depends on the existence of explicit declarative
semantic models (ontologies). We have been building tools for ontology development based on the Unified Modeling Language
(UML). This allows the many mature UML tools, models and expertise to be applied to knowledge representation systems, not
only for visualizing complex ontologies but also for managing the ontology development process. UML has many features, such
as profiles, global modularity and extension mechanisms that are not generally available in most ontology languages. However,
ontology languages have some features that UML does not support. Our paper identifies the similarities and differences (with
examples) between UML and the ontology languages RDF and DAML+OIL. To reconcile these differences, we propose a modification
to the UML metamodel to address some of the most problematic differences. One of these is the ontological concept variously
called a property, relation or predicate. This notion corresponds to the UML concepts of association and attribute. In ontology
languages properties are first-class modeling elements, but UML associations and attributes are not first-class. Our proposal
is backward-compatible with existing UML models while enhancing its viability for ontology modeling. While we have focused
on RDF and DAML+OIL in our research and development activities, the same issues apply to many of the knowledge representation
languages. This is especially the case for semantic network and concept graph approaches to knowledge representations.
Initial sbmission: 16 February 2002 / Revised submission: 15 October 2002 Published online: 2 December 2002 相似文献
14.
Cindy Eisner 《International Journal on Software Tools for Technology Transfer (STTT)》2002,4(1):107-124
We examine the application of symbolic CTL model checking to railway interlocking software. We show that the railway interlocking
systems examined exhibit the characteristics of robustness and locality, and that these characteristics allow optimizations
to the model checking algorithms not possible in the general case. In order to gain a better understanding of robustness and
locality, we examine in detail a small railway interlocking.
Published online: 9 October 2001 相似文献
15.
Handling message semantics with Generic Broadcast protocols 总被引:1,自引:0,他引:1
Summary. Message ordering is a fundamental abstraction in distributed systems. However, ordering guarantees are usually purely “syntactic,”
that is, message “semantics” is not taken into consideration despite the fact that in several cases semantic information about
messages could be exploited to avoid ordering messages unnecessarily. In this paper we define the Generic Broadcast problem, which orders messages only if needed, based on the semantics of the messages. The semantic information about messages
is introduced by conflict relations. We show that Reliable Broadcast and Atomic Broadcast are special instances of Generic
Broadcast. The paper also presents two algorithms that solve Generic Broadcast.
Received: August 2000 / Accepted: August 2001 相似文献
16.
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 相似文献
17.
Subspace-based line detection (SLIDE) is a novel approach for straight line fitting that has recently been suggested by Aghajan
and Kailath. It is based on an analogy made between a straight line in an image and a planar propagating wavefront impinging
on an array of sensors. Efficient sensor array processing algorithms are used to detect the parameters of the line. SLIDE
is computationally cheaper than the Hough transform, but it has not been clear whether or not this is a magical free bonus.
In particular, it has not been known how the breakpoints of SLIDE relate to those of the Hough transform. We compare the failure
modes and limitations of the two algorithms and demonstrate that SLIDE is significantly less robust than the Hough transform. 相似文献
18.
Location is one of the most important elements of context in ubiquitous computing. In this paper we describe a location model, a spatial-aware communication model and an implementation of the models that exploit location for processing and communicating context. The location model presented describes a location
tree, which contains human-readable semantic and geometric information about an organisation and a structure to describe the
current location of an object or a context. The proposed system is dedicated to work not only on more powerful devices like
handhelds, but also on small computer systems that are embedded into everyday artefact (making them a digital artefact). Model and design decisions were made on the basis of experiences from three prototype setups with several applications,
which we built from 1998 to 2002. While running these prototypes we collected experiences from designers, implementers and users and formulated them as guidelines in this paper. All the prototype applications heavily use location information for providing their functionality. We found
that location is not only of use as information for the application but also important for communicating context. In this
paper we introduce the concept of spatial-aware communication where data is communicated based on the relative location of
digital artefacts rather than on their identity.
Correspondence to: Michael Biegl, Telecooperation Office (TecO), University of Karlsruhe, Vincenz-Prieβritz-Str. 1 D-76131 Karlsruhe, Germany.
Email: michael@teco.edu 相似文献
19.
This paper presents a new online check system that solves the reusability problem of refunds in existing systems using the
partially blind signature. The clear part of the signature is used to encode the face value of a check. In our system, refunds
can be reused in payment in the same way as withdrawn checks without any limitation. We also use a one-time secret key as
the serial number of a check to increase the efficiency of payment. The new system provides multiple offline shopping sessions
to minimize the number of online messages. During the offline session, we use a one-way accumulator to construct a proof of
payment. The security and the atomicity of the system is also discussed.
Published online: 3 September 2002 相似文献
20.
Wood inspection with non-supervised clustering 总被引:9,自引:0,他引:9
Abstract. The appearance of sawn timber has huge natural variations that the human inspector easily compensates for mentally when determining
the types of defects and the grade of each board. However, for automatic wood inspection systems these variations are a major
source for complication. This makes it difficult to use textbook methodologies for visual inspection. These methodologies
generally aim at systems that are trained in a supervised manner with samples of defects and good material, but selecting
and labeling the samples is an error-prone process that limits the accuracy that can be achieved. We present a non-supervised
clustering-based approach for detecting and recognizing defects in lumber boards. A key idea is to employ a self-organizing
map (SOM) for discriminating between sound wood and defects. Human involvement needed for training is minimal. The approach
has been tested with color images of lumber boards, and the achieved false detection and error escape rates are low. The approach
also provides a self-intuitive visual user interface.
Received: 16 December 2000 / Accepted: 8 December 2001
Correspondence to: O. Silvén 相似文献