No abstract available.

This year, the 'CS 1' course at Rose-HuIman Institute of Technology used Microsoft Visual C++ (MSVC) on laptop computers.We chose MSVC to provide as exciting a platform as possible for our students.MSVC is a powerful environment that permits us to do exciting laboratories.At the same time, it permits students (and us) to be sidetracked into issues not directly pertinent to a first course in computer science.We chronicle our use of MSVC, discussing the closed laboratories we developed and our efforts to make them stirring yet not overwhelming.In particular, we discuss how we used multimedia and Windows/GUI (graphical user interface) programming to create dramatic laboratories withcut obscuring fundamentals.

Games with imperfect information are an interesting and important class of games. They include most card games (e.g., bridge and poker) as well as many economic and political models. Here we investigate algorithms for findi ng the simplest form of a solution (a pure‐strategy equilibrium point) to imperfect information games expressed in their extensive (game tree) form. We introduce to the artificial intelligence community a classic algorithm, due to Wilson, that solves one‐player games with perfect recall. Wilson's algorithm, which we call iMP‐minimax, runs in time linear in the size of the game‐tree searched. In contrast to Wilson's result, Koller and Meggido have shown that finding a pure‐strategy equilibrium point in one‐player games without perfect recall is NP‐hard. Here, we provide another contrast to Wilson's result–we show that in games with perfect recall but more than one player, finding a pure‐strategy equilibrium point, given that such an equilibrium point exists, is NP‐hard. Our second contribution is to present a pruning technique for Wilson's IMP‐minimax algorithm to make the latter more tractable. We call this new algorithm IMP‐alpha‐beta. We provide a theoretical framework (model) and analyze IMP‐alpha‐beta in that model. IMP‐alpha‐beta is of direct value for one‐player, perfect‐recall games. It also has strong potential for other imperfect information games, as it is a natural (but as yet untested) heuristic in those cases.

There are several replica control algorithms for managing replicated files in the face of network partitioning due to site or communication link failures. Pessimistic algorithms ensure consistency at the price of reduced availability; they permit at most one (distinguished) partition to process updates at any given time. The best known pessimistic algorithm, voting , is a “static” algorithm, meaning that all potential distinguished partitions can be listed in advance. We present a dynamic extension of voting called dynamic voting . This algorithm permits updates in a partition provided it contains more than half of the up-to-date copies of the replicated file. We also present an extension of dynamic voting called dynamic voting with linearly ordered copies (abbreviated as dynamic-linear ). These algorithms are dynamic because the order in which past distinguished partitions were created plays a role in the selection of the next distinguished partition. Our algorithms have all the virtues of ordinary voting, including its simplicity, and provide improved availability as well. We provide two stochastic models to support the latter claim. In the first (site) model, sites may fail but communication links are infallible; in the second (link) model the reverse is true. We prove that under the site model, dynamic-linear has greater availability than any static algorithm, including weighted voting, if there are four or more sites in the network. In the link model, we consider all biconnected five-site networks and a wide variety of failure and repair rates. In all cases considered, dynamic-linear had greater availability than any static algorithm.

A hybrid scheme that integrates the static voting protocol and dynamic voting with linearly ordered copies is proposed. A stochastic model is used to compare the file availability afforded by the proposed hybrid scheme with the availabilities of voting, dynamic voting, and dynamic voting with linearly ordered copies. The hybrid scheme has the most availability of these four algorithms for all reasonable repair/failure ratios tested.>

A consistency control algorithm is described for managing replicated files in the face of network partitioning due to node or communication link failures. It adopts a pessimistic approach in that mutual consistency among copies of a file is maintained by permitting files to be accessed only in a single partition at any given time. The algorithm simplifies the Davcev-Burkhard dynamic voting algorithm (1985) and also improves its availability by adding the notion of linearly ordered copies. A proof that any pessimistic algorithm with fresh reads is one-copy serializable is given.>

A hybrid scheme is proposed that integrates the static voting protocol and dynamic voting with linearly ordered copies. A stochastic model is used to compare the file availability afforded by the proposed hybrid scheme against the availabilities of voting, dynamic voting, and dynamic voting with linearly ordered copies. The analysis provides evidence for the conjecture that the hybrid scheme is the optimal algorithm in the context of the stochastic model.>

In a voting-based algorithm, a replicated file can be updated in a partition if it contains a majority of copies. In this paper, we propose an extension of this scheme which permits a file to be updated in a partition provided it contains a majority of up-to-date copies. Our scheme not only preserves mutual consistency of the replicated file, but provides improvement in its availability as well. We develop a stochastic model which gives insight into the improvements afforded by our scheme over the voting scheme.

The problem of authentication of mutually suspicious parties is one that is becoming more and more important with the proliferation of distributed systems. In this paper we describe a protocol, based on the difficulty of finding discrete logarithms over finite fields, by which users can verify whether they have matching credentials without revealing their credentials to each other unless there is a match. This protocol requires a trusted third party, but does not require it to be available to the users except when they sign up for the system. Thus it is useful in situations in which a trusted third party exists but is not available to all users at all times.

This paper presents a probabilistic model for studying the question: given n search resources, where in the search tree should they be expended? Specifically, a least-cost root-to-leaf path is sought in a random tree. The tree is known to be binary and complete to depth N. Arc costs are independently set either to 1 (with probability p)or to 0 (with probability l-p). The cost of a leaf is the sum of the arc costs on the path from the root to that leaf. The searcher (scout) can learn n arc values. How should these scarce resources be dynamically allocated to minimize the average cost of the leaf selected? A natural decision rule for the scout is to allocate resources to arcs that lie above leaves whose current expected cost is minimal. The bad-news theorem says that situations exist for which this rule is nonoptimal, no matter what the value of n. The good-news theorem counters this: for a large class of situations, the aforementioned rule is an optimal decision rule if p ≤ 1/2 and within a constant of optimal if p ≫ 1/2.