共查询到10条相似文献,搜索用时 140 毫秒
1.
Summary. A useless checkpoint is a local checkpoint that cannot be part of a consistent global checkpoint. This paper addresses the following
problem. Given a set of processes that take (basic) local checkpoints in an independent and unknown way, the problem is to design communication-induced checkpointing protocols
that direct processes to take additional local (forced) checkpoints to ensure no local checkpoint is useless.
The paper first proves two properties related to integer timestamps which are associated with each local checkpoint. The first
property is a necessary and sufficient condition that these timestamps must satisfy for no checkpoint to be useless. The second
property provides an easy timestamp-based determination of consistent global checkpoints. Then, a general communication-induced
checkpointing protocol is proposed. This protocol, derived from the two previous properties, actually defines a family of
timestamp-based communication-induced checkpointing protocols. It is shown that several existing checkpointing protocols for
the same problem are particular instances of the general protocol. The design of this general protocol is motivated by the
use of communication-induced checkpointing protocols in “consistent global checkpoint”-based distributed applications such
as the detection of stable or unstable properties and the determination of distributed breakpoints.
Received: July 1997 / Accepted: August 1999 相似文献
2.
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 相似文献
3.
Alessandro Panconesi Marina Papatriantafilou Philippas Tsigas Paul Vitányi 《Distributed Computing》1998,11(3):113-124
A naming protocol assigns unique names (keys) to every process out of a set of communicating processes. We construct a randomized
wait-free naming protocol using wait-free atomic read/write registers (shared variables) as process intercommunication primitives.
Each process has its own private register and can read all others. The addresses/names each one uses for the others are possibly
different: Processes p and q address the register of process r in a way not known to each other. For processes and , the protocol uses a name space of size and running time (read/writes to shared bits) with probability at least , and overall expected running time. The protocol is based on the wait-free implementation of a novel -Test&SetOnce object that randomly and fast selects a winner from a set of q contenders with probability at least in the face of the strongest possible adaptive adversary.
Received: September 1994 / Accepted: January 1998 相似文献
4.
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 相似文献
5.
David P.L. Simons Mariëlle I.A. Stoelinga 《International Journal on Software Tools for Technology Transfer (STTT)》2001,3(4):469-485
This paper reports on the mechanical verification of the IEEE 1394 root contention protocol. This is an industrial leader
election protocol, in which timing parameters play an essential role. A manual verification of this protocol using I/O automata
has been published in [24]. We improve the communication model presented in that paper. Using the Uppaal2k tool, we investigate
the timing constraints on the parameters which are necessary and sufficient for correct protocol operation: by analyzing large
numbers of protocol instances with different parameter values, we derive the required timing constraints. We explore the use
of model checking in combination with stepwise abstraction. That is, we show that the implementation automaton correctly implements
the specification via several intermediate automata, using Uppaal to prove the trace inclusion in each step.
Published online: 18 July 2001 相似文献
6.
Hong Peng Sofiène Tahar Ferhat Khendek 《International Journal on Software Tools for Technology Transfer (STTT)》2003,4(2):234-245
In this paper, we compare and contrast SPIN and VIS, two widely used formal verification tools. In particular, we devote special
attention to the efficiency of these tools for the verification of communications protocols that can be implemented either
in software or hardware. As a basis of our comparison, we formally describe and verify the Asynchronous Transfer Mode Ring
(ATMR) medium access protocol using SPIN and its hardware model using VIS. We believe that this study is of particular interest
as more and more protocols, like ATM protocols, are implemented in hardware to match high-speed requirements.
Published online: 1 March 2002 相似文献
7.
Naci S. Ishakbeyoglu Z. Meral Ozsoyoglu 《The VLDB Journal The International Journal on Very Large Data Bases》1998,7(2):67-78
Semantic integrity constraints are used for enforcing the integrity of the database as well as for improving the efficiency
of the database utilization. Although semantic integrity constraints are usually much more static as compared to the data
itself, changes in the data semantics may necessitate corresponding changes in the constraint base. In this paper we address
the problems related with maintaining a consistent and non-redundant set of constraints satisfied by the database in the case
of updates to the constraint base. We consider implication constraints as semantic integrity constraints. The constraints
are represented as conjunctions of inequalities. We present a methodology to determine whether a constraint is redundant or
contradictory with respect to a set of constraints. The methodology is based on the partitioning of the constraint base which
improves the efficiency of algorithms that check whether a constraint is redundant or contradictory with respect to a constraint
base.
Received August 19, 1993 / Accepted July 7, 1997 相似文献
8.
A new class of gossip protocols to diffuse updates securely is presented. The protocols rely on annotating updates with the
path along which they travel. To avoid a combinatorial explosion in the number of annotated updates, rules are employed to
choose which updates to keep. Different sets of rules lead to different protocols. Results of simulated executions for a collection
of such protocols are described – the protocols would appear to be practical, even in large networks.
Received: October 2001 / Accepted: July 2002
Supported in part by ARPA/RADC grant F30602-96-1-0317, AFOSR grant F49620-00-1-0198, Defense Advanced Research Projects Agency
(DARPA) and Air Force Research Laboratory Air Force Material Command USAF under agreement number F30602-99-1-0533, National
Science Foundation Grant 9703470, and a grant from Intel Corporation. The views and conclusions contained herein are those
of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed
or implied, of these organizations or the U.S. Government. 相似文献
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 相似文献