A coterie under an underlying set U is a family of subsets of U such that every pair of subsets has at least one element in common, but neither is a subset of the other. A coterie C under U is said to be nondominated (ND) if there is no other coterie D under U such that, for every $Q \in C$, there exists $Q' \in D$ satisfying $Q' \subseteq Q$. We introduce the operation $\sigma$ which transforms a ND coterie to another ND coterie. A regular coterie is a natural generalization of a vote-assignable coterie. We show that any regular ND coterie C can be transformed to any other regular ND coterie D by judiciously applying the $\sigma$ operation to C at most |C|+|D|-2 times. As another application of the $\sigma$ operation, we present an incrementally polynomial-time algorithm for generating all regular ND coteries. We then introduce the concept of a g-regular functional as a generalization of availability. We show how to construct an optimum coterie C with respect to a g-regular functional in O(n 3 |C|) time, where n =|U|. Finally, we discuss the structures of optimum coteries with respect to a g-regular functional.

When nodes may fail, it is desirable to minimize the expected number of probes required to find a quorum. We show some properties of “probe trees”, propose several heuristics for finding an optimal probe strategy, and compare their performance.

A coterie is a family of subsets such that every pair of subsets in it has at least one element in common but neither is a subset of the other. We introduce an operator σ, which transforms a ND (non-dominated; see the Introduction for definition) coterie to another ND coterie. A “regular” coterie is a natural generalization of a “vote-assignable” coterie, which is used in some practical applications. We show that any regular ND coterie C can be transformed to any other regular ND coterie D by judiciously applying σ operations to C at most |C| + |D| - 2 times.

Let G be an undirected graph with a set of vertices V and a set of edges E. Given an integer r, we assign at most r labels (representing "resources") to each vertex. We say that such an assignment is an r-configuration if, for each label c, the vertices labeled by c form a dominating set for G. In this paper, we are interested in the maximum number, D r (G), of labels that can be assigned to the vertices of graph G by an r-configuration. The decision problem ``$D_1(G)\geq K$?" (known as the domatic number problem) is NP-complete. We first investigate D r (G) for general graphs and establish bounds on D r (G) in terms of D 1 (G) and the minimum vertex degree of G. We then discuss D r (G) for d-regular graphs. We clearly have $D_r (G) \leq r(d+1)$. We show that the problem of testing if D r (G) = r(d+1) is solvable in polynomial time for d-regular graphs with |V| = 2(d+1), but is NP-complete for those with |V| = a(d+1) for some integer $a \geq 3$. Finally, we discuss cubic (i.e., 3-regular) graphs. It is easy to show $2r \leq D_r (G) \leq 4r$ for cubic graphs. We show that the decision problem for D 1 (G) = K is co-NP-complete for K = 2 and is NP-complete for K = 4. Although there are many cubic graphs G with D 1 (G) = 2, surprisingly, every cubic graph has a 2-configuration with five labels, i.e., $D_2 (G) \geq 5$ and such a 2-configuration can be constructed in polynomial time. We use this fact to show $D_r (G) \geq \lfloor 5r/2 \rfloor$ in general.

We consider the problem faced by a robot that must explore and learn an unknown room with obstacles in it. We seek algorithms that achieve a bounded ratio of the worst-case distance traversed in order to see all visible points of the environment (thus creating a map), divided by the optimum distance needed to verify the map, if we had it in the beginning. The situation is complicated by the fact that the latter off-line problem (the problem of optimally verifying a map) is NP-hard. Although we show that there is no such “competitive” algorithm for general obstacle courses, we give a competitive algorithm for the case of a polygonal room with a bounded number of obstacles in it. We restrict ourselves to the rectilinear case, where each side of the obstacles and the room is parallel to one of the coordinates, and the robot must also move either parallel or perpendicular to the sides. (In a subsequent paper, we will discuss the extension to polygons of general shapes.) We also discuss the off-line problem for simple rectilinear polygons and find an optimal solution (in the L 1 metric) in polynomial time, in the case where the entry and the exit are different points.

The B/sup +/-tree, R-tree and K-D-B tree have been proposed as the index structures for point data in a d-dimensional space. We apply the lock coupling technique to them to allow concurrent accesses. We discuss the two common user operations, search and insert, and present concurrency control algorithms for them. We have implemented these concurrency control algorithms in the SR distributed programming language. We report on our preliminary results comparing their relative performance.

