bluuebunny/crossref_metadata_2025 huggingface dataset:
Bias in computer systems
Authors: Friedman Batya , Nissenbaum Helen
Published: July 2002

From an analysis of actual cases, three categories of bias in computer systems have been developed: preexisting, technical, and emergent. Preexisting bias has its roots in social institutions, practices, and attitudes. Technical bias arises from technical constraints of considerations. Emergent bias arises in a context of use. Although others have pointed to bias inparticular computer systems and have noted the general problem, we know of no comparable work that examines this phenomenon comprehensively and which offers a framework for understanding and remedying it. We conclude by suggesting that freedom from bias should by counted amoung the select set of criteria—including reliability, accuracy, and efficiency—according to which the quality of systems in use in society should be judged.
An analysis of magic sets and related optimization strategies for logic queries
Authors: Sippu Seppo , Soisalon-Soininen Eljas
Published: July 2002

We analyze the optimization effect of the “magic sets” rewriting technique for datalog queries and present some supplementary or alternative techniques that avoid many shortcomings of the basic technique. Given a magic sets rewritten query, the set of facts generated for the original, nonmagic predicates by the seminaive bottom-up evaluation is characterized precisely. It is shown that—because of the additional magic facts—magic sets processing may result in generating an order of magnitude more facts than the straightforward naive evaluation. A refinement of magic sets infactorized magic setsis defined. These magic sets retain most of the efficiency of original magic sets in regards to the number of nonmagic facts generated and have the property that a linear-time bound with respect to seminaive evaluation is guaranteed in all cases. An alternative technique for magic sets, calledenvelopes, which has several desirable properties over magic sets, is introduced. Envelope predicates are never recursive with the original predicates; thus, envelopes can be computed as a preprocessing task. Envelopes also allow the utilization of multiple sideways information passing strategies (sips) for a rule. An envelope-transformed program may be “readorned” according to another choice of sips and reoptimized by magic sets (or envelopes), thus making possible an optimization effect that cannot be achieved by magic sets based on a particular choice of sips.
A composition-alias method for generating gamma variates with shape parameter greater than 1
Authors: Sarkar Tapas K.
Published: July 2002

In this article the author describes a procedure for generating gamma variates with shape parameter >1. Given a supply of “good” uniform (0,1) variates, the procedure makes use of composition method, squeeze method, and aliasing to generate gamma variates. Comparison with existing methods shows that the author's method is faster in terms of computer time and uses a smaller number of uniform (0,1) variates. The method is also statistically exact.
Exponential bounds with applications to call admission
Authors: Liu Zhen , Nain Philippe , Towsley Don
Published: July 2002

In this paper, we develop a framework for computing upper and lower bounds of an exponential form for a large class of single resource systems with Markov additive inputs. Specifically, the bounds are on quantities such as backlog, queue length, and response time. Explicit or computable expressions for our bounds are given in the context of queuing theory and numerical comparisons with other bounds and exact results are presented. The paper concludes with two applications to admission control in multimedia systems.
Distributed nested decomposition of staircase linear programs
Authors: Ho James K. , Sundarraj R. P.
Published: July 2002

This article considers the application of a primal nested-decomposition method to solve staircase linear programs (SLPs) on distributed-memory, multiple-instruction-multiple-data computers. Due to the coupling that exists among the stages of an SLP, a standard parallel-decompositon algorithm for these problems would allow only a subset of the subproblem processes to overlap with one another at any give time. We propose algorithms that seek to increase the amount of overlap among the processes as well as utilize idle time beneficially. Computational results testing the effectiveness of our algoritms are reported, using a standard set of test problems.
Computational investigations of low-discrepancy sequences
Authors: Kocis Ladislav , Whiten William J.
Published: July 2002

The Halton, Sobol, and Faure sequences and the Braaten-Weller construction of the generalized Halton sequence are studied in order to assess their applicability for the quasi Monte Carlo integration with large number of variates. A modification of the Halton sequence (the Halton sequence leaped) and a new construction of the generalized Halton sequence are suggested for unrestricted number of dimensions and are shown to improve considerably on the original Halton sequence. Problems associated with estimation of the error in quasi Monte Carlo integration and with the selection of test functions are identified. Then an estimate of the maximum error of the quasi Monte Carlo integration of nine test functions is computed for up to 400 dimensions and is used to evaluate the known generators mentioned above and the two new generators. An empirical formula for the error of the quasi Monte Carlo integration is suggested.
The Monty Python method for generating random variables
Authors: Marsaglia George , Tsang Wai Wan
Published: July 2002

