The proceedings contains 31 papers from the proceedings of the twenty-thirdacm SIGMOD-SIGACT-SIGART symposium on principles of Database Systems. The topics discussed include: conditional XPath, the first order comple...
详细信息
The proceedings contains 31 papers from the proceedings of the twenty-thirdacm SIGMOD-SIGACT-SIGART symposium on principles of Database Systems. The topics discussed include: conditional XPath, the first order complete XPath dialect;frontiers for tractability for typechecking simple XML transformations;positive active XML;the past, present and future of web information retrieval;comparing and aggregating rankings with ties and specification and verification of data-driven web services.
In an earlier paper, Awerbuch presented an innovative distributed algorithm for solving minimum spanning tree problems that achieved optimal time and message complexity through the introduction of several advanced fea...
详细信息
ISBN:
(纸本)9780897917100
In an earlier paper, Awerbuch presented an innovative distributed algorithm for solving minimum spanning tree problems that achieved optimal time and message complexity through the introduction of several advanced features. In this paper, we show that there are some cases where his algorithm can create cycles or fail to achieve optimal time complexity. We then show how to modify the algorithm to avoid these problems, and demonstrate both the correctness and optimality of the revised algorithm.
This conference proceedings contains 25 papers. The topics covered are: impossibility proofs;nondeterministic processes;communicating finite-state machines;bounded protocols for FIFO channels;sequence transmission pro...
详细信息
ISBN:
(纸本)0897913264
This conference proceedings contains 25 papers. The topics covered are: impossibility proofs;nondeterministic processes;communicating finite-state machines;bounded protocols for FIFO channels;sequence transmission problems;communication in the presence of faults;knowledge, probability, and adversaries;reliable message diffusion;expressivity and knowledge;ambiguity of choosing;concensus;mutual exclusion;fault-tolerant computing;parallel algorithms;distributed recovery;induction theorem;parallel programs;concurrency;Byzantine agreement;shared memory versus message passing;calling names;multishop radio networks;fault isolation;randomized concensus.
distributed problems that can be solved with so-called k-ftss protocols that combine two types of failure resilience: k-fault-tolerance (k-ft) and self-stabilization (ss) is investigated. The protocol guarantees that,...
详细信息
ISBN:
(纸本)9780897919524
distributed problems that can be solved with so-called k-ftss protocols that combine two types of failure resilience: k-fault-tolerance (k-ft) and self-stabilization (ss) is investigated. The protocol guarantees that, whether the network is a ring or a descending order of identifiers. Once stabilized, the correct processes do not change their solutions even if a crash fault breaks the ring to a line.
This paper presents two distributed algorithms for the computation of sparse certificates for k-connectivity in asynchronous networks where a network is represented by a graph and processors have unique identities. A ...
详细信息
ISBN:
(纸本)9780897918008
This paper presents two distributed algorithms for the computation of sparse certificates for k-connectivity in asynchronous networks where a network is represented by a graph and processors have unique identities. A certificate of the k-connectivity of a graph G = (V,E) on n nodes and m edges is a spanning subgraph G′ = (V,E′). Finding a certificate with the minimum number of edges for any fixed k is NP-hard, thus, sparse certificates which contain 0(kn) edges are found.
The existing analyses of distributed Shared Memory (DSM) consistency conditions is extended by investigating achievable levels of fault tolerance. It is shown that in many cases there is a tradeoff - increasing the re...
详细信息
ISBN:
(纸本)9780897919524
The existing analyses of distributed Shared Memory (DSM) consistency conditions is extended by investigating achievable levels of fault tolerance. It is shown that in many cases there is a tradeoff - increasing the resilience of one operation necessitates a decrease in the resilience of the other. This result implies that, in practice, it may be possible to increase the resilience of critical or oft-used operations at the expense of other operations.
We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that w...
详细信息
ISBN:
(纸本)9781581138023
We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant of consensus in which processes have the option to decide 'quit' if a failure occurs), and solving non-blocking atomic commit.
暂无评论