The ATM switching scheme we propose is similar to the multi-frame stop-and-go, except that we use EDF (earliest-deadline-first) scheduling, instead of rate-monotonic, static-priority scheduling. Unlike the multi-frame stop-and-go, our scheme can fully utilize the link bandwidth, and does not require that the input or output frames of the same size be synchronized. EDF scheduling is, in general, more complex than static-priority scheduling. However, we show that the next earliest deadline needs to be computed only when an output frame reaches its end, i.e., not whenever a cell is output, resulting in significant saving in computation time. We derive bounds on end-to-end delay and delay-jitter, and discuss implementation issues.

Abstract A graph‐theoretical model is presented for scheduling the transmission of messages in a computer network. A related wiring problem is also discussed; connections with classical edge colorings are exhibited and optimality properties are discussed. © 1993 by John Wiley & Sons, Inc.

Many results regarding the probability of aliasing for multiple-input compactors have been derived under error assumptions that are not very realistic for VLSI circuits. Recently, the value of aliasing probability has been proven to tend to 2/sup -k/, where k is the number of binary memory elements of the linear compactor. This result is based on the assumption that the compactor is characterized by an irreducible polynomial and that the 'no error' vector has a probability different from zero. In these notes, the above result is generalized. More specifically, it is proved that it is valid if any two error vectors, neither of which needs to be the 'no error' vector, have probabilities of occurrence different from zero. To make the error model complete, the situation in which exactly one error vector has a probability different from zero is also considered. For the latter type of error distributions, the test lengths at which aliasing occurs are determined. Simple proofs for the results are provided; they are based on standard linear algebra notions and well-known theorems.>

Aliasing is studied for delay and stuck-open faults. It is shown that, as the test sequence length is increased, the probability of aliasing for such faults tend to 2/sup -k/, where k is the number of binary memory elements in a linear compactor. The result is based on the assumption that the linear compactor has an irreducible characteristic polynomial. Some recent results on combinational faults are special cases of the results presented here.>

A coterie under a ground set U consists of subsets (called quorums) of U such that any pair of quorums intersect with each other. Nondominated (ND) coteries are of particular interest, since they are optimal in some sense. By assigning a Boolean variable to each element in U, a family of subsets of U is represented by a Boolean function of these variables. The authors characterize the ND coteries as exactly those families which can be represented by positive, self-dual functions. In this Boolean framework, it is proved that any function representing an ND coterie can be decomposed into copies of the three-majority function, and this decomposition is representable as a binary tree. It is also shown that the class of ND coteries proposed by D. Agrawal and A. El Abbadi (1989) is related to a special case of the above binary decomposition, and that the composition proposed by M.L. Neilsen and M. Mizuno (1992) is closely related to the classical Ashenhurst decomposition of Boolean functions. A number of other results are also obtained. The compactness of the proofs of most of these results indicates the suitability of Boolean algebra for the analysis of coteries.>

Although finding an optimal coterie for a general graph G is computationally intractable, it is shown that it can be easily found if G is a ring. Since the solution is already known when G is a complete graph, it is implied that an optimal coterie can be obtained if every biconnected component of G consists of a single edge, a ring, or a complete graph.>

The effectiveness of a random built-in self-test technique for VLSI circuits is studied. This technique, called the circular self-test path (CSTP), is applicable to circuits that consist of combinational blocks and registers. In particular, the effectiveness of test pattern generation, the effectiveness of test response compaction and fault coverage are examined. The test generation effectiveness is evaluated by the fraction of all possible test patterns applied during a testing session to the circuit under test. The compaction effectiveness of the CSTP technique is measured by the probability of aliasing, and fault coverage by the fraction of all permanent faults that are detected. For all these measures, simple formulas are developed, which give very accurate estimations without detailed circuit simulation. To demonstrate their accuracy, the estimates obtained by the formulas are compared to the results obtained by extensive simulation experiments.>