We suggest an interesting and fast method for generating normal, exponential, t, von Mises, and certain other important random variables used in Monte Carlo studies. The right half of a symmetric density is cut into pieces, then, using simple area-preserving transformations, reassembled into a rectangle from which the x-coordinate—or a linear function of the x-coordinate—of a random point provides the required variate. To illustrate the speed and simplicity of the Monty Python method, we provide a small C program, self-contained, for rapid generation of normal (Gaussian) variables. It is self-contained in the sense that required uniform variates are generated in-line, as pairs of 16-bit integers by means of the remarkable new multiply-with-carry method.
Provably efficient scheduling for languages with fine-grained parallelism
Authors: Blelloch Guy E. , Gibbons Phillip B. , Matias Yossi
Published: July 2002

Many high-level parallel programming languages allow for fine-grained parallelism. As in the popular work-time framework for parallel algorithm design, programs written in such languages can express the full parallelism in the program without specifying the mapping of program tasks to processors. A common concern in executing such programs is to schedule tasks to processors dynamically so as to minimize not only the execution time, but also the amount of space (memory) needed. Without careful scheduling, the parallel execution onpprocessors can use a factor ofpor larger more space than a sequential implementation of the same program.

This paper first identifies a class of parallel schedules that are provably efficient in both time and space. For any computation withwunits of work and critical path lengthd, and for any sequential schedule that takes space s1, we provide a parallel schedule that takes fewer than w/p + d steps on p processors and requires less than s1+ p·d space. This matches the lower bound that we show, and significantly improves upon the best previous bound of s1·p spaces for the common case whered«s1.

The paper then describes a scheduler for implementing high-level languages withnestedparallelism, that generates schedules in this class. During program execution, as the structure of the computation is revealed, the scheduler keeps track of the active tasks, allocates the tasks to the processors, and performs the necessary task synchronization. The scheduler is itself a parallel algorithm, and incurs at most a constant factor overhead in time and space, even when the scheduling granularity is individual units of work. The algorithm is the first efficient solution to the scheduling problem discussed here, even if space considerations are ignored.
Update semantics of relational views
Authors: Bancilhon F. , Spyratos N.
Published: July 2002

A database view is a portion of the data structured in a way suitable to a specific application. Updates on views must be translated into updates on the underlying database. This paper studies the translation process in the relational model.

The procedure is as follows: first, a “complete” set of updates is defined such that

together with every update the set contains a “return” update, that is, one that brings the view back to the original state;

given two updates in the set, their composition is also in the set.

To translate a complete set, we define a mapping called a “translator,” that associates with each view update a unique database update called a “translation.” The constraint on a translation is to take the database to a state mapping onto the updated view. The constraint on the translator is to be a morphism.

We propose a method for defining translators. Together with the user-defined view, we define a “complementary” view such that the database could be computed from the view and its complement. We show that a view can have many different complements and that the choice of a complement determines an update policy. Thus, we fix a view complement and we define the translation of a given view update in such a way that the complement remains invariant (“translation under constant complement”). The main result of the paper states that, given a complete set
U
of view updates,
U
has a translator if and only if
U
is translatable under constant complement.
Sieving Procedures on a Digital Computer
Authors: Wunderlich Marvin C.
Published: July 2002

Many sequences are most efficiently generated on a digital computer with a sieving procedure in which one represents in the main memory of the machine a set of elements known to contain the desired sequence and then systematically sieves out elements not in the desired sequence. In this expository paper, the technical aspects of programming such sieves are discussed. Special attention is given to the most efficient methods of representing sets in the main memory of the machine as well as the programming difficulties encountered when sieving on these sets. The paper concludes with a discussion of four examples in which sieving procedures were employed.
A Procedure for Checking Equality of Regular Expressions
Authors: Ginzburg A.
Published: July 2002

A simple “mechanical” procedure is described for checking equality of regular expressions. The procedure, based on the work of A. Salomaa, uses derivatives of regular expressions and transition graphs.

Given a regular expression
R
, a corresponding transition graph is constructed. It is used to generate a finite set of left-linear equations which characterize
R
. Two regular events
R
and
S
are equal if and only if each constant term in the set of left-linear equations formed for the pair (
R S
) is (φ φ) or (^ ^).

The procedure does not involve any computations with or transformations of regular expressions and is especially appropriate for the use of a computer.
Probability Models for Multiprogramming Computer Systems
Authors: Gaver D. P.
Published: July 2002