Checkpointing in a distributed database system is analyzed by establishing a correspondence between consistent snapshots in a general distributed system and transaction-consistent checkpoints in a distributed database system. The analysis culminates in a useful condition for transaction-consistent checkpoints. Based on this condition, a general checkpointing scheme, which records a transaction-consistent set of values of all or some selected data items is presented. These rules are implemented in some representative concurrency control protocols, i.e., those based on two-phase locking and timestamping. These implementations cause little interference with other activities in the database system.>

The authors consider the problem faced by a newborn that must explore and learn an unknown room with obstacles in it. They seek algorithms that achieve a bounded ratio of the worst-case distance traversed in order to see all visible points of the environment (thus creating a map), divided by the optimum distance needed to verify the map. The situation is complicated by the fact that the latter offline problem (optimally verifying a map) is NP-hard and thus must be solved approximately. Although the authors show that there is no such competitive algorithm for general obstacle courses, they give a competitive algorithm for the case of a polygonal room with a bounded number of obstacles in it.>

We present a new checkpointing scheme for a distributed database system. Our scheme records the states of some selected data items and can be executed at any time without stopping other activities in the database system. It makes use of “shadows” of data items to make sure that the collected data item values are “transaction-consistent”. Storage overhead is low, since at most one shadow is needed for each data item.

Let MC stand for a class of logs (i.e. sequences of read/write steps of transactions) that are serializable when multiple versions of the data items are maintained. The multiversion cautious scheduler, MCS(MC) which is introduced, outputs a sequence belonging to MC by reordering, if necessary, the incoming sequence of requests from transactions and it never resorts to rollbacks. In the model, transactions on arrival predeclare their read sets and write sets. It is shown that MCS(MWW) and MCS(MWRW) can be executed in polynomial time, where MWW and MWRW are multiversion classes of logs serializable under the write-write and write-read-write constraints respectively. For any multiversion class MC of interest, MCS(MC) does not exhibit cancellation anomaly, i.e. it functions correctly even if some of the predeclared steps are canceled. Furthermore, MCS(MWW) functions correctly, even if transactions issue more read operations than they predeclared. Thus, MCS(MWW) allows each transaction to predeclare only its write set.>

This paper presents a concurrency control algorithm for nested transactions accessing B-trees. It combines the idea of B-link tree with that of resilient 2-phase locking [Mos85b]. The I/O automaton model is used in the specification and proofs of correctness of the system. We define “strongly-serially correct” schedules and use this property as our correctness criterion.

Article Computing on an anonymous network Share on Authors: Masafumi Yamashita Department of Electrical Engineering, Hiroshima University, 724 Japan Department of Electrical Engineering, Hiroshima University, 724 JapanView Profile , Tiko Kameda School of Computing Science, Simon Fraser University, Bumaby, B.C., Canada V5A 1S6 School of Computing Science, Simon Fraser University, Bumaby, B.C., Canada V5A 1S6View Profile Authors Info & Claims PODC '88: Proceedings of the seventh annual ACM Symposium on Principles of distributed computingJanuary 1988 Pages 117–130https://doi.org/10.1145/62546.62568Online:01 January 1988Publication History 50citation547DownloadsMetricsTotal Citations50Total Downloads547Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Cautious schedulers, which never resort to rollbacks for the purpose of concurrency control, are investigated. In particular, cautious schedulers for classes WW consisting of schedules serializable under the write-write constraints, and WRW, a superclass of W, are considered. The cautious WW-scheduler has a number of nice properties, one of which is the existence of a polynomial-time scheduling algorithm. Since cautious WRW-scheduling is, in general, NP-complete, some restrictions are introduced which allow polynomial-time scheduling. All of these cautious schedulers are based on the assumption that transaction predeclare their read and write sets on arrival. Anomalies which occur when transaction modify their read sets or write sets during execution are discussed and countermeasures are proposed.>

This paper deals with the serializability theory for single-version and multiversion database systems. We first introduce the concept of disjoint-interval topological sort ( DITS , for short) of an arc-labeled directed acyclic graph. It is shown that a history is serializable if and only if its transaction IO graph has a DITS. We then define several subclasses of serializable histories, based on the constraints imposed by write-write, write-read, read-write, or read-read conflicts, and investigate inclusion relationships among them. In terms of DITS, we give a sufficient condition for a class of serializable histories to be polynomially recognizable, which is then used to show that a new class of histories, named WRW, can be recognized in polynomial time. We also present NP-completeness results for the problem of testing membership in some other classes. In the second half of this paper, we extend these results to multiversion database systems. The inclusion relationships among multiversion classes defined by constraints, such as write-write and write-read, are investigated. One such class coincides with class DMVSR, introduced by Papadimitriou and Kanellakis, and gives a simple characterization of this class. It is shown that for most constraints, multiversion classes properly contain the corresponding single-version classes. Complexity results for the membership testing are also discussed.

Partition failure causes a major problem for the availability of a distributed database system.No protocol can consistently terminate all parts of a distributed transaction under all possible partitions, since some sites executing subtransactions may not know thai other sites have already committed (or aborted) and, therefore, must wait until the failure is repaired.Under a site optimal termination protocol, the expected number of waiting sites is minimized, hence it maximizes the "availability" of a database system in the presence of partition failures.We introduce a new class of termination protocols, called size-based termination protocols, and identify site optimal termination protocols within this class.

We propose a new class of schedulers, called cautious schedulers , that grant an input request if it will not necessitate any rollback in the future. In particular, we investigate cautious WRW-schedulers that output schedules in class WRW only. Class WRW consists of all schedules that are serializable, while preserving the write-read and read-write conflict, and is the largest polynomially recognizable subclass of serializable schedules currently known. It is shown, in this paper however, that cautious WRW- scheduling is, in general, NP-complete. Therefore, we introduce a special type ( type 1R ) of transaction, which consists of no more than one read step (an indivisible set of read operations) followed by multiple write steps. It is shown that cautious WRW-scheduling can be performed efficiently if all transactions are of type 1R and if admission control can be exercised. Admission control rejects a transaction unless its first request is immediately grantable.

Using the nested loops method, this paper addresses the problem of minimizing the number of page fetches necessary to evaluate a given query to a relational database. We first propose a data structure whereby the number of page fetches required for query evaluation is substantially reduced and then derive a formula for the expected number of page fetches. An optimal solution to our problem is the nesting order of relations in the evaluation program, which minimizes the number of page fetches. Since the minimization of the formula is NP-hard, as shown in the Appendix, we propose a heuristic algorithm which produces a good suboptimal solution in polynomial time. For the special case where the input query is a “tree query,” we present an efficient algorithm for finding an optimal nesting order.

Consider a system consisting of a set ofn processes, P~, P2 ..... Pn, and a set of serially reusable resources of m different types, R1, R~ ..... R,~.It is assumed that the system is "claim-limited," that is, its "claim matrix" C, whose (i, j) element C(i, j) is the maximum number of units of R: that may be needed by P, at the same time, is known a priori.It is desired to design a deadlock-free system, that is, one which never deadlocks for any allocation sequence within the limits given by C. For j ffi 1, 2 ..... m, let a, (>0) be the cost of one unit of Rj.An algorithm for designing a deadlock-free system with the minimum resource cost is presented.Its running time is bounded by O(ca(m) + mlogm), where e ts the number of nonzero elements in C and a, is the inverse of Ackermann's function, which is very slowly growing Categories and Subject Descriptors: D.4.m

In this paper, we show that some Codd third normal form relations may contain “superfluous” attributes because the definitions of transitive dependency and prime attribute are inadequate when applied to sets of relations. To correct this, an improved third normal form is defined and an algorithm is given to construct a set of relations from a given set of functional dependencies in such a way that the superfluous attributes are guaranteed to be removed. This new normal form is compared with other existing definitions of third normal form, and the deletion normalization method proposed is shown to subsume the decomposition method of normalization.

The problem of determining whether it is possible for a set of “free-running” processes to become deadlocked is considered. It is assumed that any request by a process is immediately granted as long as there are enough free resource units to satisfy the request. The question of whether or not there exists a polynomial algorithm for predicting deadlock in a “claim-limited” serially reusable resource system has been open. An algorithm employing a network flow technique is presented for this purpose. Its running time is bounded by O ( mn 1.5 ) if the system consists of n processes sharing m types of serially reusable resources.

System diagnosis is investigated along the line of a pioneering work by Preparata et al. and motivated by a recent work of Hakimi and Amin. It is shown that practically all the previous results on the analysis aspect of this problem can be derived from a single theorem in this correspondence.