A probabilistic model is developed for a multiprogramming computer configuration, i.e., one in which several program segments are simultaneously in main memory (core). The model relates speed and number of input-output devices, core size, and central processor speed to central processor and system productivity. Incorporated in the model are parameters describing the statistical variability of input-output and central processor activities. Thus the model permits comparisons between systems loaded with different mixtures of job types (“scientific” vs. “business” applications). Numerical comparisons of various systems are provided.
Analysis of Factorial Experiments Using Generalized Matrix Operations
Authors: Oliver I.
Published: July 2002

The computer analysis of factorial experiments is discussed in terms of a new generalized matrix notation which highlights the special properties of factorial designs. A method of calculating an analysis of a variance suitable for programming as a library subroutine is described. An orthogonal transformation is used to obtain components of variance based on single degrees of freedom. The transformation is done sequentially so that no additional storage for intermediate results is required. The analysis of variance table is obtained by summation of the components according to a simple indexing procedure. An algorithm for the calculation of sums and means over all combinations of factor levels is proposed.
On the Number of Multiplications for the Evaluation of a Polynomial and Some of Its Derivatives
Authors: Shaw Mary , Traub J. F.
Published: July 2002

A family of new algorithms is given for evaluating the first
m
derivatives of a polynomial. In particular, it is shown that all derivatives may be evaluated in 3
n
- 2 multiplications. The best previous result required 1/2
n
(
n
+ 1) multiplications. Some optimality results are presented.
Enumeration of Fanout-Free Boolean Functions
Authors: Hayes John P.
Published: July 2002

A solution to the problem of counting the number of fanout-free Boolean functions of
n
variables is presented. The relevant properties of fanout-free functions and circuits are summarized. The AND and OR ranks of a fanout-free function are defined. Recursive formulas for determining the number of distinct functions of specified rank are derived. Based on these, expressions are obtained for @@@@
D
(
n
), @@@@
ND
(
n
), and @@@@(
n
), which denote the number of degenerate, nondegenerate, and all
n
-variable fanout-free functions, respectively. Simple nonrecursive bounds on the various @@@@ functions are also computed and are used to determine some asymptotic properties of the @@@@ functions. It is shown that for large
n
almost all fanout-free functions are nondegenerate, and that almost all unate functions are not fanout-free. The relationship between the fanout-free function enumeration problem and other function enumeration problems in switching theory is discussed.
Inductive analysis of the Internet protocol TLS
Authors: Paulson Lawrence C.
Published: July 2002

Internet browsers use security protocols to protect sensitive messages. An inductive analysis of TLS (a descendant of SSL 3.0) has been performed using the theorem prover Isabelle. Proofs are based on higher-order logic and make no assumptions concerning beliefs of finiteness. All the obvious security goals can be proved; session resumption appears to be secure even if old session keys are compromised. The proofs suggest minor changes to simplify the analysis.

TLS, even at an abstract level, is much more complicated than most protocols verified by researchers. Session keys are negotiated rather than distributed, and the protocol has many optional parts. Netherless, the resources needed to verify TLS are modest: six man-weeks of effort and three minutes of processor time.
Purely functional, real-time deques with catenation
Authors: Kaplan Haim , Tarjan Robert E.
Published: July 2002

We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, finding a purely functional implementation of catenable deques is required to add certain sophisticated programming constructs to functional programming languages. Our solution has a worst-case running time of
O
(1) for each push, pop, inject, eject and catenation. The best previously known solution has an
O
(log
*
k
) time bound for the
k
th deque operation. Our solution is not only faster but simpler. A key idea used in our result is an algorithmic technique related to the redundant digital representations used to avoid carry propagation in binary counting.
Implications of certain assumptions in database performance evauation
Authors: Christodoulakis S.
Published: July 2002

The assumptions of uniformity and independence of attribute values in a file, uniformity of queries, constant number of records per block, and random placement of qualifying records among the blocks of a file are frequently used in database performance evaluation studies. In this paper we show that these assumptions often result in predicting only an upper bound of the expected system cost. We then discuss the implications of nonrandom placement, nonuniformity, and dependencies of attribute values on database design and database performance evaluation.
A generalized implicit enumeration algorithm for graph coloring
Authors: Kubale Marek , Jackowski Boguslaw
Published: July 2002

A generalized algorithm for graph coloring by implicit enumeration is formulated. A number of backtracking sequential methods are discussed in terms of the generalized algorithm. Some are revealed to be partially correct and inexact. A few corrections to the invalid algorithms, which cause these algorithms to guarantee optimal solutions, are proposed. Finally, some computational results and remarks on the practical relevance of improved implicit enumeration algorithms are given.
A simple method for drawing a rational curve as two Bézier segments
Authors: Gallier Jean
Published: July 2002

In this paper we give a simple method for drawing a closed rational curve specified in terms of control points as two Bézier segments. The main result is the following:

For every affine frame
(r,s)
(where
r<s
), for every rational curve
F(t)
specified over [
r,s
] by some control polygon (β

0

, …, β

m

) (where the β

zero

are weighted control points or control vectors), the control points (θ

0

,… ,θ

m

(w.r.t.[
r,s
]) of the rational curve
G(t)
= F(φ(t)) are given by θ
i
=(-1)
i
β
i
, where φ:

RP
1
→RP
1

is the projectivity mapping [
r,s
] onto
RP
1
-]
r,s
]. Thus, in order to draw the entire trace of the curve
F
over [-∞,+∞], we simply draw the curve segments
F
[(
r,s
]) and
G
([
r,s
]).

The correctness of the method is established using a simple geometric argument about ways of partitioning the real projective line into two disjoint segments. Other known methods for drawing rational curves can be justified using similar geometric arguments.
Fine-grained mobility in the Emerald system
Authors: Jul Eric , Levy Henry , Hutchinson Norman , Black Andrew
Published: July 2002

Emerald is an object-based language and system designed for the construction of distributed programs. An explicit goal of Emerald is support for object mobility; objects in Emerald can freely move within the system to take advantage of distribution and dynamically changing environments. We say that Emerald has fine-grained mobility because Emerald objects can be small data objects as well as process objects. Fine-grained mobility allows us to apply mobility in new ways but presents implementation problems as well. This paper discusses the benefits of tine-grained mobility, the Emerald language and run-time mechanisms that support mobility, and techniques for implementing mobility that do not degrade the performance of local operations. Performance measurements of the current implementation are included.
Reflection as a mechanism for software integrity verification
Authors: Spinellis Diomidis
Published: July 2002

The integrity verification of a device's controlling software is an important aspect of many emerging information appliances. We propose the use of reflection, whereby the software is able to examine its own operation, in conjunction with cryptographic hashes as a basis for developing a suitable software verification protocol. For more demanding applications meta-reflective techniques can be used to thwart attacks based on device emulation strategies. We demonstrate how our approach can be used to increase the security of mobile phones, devices for the delivery of digital content, and smartcards.
Configuring role-based access control to enforce mandatory and discretionary access control policies
Authors: Osborn Sylvia , Sandhu Ravi , Munawer Qamar
Published: July 2002

Access control models have traditionally included mandatory access control (or lattice-based access control) and discretionary access control. Subsequently, role-based access control has been introduced, along with claims that its mechanisms are general enough to simulate the traditional methods. In this paper we provide systematic constructions for various common forms of both of the traditional access control paradigms using the role-based access control (RBAC) models of Sandhu et al., commonly called RBAC96. We see that all of the features of the RBAC96 model are required, and that although for the manatory access control simulation, only one administrative role needs to be assumed, for the discretionary access control simulations, a complex set of administrative roles is required.
The base-rate fallacy and the difficulty of intrusion detection
Authors: Axelsson Stefan
Published: July 2002

Many different demands can be made of intrusion detection systems. An important requirement is that an intrusion detection system be
effective
; that is, it should detect a substantial percentage of intrusions into the supervised system, while still keeping the false alarm rate at an acceptable level. This article demonstrates that, for a reasonable set of assumptions, the false alarm rate is the limiting factor for the performance of an intrusion detection system. This is due to the base-rate fallacy phenomenon, that in order to achieve substantial values of the Bayesian detection rate
P(Intrusion***Alarm)
, we have to achieve a (perhaps in some cases unattainably) low false alarm rate. A selection of reports of intrusion detection performance are reviewed, and the conclusion is reached that there are indications that at least some types of intrusion detection have far to go before they can attain such low false alarm rates.
The fifth generation project — a trip report
Authors: Shapiro Ehud Y.
Published: July 2002

As part of Japan's effort to become a leader in the computer industry, the Institute for New Generation Computer Technology has launched a revolutionary ten-year plan for the development of large computer systems which will be applicable to knowledge information processing systems. These Fifth Generation computers will be built around the concepts of logic programming. In order to refute the accusation that Japan exploits knowledge from abroad without contributing any of its own, this project will stimulate original research and will make its results available to the international research community.
Random sample consensus
Authors: Fischler Martin A. , Bolles Robert C.
Published: July 2002

A new paradigm, Random Sample Consensus (RANSAC), for fitting a model to experimental data is introduced. RANSAC is capable of interpreting/smoothing data containing a significant percentage of gross errors, and is thus ideally suited for applications in automated image analysis where interpretation is based on the data provided by error-prone feature detectors. A major portion of this paper describes the application of RANSAC to the Location Determination Problem (LDP): Given an image depicting a set of landmarks with known locations, determine that point in space from which the image was obtained. In response to a RANSAC requirement, new results are derived on the minimum number of landmarks needed to obtain a solution, and algorithms are presented for computing these minimum-landmark solutions in closed form. These results provide the basis for an automatic system that can solve the LDP under difficult viewing
A psychology of learning BASIC
Authors: Mayer Richard E.
Published: July 2002

This paper addresses the question: What does a person know following learning of BASIC programming? Several underlying conceptual structures are identified: (1) a transaction is an event that occurs in the computer and involves some operation on some object at some location, (2) a prestatement is a set of transactions corresponding to a line of code, (3) chunks are frequently occurring configurations of prestatements corresponding to several lines of code.
Experimental investigations of the utility of detailed flowcharts in programming
Authors: Shneiderman Ben , Mayer Richard , McKay Don , Heller Peter
Published: July 2002

This paper describes previous research on flowcharts and a series of controlled experiments to test the utility of detailed flowcharts as an aid to program composition, comprehension, debugging, and modification. No statistically significant difference between flowchart and nonflowchart groups has been shown, thereby calling into question the utility of detailed flowcharting. A program of further research is suggested.
Buddy systems
Authors: Peterson James L. , Norman Theodore A.
Published: July 2002

Two algorithms are presented for implementing any of a class of buddy systems for dynamic storage allocation. Each buddy system corresponds to a set of recurrence relations which relate the block sizes provided to each other. Analyses of the internal fragmentation of the binary buddy system, the Fibonacci buddy system, and the weighted buddy system are given. Comparative simulation results are also presented for internal, external, and total fragmentation.
A fast string searching algorithm
Authors: Boyer Robert S. , Moore J. Strother
Published: July 2002

An algorithm is presented that searches for the location, “
i
l” of the first occurrence of a character string, “
pat
,” in another string, “
string
.” During the search operation, the characters of
pat
are matched starting with the last character of
pat
. The information gained by starting the match at the end of the pattern often allows the algorithm to proceed in large jumps through the text being searched. Thus the algorithm has the unusual property that, in most cases, not all of the first
i
characters of
string
are inspected. The number of characters actually inspected (on the average) decreases as a function of the length of
pat
. For a random English pattern of length 5, the algorithm will typically inspect
i
/4 characters of
string
before finding a match at
i
. Furthermore, the algorithm has been implemented so that (on the average) fewer than
i
+
patlen
machine instructions are executed. These conclusions are supported with empirical evidence and a theoretical analysis of the average behavior of the algorithm. The worst case behavior of the algorithm is linear in
i
+
patlen
, assuming the availability of array space for tables linear in
patlen
plus the size of the alphabet.
The new math of computer programming
Authors: Mills Harlan D.
Published: July 2002

Structured programming has proved to be an important methodology for systematic program design and development. Structured programs are identified as compound function expressions in the algebra of functions. The algebraic properties of these function expressions permit the reformulation (expansion as well as reduction) of a nested subexpression independently of its environment, thus modeling what is known as stepwise program refinement as well as program execution. Finally, structured programming is characterized in terms of the selection and solution of certain elementary equations defined in the algebra of functions. These solutions can be given in general formulas, each involving a single parameter, which display the entire freedom available in creating correct structured programs.
Multidimensional binary search trees used for associative searching
Authors: Bentley Jon Louis
Published: July 2002

This paper develops the multidimensional binary search tree (or
k
-d tree, where
k
is the dimensionality of the search space) as a data structure for storage of information to be retrieved by associative searches. The
k
-d tree is defined and examples are given. It is shown to be quite efficient in its storage requirements. A significant advantage of this structure is that a single data structure can handle many types of queries very efficiently. Various utility algorithms are developed; their proven average running times in an
n
record file are: insertion,
O
(log
n
); deletion of the root,
O
(
n

(
k
-1)/
k

); deletion of a random node,
O
(log
n
); and optimization (guarantees logarithmic performance of searches),
O
(
n
log
n
). Search algorithms are given for partial match queries with
t
keys specified [proven maximum running time of
O
(
n

(
k
-
t
)/
k

)] and for nearest neighbor queries [empirically observed average running time of
O
(log
n
).] These performances far surpass the best currently known algorithms for these tasks. An algorithm is presented to handle any general intersection query. The main focus of this paper is theoretical. It is felt, however, that
k
-d trees could be quite useful in many applications, and examples of potential uses are given.
The application of sequential sampling to simulation
Authors: Sasser W. Earl , Burdick Donald S. , Graham Daniel A. , Naylor Thomas H.
Published: July 2002

Four different sequential sampling procedures are applied to the analysis of data generated by a computer simulation experiment with a multi-item inventory model. For each procedure the cost of computer time required to achieve given levels of statistical precision is calculated. Also the cost of computer time using comparable fixed sample size methods is calculated. The computer costs of fixed sample size procedures versus sequential sampling procedures are compared.
Space/time trade-offs in hash coding with allowable errors
Authors: Bloom Burton H.
Published: July 2002

In this paper trade-offs among certain computational factors in hash coding are analyzed. The paradigm problem considered is that of testing a series of messages one-by-one for membership in a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency.

The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods.

In such applications, it is envisaged that overall performance could be improved by using a smaller core resident hash area in conjunction with the new methods and, when necessary, by using some secondary and perhaps time-consuming test to “catch” the small fraction of errors associated with the new methods. An example is discussed which illustrates possible areas of application for the new methods.

Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time.
An extension of the Munkres algorithm for the assignment problem to rectangular matrices
Authors: Bourgeois François , Lassalle Jean-Claude
Published: July 2002

The assignment problem, together with Munkres proposed algorithm for its solution in square matrices, is presented first. Then the authors develop an extension of this algorithm which permits a solution for rectangular matrices.

Timing results obtained by using an adapted version of Silver's Algol procedure are discussed, and a relation between solution time and problem size is given.
Symmetric list processor
Authors: Weizenbaum J.
Published: July 2002

A list processing system in which each list cell contains both a forward and a backward link as well as a datum is described. This system is intended for imbedding in higher level languages capable of calling functions and subroutines coded in machine language. The presentation is in the form of FORTRAN programs depending on only a limited set of “primitive” machine language subroutines which are also defined. Finally, a set of field, particularly character, manipulation primitives are given to round out the system.
Asynchronous consensus and broadcast protocols
Authors: Bracha Gabriel , Toueg Sam
Published: July 2002

A consensus protocol enables a system of
n
asynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes that can only die and malicious processes that can also send false messages. The class of asynchronous systems with fair schedulers is defined, and consensus protocols that terminate with probability 1 for these systems are investigated. With fail-stop processes, it is shown that ⌈(
n
+ 1)/2⌉ correct processes are necessary and sufficient to reach agreement. In the malicious case, it is shown that ⌈(2
n
+ 1)/3⌉ correct processes are necessary and sufficient to reach agreement. This is contrasted with an earlier result, stating that there is no consensus protocol for the fail-stop case that always terminates within a bounded number of steps, even if only one process can fail. The possibility of reliable broadcast (Byzantine Agreement) in asynchronous systems is also investigated. Asynchronous Byzantine Agreement is defined, and it is shown that ⌈(2
n
+ 1)/3⌉ correct processes are necessary and sufficient to achieve it.
A polynomial algorithm for the min-cut linear arrangement of trees
Authors: Yannakakis Mihalis
Published: July 2002

An algorithm is presented that finds a min-cut linear arrangement of a tree in
O
(
n
log
n
) time. An extension of the algorithm determines the number of pebbles needed to play the black and white pebble game on a tree.
Ray tracing Jell-O brand gelatin
Authors: Heckbert Paul S.
Published: July 2002

New technology is presented for imaging a restricted class of dessert foods.
Relational database design using an object-oriented methodology
Authors: Blaha Michael R. , Premerlani William J. , Rumbaugh James E.
Published: July 2002

Of the many approaches to relational database design, the Object Modeling Technique (OMT) is particularly effective. A comprehensive explanation and two applications show the semantic improvement of OMT over other approaches.
Growth stages of end user computing
Authors: Huff Sid L. , Munro Malcolm C. , Martin Barbara H.
Published: July 2002

The stages of growth and interconnectedness of the applications of end user computing are described in a model that is directed toward management and planning.
Genre taxonomy
Authors: Yoshioka Takeshi , Herman George , Yates JoAnne , Orlikowski Wanda
Published: July 2002

We propose a genre taxonomy as a knowledge repository of communicative structures or "typified actions" enacted by organizational members. The genre taxonomy is intended to help people make sense of diverse types of communicative actions and provide ideas for improving work processes that coordinate the communication of information. It engages several features to achieve this objective. First, the genre taxonomy represents the elements of both genres and genre systems as embedded in a social context reflecting the communicative questions why, what, who, when, where, and how (5W1H). In other words, the genre taxonomy represents the purpose, content, participants, timing, location, and form of communicative action. Second, the genre taxonomy distinguishes between widely recognized genres such as a report and specific genres such as a particular company's technical report, because the difference sheds light on the context of genre use. Third, the genre taxonomy represents use and evolution of a genre over time to help people understand how a genre is used and changed by a community over time. Fourth, the genre taxonomy represents aspects of information coordination via genres, thus providing ideas for improving work processes using genres. We have constructed a prototype of such a genre taxonomy using the Process Handbook, a process knowledge repository developed at MIT. We have included both widely recognized genres such as the memo and specific genres such as those used in the Process Handbook itself. We suggest that this genre taxonomy may be useful in the innovation of new document templates or methods for communication because it helps to clarify different possible uses of similar genres and explicates how genres play a coordination role among people and between people and their tasks.
Consistency in a partitioned network: a survey
Authors: Davidson Susan B. , Garcia-Molina Hector , Skeen Dale
Published: July 2002

Recently, several strategies have been proposed for transaction processing in partitioned distributed database systems with replicated data. These strategies are surveyed in light of the competing goals of maintaining correctness and achieving high availability. Extensions and combinations are then discussed, and guidelines are presented for selecting strategies for particular applications.
Calculating availability and performability measures of repairable computer systems using randomization
Authors: de Souza e Silva Edmundo , Gail H. Richard
Published: July 2002

Repairable computer systems are considered, the availability behavior of which can be modeled as a homogeneous Markov process. The randomization method is used to calculate various measures over a finite observation period related to availability modeling of these systems. These measures include the distribution of the number of events of a certain type, the distribution of the length of time in a set of states, and the probability of a near-coincident fault. The method is then extended to calculate performability distributions. The method relies on coloring subintervals of the finite observation period based on the particular application, and then calculating the measure of interest using these colored intervals.
Legged robots
Authors: Raibert Marc H.
Published: July 2002

Research on legged machines can lead to the construction of useful legged vehicles and help us to understand legged locomotion in animals.
Distributed operating systems
Authors: Tanenbaum Andrew S. , Van Renesse Robbert
Published: July 2002

Distributed operating systems have many aspects in common with centralized ones, but they also differ in certain ways. This paper is intended as an introduction to distributed operating systems, and especially to current university research about them. After a discussion of what constitutes a distributed operating system and how it is distinguished from a computer network, various key design issues are discussed. Then several examples of current research projects are examined in some detail, namely, the Cambridge Distributed Computing System, Amoeba, V, and Eden.
Random number generators: good ones are hard to find
Authors: Park S. K. , Miller K. W.
Published: July 2002

Practical and theoretical issues are presented concerning the design, implementation, and use of a good, minimal standard random number generator that will port to virtually all systems.
Practical performance of Bloom filters and parallel free-text searching
Authors: Ramakrishna M. V.
Published: July 2002

Bloom filter technique of hashing finds several applications, such as in efficient maintenance of differential files, space efficient storage of dictionaries, and parallel free-text searching. The performance of hash transformations with reference to the filter error rate is the focus of this article.
What best predicts computer proficiency?
Authors: Evans Gerald E. , Simkin Mark G.
Published: July 2002

Identifying variables that predict computer aptitude can help educators and employers target potential students and employees. The authors examine a number of possible explanatory variables including demographic profiles, high school achievements, prior computer training and experience, cognitive styles, and problem-solving abilities.
Organizational power and the information services department
Authors: Lucas Henry C.
Published: July 2002

A theory of intraorganizational power is discussed and applied to the information services department. The results of a study of the power of five departments in 40 manufacturing plants is presented. Hypotheses about the levels of power of information processing are not supported by the findings; however, the power theory in general does receive support.The information-services department is perceived as having low levels of power and influence in the organization: Reasons for this unexpected finding are discussed. The paper suggests several explanations for the results and possible problems in the organization. Recommendations to senior management and the information-services department are offered.
The family of concurrent logic programming languages
Authors: Shapiro Ehud
Published: July 2002

Concurrent logic languages are high-level programming languages for parallel and distributed systems that offer a wide range of both known and novel concurrent programming techniques. Being logic programming languages, they preserve many advantages of the abstract logic programming model, including the logical reading of programs and computations, the convenience of representing data structures with logical terms and manipulating them using unification, and the amenability to metaprogramming. Operationally, their model of computation consists of a dynamic set of concurrent processes, communicating by instantiating shared logical variables, synchronizing by waiting for variables to be instantiated, and making nondeterministic choices, possibly based on the availability of values of variables.

This paper surveys the family of concurrent logic programming languages within a uniform operational framework. It demonstrates the expressive power of even the simplest language in the family and investigates how varying the basic synchronization and control constructs affect the expressiveness and efficiency of the resulting languages.

In addition, the paper reports on techniques for sequential and parallel implementation of languages in this family, mentions their applications to date, and relates these languages to the abstract logic programming model, to the programming language PROLOG, and to other concurrent computational models and programming languages.
Measuring parallel processor performance
Authors: Karp Alan H. , Flatt Horace P.
Published: July 2002

Many metrics are used for measuring the performance of a parallel algorithm running on a parallel processor. This article introduces a new metric that has some advantages over the others. Its use is illustrated with data from the Linpack benchmark report and the winners of the Gordon Bell Award.
An empirical study of the reliability of UNIX utilities
Authors: Miller Barton P. , Fredriksen Lars , So Bryan
Published: July 2002

The following section describes the tools we built to test the utilities. These tools include the fuzz (random character) generator, ptyjig (to test interactive utilities), and scripts to automate the testing process. Next, we will describe the tests we performed, giving the types of input we presented to the utilities. Results from the tests will follow along with an analysis of the results, including identification and classification of the program bugs that caused the crashes. The final section presents concluding remarks, including suggestions for avoiding the types of problems detected by our study and some commentary on the bugs we found. We include an Appendix with the user manual pages for fuzz and ptyjig.
THE ARCHAEOLOGY OF THE AFRICAN DIASPORA
Authors: Orser C. E.
Published: July 2002

▪ Abstract  Archaeologists currently studying the African diaspora generally examine three broad issues, in decreasing order of prominence: the material identification of African identity, the archaeology of freedom at maroon sites, and race and racism. While conducting this research, several scholars have learned that many nonarchaeologists are deeply interested in their interpretations. At the present time, the archaeology of the African diaspora is not a truly global pursuit and the New World is overrepresented. This situation should change as archaeologists around the world discover post-Columbian archaeology and take up diasporic investigations.
Bad Endings: American Apocalypsis
Authors: Stewart Kathleen , Harding Susan
Published: July 2002

▪ Abstract  Apocalypticism and millennialism are the dark and light sides of a historical sensibility transfixed by the possibility of imminent catastrophe, cosmic redemption, spiritual transformation, and a new world order. This essay briefly surveys work by anthropologists and like-minded scholars that focuses directly on endtime movements. It then reviews at more length a varied literature focusing on American apocalypticisms and millennialisms. Turning to contemporary America, we survey the ways in which an apocalyptic/millennial sensibility—as a mode of attention, mode of knowing, and voice—has come to inhabit and structure modern American life across a wide range of registers.
Evolutionary Psychology
Authors: Jones Doug
Published: July 2002

▪ Abstract  Studying human behavior in the light of evolutionary theory involves studying the comparative evolutionary history of behaviors (phylogeny), the psychological machinery that generates them (mechanisms), and the adaptive value of that machinery in past reproductive competition (natural selection). To show the value of a phylogenetic perspective, I consider the ethology of emotional expression and the cladistics of primate social systems. For psychological mechanisms, I review evidence for a pan-human set of conceptual building blocks, including innate concepts of things, space, and time, of number, of logic, of natural history, and of “other minds” and social life, which can be combined to generate a vast array of culture-specific concepts. For natural selection, I discuss the sexual selection of sex differences and similarities, and the social selection of moral sentiments and group psychology.
The Visible Evidence of Cultural Producers
Authors: Mahon Maureen
Published: July 2002

▪ Abstract  This review discusses anthropological research that analyzes the practices through which individuals and groups produce music, video, film, visual arts, and theater, and the ideological and institutional frameworks within which these processes occur. Viewing these media and popular culture forms as arenas in which social actors struggle over social meanings and as visible evidence of social processes and social relations, this research addresses the social, political, and aesthetic dimensions of these productions. The review considers the ways these studies treat the material and discursive practices of cultural producers as complex, often contradictory, sites of social reproduction and as potential sites of social transformation. It also considers the ways this research responds to the challenges associated with conducting fieldwork and producing ethnography in and about a global economy and “media-saturated” world.