% % BibTex Entries for the Technical Reports of % The Department of Computer Science at Boston University % % Date of last Update: -- 21:16, 2 Apr 2008 % @techreport{BUCS-TR-1993-001, author = {Azer Bestavros and Spyridon Braoudakis and Euthimios Panagos}, title = {{Performance Evaluation of Two-Shadow Speculative Concurrency Control}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-001}, month = {February}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-001-scc-2s-perf.ps.Z}, abstract = { Speculative Concurrency Control (SCC) is a new concurrency control approach especially suited for real-time database applications. It relies on the use of redundancy to ensure that serializable schedules are discovered and adopted as early as possible, thus increasing the likelihood of the timely commitment of transactions with strict timing constraints. In a recent publication by two of the authors, SCC-nS, a generic algorithm that characterizes a family of SCC-based algorithms was described, and its correctness established by showing that it only admits serializable histories. In this paper, we evaluate the performance of the Two-Shadow SCC algorithm (SCC-2S), a member of the SCC-nS family, which is notable for its minimal use of redundancy. In particular, we show that SCC-2S (as a representative of SCC-based algorithms) provides significant performance gains over the widely used Optimistic Concurrency Control with Broadcast Commit (OCC-BC), under a variety of operating conditions and workloads.} } @techreport{BUCS-TR-1993-002, author = {Azer Bestavros}, title = {{Speculative Concurrency Control for Real-Time Databases}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-002}, month = {January}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-002-scc.ps.Z}, abstract = { In this paper we examine a number of admission control and scheduling protocols for high-performance web servers based on a 2-phase policy for serving HTTP requests. The first ``registration'' phase involves establishing the TCP connection for the HTTP request and parsing/iterpreting its arguments, whereas the second ``service'' phase involves the service/transmission of data in response to the HTTP request. By introducing a delay between these two phases, we show that the performance of a web server could be improved significantly through the adoption of a number of scheduling policies that optimize the utilization of various system components (e.g. memory cache and I/O). In addition, to its premise for improving the performance of a single web server, the delineation between the registration and service phases of an HTTP request may be useful for load balancing purposes on clusters of web servers. We are investigating the use of such a mechanism as part of the Commonwealth testbed being developed at Boston University.} } @techreport{BUCS-TR-1993-003, author = {Marwan Shaban}, title = {{Quadsim Student Manual}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-003}, month = {April}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-003-quadsim.ps.Z}, abstract = { Quadsim is an intermediate code simulator. It allows you to "run" programs that your compiler generates in intermediate code format. Its user interface is similar to most debuggers in that you can step through your program, instruction by instruction, set breakpoints, examine variable values, and so on. The intermediate code format used by Quadsim is that described in [Aho 86]. If your compiler generates intermediate code in this format, you will be able to take intermediate-code files generated by your compiler, load them into the simulator, and watch them "run." You are provided with functions that hide the internal representation of intermediate code. You can use these functions within your compiler to generate intermediate code files that can be read by the simulator. Quadsim was inspired and greatly influenced by [Aho 86]. The material in chapter 8 (Intermediate Code Generation) of [Aho 86] should be considered background material for users of Quadsim.} } @techreport{BUCS-TR-1993-004, author = {Wayne Snyder}, title = {{Proceedings of Sixth International Workshop on Unification}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-004}, month = {April}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-004-unif93proc.ps.Z}, abstract = { The Proceedings of the Sixth International Workshop on Unification contains short papers presented at the workshop which took place at the Dagstuhl conference center in Germany, in June 1992.} } @techreport{BUCS-TR-1993-005, author = {Himanshu Sinha}, title = {{Mermera: Non-coherent Distributed Shared Memory for Parallel Computing}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-005}, month = {May}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-005-mermera.hss.thesis.ps.Z}, abstract = { The proliferation of inexpensive workstations and networks has prompted several researchers to use such distributed systems for parallel computing. Attempts have been made to offer a shared-memory programming model on such distributed memory computers. Most systems provide a shared-memory that is {$\backslash$m coherent} in that all processes that use it agree on the order of all memory events. This dissertation explores the possibility of a significant improvement in the performance of some applications when they use {$\backslash$m non-coherent} memory. First, a new formal model to describe existing non-coherent memories is developed. I use this model to prove that certain problems can be solved using asynchronous iterative algorithms on shared-memory in which the coherence constraints are substantially relaxed. In the course of the development of the model I discovered a new type of non-coherent behavior called {$\backslash$m Local Consistency}. Second, a programming model, {\sc Mermera}, is proposed. It provides programmers with a choice of hierarchically related non-coherent behaviors along with one coherent behavior. Thus, one can trade-off the ease of programming with coherent memory for improved performance with non-coherent memory. As an example, I present a program to solve a linear system of equations using an asynchronous iterative algorithm. This program uses all the behaviors offered by {\sc Mermera}. Third, I describe the implementation of {\sc Mermera} on a BBN Butterfly TC2000 and on a network of workstations. The performance of a version of the equation solving program that uses all the behaviors of {\sc Mermera} is compared with that of a version that uses coherent behavior only. For a system of 1000 equations the former exhibits at least a 5-fold improvement in convergence time over the latter. The version using coherent behavior only does not benefit from employing more than one workstation to solve the problem while the program using non-coherent behavior continues to achieve improved performance as the number of workstations is increased from 1 to 6. This measurement corroborates our belief that non-coherent shared memory can be a performance boon for some applications.} } @techreport{BUCS-TR-1993-006, author = {Abdelsalam Heddaya and Himanshu Sinha}, title = {{An Implementation of Mermera: {A} Shared Memory System that Mixes Coherence with Non-coherence}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-006}, month = {June}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-006-mermera3.ps.Z}, abstract = { Coherent shared memory is a convenient, but inefficient, method of inter-process communication for parallel programs. By contrast, message passing can be less convenient, but more efficient. To get the benefits of both models, several non-coherent memory behaviors have recently been proposed in the literature. We present an implementation of Mermera, a shared memory system that supports both coherent and non-coherent behaviors in a manner that enables programmers to mix multiple behaviors in the same program~\cite{HeddayaS93}. A programmer can debug a Mermera program using coherent memory, and then improve its performance by selectively reducing the level of coherence in the parts that are critical to performance. Mermera permits a trade-off of coherence for performance. We analyze this trade-off through measurements of our implementation, and by an example that illustrates the style of programming needed to exploit non-coherence. We find that, even on a small network of workstations, the performance advantage of non-coherence is compelling. Raw non-coherent memory operations perform 20-40~times better than non-coherent memory operations. An example aplication program is shown to run 5-11~times faster when permitted to exploit non-coherence. We conclude by commenting on our use of the Isis Toolkit of multicast protocols in implementing Mermera.} } @techreport{BUCS-TR-1993-007, author = {Abdelsalam Heddaya and Kihong Park and Himanshu Sinha}, title = {{Using Warp to Control Network Contention in Mermera}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-007}, month = {June}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-007-mermera-warp.ps.Z}, abstract = { Parallel computing on a distributed system, such as a network of workstations, can saturate the communication network, leading to excessive message delays and consequently poor application performance. Current operating systems offer only partial support for flow control protocols that can help insulate application performance from extraneous traffic on the shared network. We examine empirically the consequences of integrating one such protocol, called Warp control~\cite{Park93}, into Mermera, a software shared memory system that supports parallel computing on distributed systems~\cite{HeddayaS93hicss}. Preliminary performance measurements are reported for an asynchronous iterative program to solve a system of linear equations, under varying levels of network contention. The experiments were conducted on a network of seven Sun Sparc~1+ workstations, using an auxiliary traffic generator. These measurements show that Warp succeeds in stabilizing the network behavior when there is high contention, increasing the effective throughput available to the application, and consequently decreasing its completion time. In some cases, however, Warp control does not achieve the performance attainable by fixed size buffering when using a statically optimal buffer size. Based on the nature of Warp and the underlying communication layers, we offer explanations for our results. Our use of Warp to regulate the allocation of network bandwidth emphasizes the possibility for integrating it with the allocation of other resources, such as CPU cycles and disk bandwidth, so as to optimize overall system throughtput, and enable fully-shared execution of parallel programs.} } @techreport{BUCS-TR-1993-008, author = {A.J. Kfoury and M. Wymann-Boeni}, title = {{Fixed Point vs. First-Order Logic on Finite Ordered Structures with Unary Relations}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-008}, month = {August}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-008-monadic-fo-vs-fp.ps.Z}, abstract = { We prove that first order logic is strictly weaker than fixed point logic over every infinite classes of finite ordered structures with additional unary relations: Over these classes there is always an inductive unary relation which cannot be defined by a first-order formula, even when every inductive sentence (i.e., closed formula) can be expressed in first-order over this particular class. Our proof first establishes a property valid for every unary relation definable by first-order logic over these classes which is peculiar to classes of ordered structures with unary relations. In a second step we show that this property itself can be expressed in fixed point logic and can be used to construct a non-elementary unary relation.} } @techreport{BUCS-TR-1993-009, author = {A.J. Kfoury and M. Wymann-Boeni}, title = {{A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-009}, month = {August}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-009-fo-subsets.ps.Z}, abstract = { We give an explicit and easy-to-verify characterization for subsets in finite total orders (infinitely many of them in general) to be definable by the same first-order formula over any class of finite total orders. From this characterization we derive immediately that Beth's definability theorem does not hold in any class of finite total orders, as well as that McColm's first conjecture is true for all classes of finite total orders. Another consequence is a natural 0-1 law for definable subsets on finite total orders expressed as a statement about the possible densities of first-order definable subsets.} } @techreport{BUCS-TR-1993-010, author = {Zhixiang Chen and Steve Homer}, title = {{Learning Unions of Rectangles with Queries}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-010}, month = {September}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-010-learning-rect.ps.Z}, abstract = { We investigate the efficient learnability of unions of $k$ rectangles in the discrete plane $\{1,\ldots,n\}^{2}$ with equivalence and membership queries. We exhibit a learning algorithm that learns any union of $k$ rectangles with $O(k^{3}\log n)$ queries, while the time complexity of this algorithm is bounded by $O(k^{5}\log n)$. We design our learning algorithm by finding ``corners'' and ``edges'' for rectangles contained in the target concept and then constructing the target concept from those ``corners'' and ``edges''. Our result provides a first approach to on-line learning of nontrivial subclasses of unions of intersections of halfspaces with equivalence and membership queries.} } @techreport{BUCS-TR-1993-011, author = {J.B. Wells}, title = {{Typability and Type Checking in the Second-Order Lambda-Calculus Are Equivalent and Undecidable}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-011}, month = {September}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-011-f-undecidable.ps.Z}, abstract = { We consider the problems of typability and type checking in the Girard/Reynolds second-order polymorphic typed lambda calculus, for which we use the short name ``System F'' and which we use in the ``Curry style'' where types are assigned to pure lambda terms. These problems have been considered and proven to be decidable or undecidable for various restrictions and extensions of System F and other related systems, and lower-bound complexity results for System F have been achieved, but they have remained ``embarrassing open problems'' for System F itself. We first prove that type checking in System F is undecidable by a reduction from semi-unification. We then prove typability in System F is undecidable by a reduction from type checking. Since the reverse reduction is already known, this implies the two problems are equivalent. The second reduction uses a novel method of constructing lambda terms such that in all type derivations, specific bound variables must always be assigned a specific type. Using this technique, we can require that specific subterms must be typable using a specific, fixed type assignment in order for the entire term to be typable at all. Any desired type assignment may be simulated. We develop this method, which we call ``constants for free'', for both the lambda-K and lambda-I calculi.} } @techreport{BUCS-TR-1993-012, author = {Azer Bestavros}, title = {{Building Responsive Systems from Physically-correct Specifications}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-012}, month = {October}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-012-tra-responsive.ps.Z}, abstract = { Predictability -- the ability to foretell that an implementation will not violate a set of specified reliability and timeliness requirements -- is a crucial, highly desirable property of responsive embedded systems. This paper overviews a development methodology for responsive systems, which enhances predictability by eliminating potential hazards resulting from physically-unsound specifications. The backbone of our methodology is the Time-constrained Reactive Automaton (TRA) formalism, which adopts a fundamental notion of space and time that restricts expressiveness in a way that allows the specification of only reactive, spontaneous, and causal computation. Using the TRA model, unrealistic systems -- possessing properties such as clairvoyance, caprice, infinite capacity, or perfect timing -- cannot even be specified. We argue that this ``ounce of prevention'' at the specification level is likely to spare a lot of time and energy in the development cycle of responsive systems -- not to mention the elimination of potential hazards that would have gone, otherwise, unnoticed. The TRA model is presented to system developers through the Cleopatra programming language. Cleopatra features a C-like imperative syntax for the description of computation, which makes it easier to incorporate in applications already using C. It is event-driven, and thus appropriate for embedded process control applications. It is object-oriented and compositional, thus advocating modularity and reusability. Cleopatra is semantically sound; its objects can be transformed, mechanically and unambiguously, into formal TRA automata for verification purposes, which can be pursued using model-checking or theorem proving techniques. Since 1989, an ancestor of Cleopatra has been in use as a specification and simulation language for embedded time-critical robotic processes.} } @techreport{BUCS-TR-1993-013, author = {Marwan Shaban}, title = {{A Minimal {GB} Parser}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-013}, month = {October}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-013-gb-parser.ps.Z}, abstract = { We describe a GB parser implemented along the lines of those written by Fong [Fong91] and Dorr [Dorr87]. The phrase structure recovery component is an implementation of Tomita's generalized LR parsing algorithm (described in [Tomi86]), with recursive control flow (similar to Fong's implementation). The major principles implemented are government, binding, bounding, trace theory, case theory, theta-theory, and barriers. The particular version of GB theory we use is that described by Haegeman [Haeg91]. The parser is minimal in the sense that it implements the major principles needed in a GB parser, and has fairly good coverage of linguistically interesting portions of the English language.} } @techreport{BUCS-TR-1993-014, author = {Azer Bestavros and Biao Wang}, title = {{Multi-version Speculative Concurrency Control with Delayed Commit}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-014}, month = {October}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-014-scc-delayed-commit.ps.Z}, abstract = { This paper presents an algorithm which extends the relatively new notion of speculative concurrency control by delaying the commitment of transactions, thus allowing other conflicting transactions to continue execution and commit rather than restart. This algorithm propagates uncommitted data to other outstanding transactions thus allowing more speculative schedules to be considered. The algorithm is shown always to find a serializable schedule, and to avoid cascading aborts. Like speculative concurrency control, it considers strictly more schedules than traditional concurrency control algorithms. Further work is needed to determine which of these speculative methods performs better on actual transaction loads.} } @techreport{BUCS-TR-1993-015, author = {Robert Carter and Kihong Park}, title = {{How good are genetic algorithms at finding large cliques: an experimental}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-015}, month = {November}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-015-ga-clique.ps.Z}, abstract = { This paper investigates the power of genetic algorithms at solving the MAX-CLIQUE problem. We measure the performance of a standard genetic algorithm on an elementary set of problem instances consisting of embedded cliques in random graphs. We indicate the need for improvement, and introduce a new genetic algorithm, the {$\backslash$m multi-phase annealed GA}, which exhibits superior performance on the same problem set. As we scale up the problem size and test on ``hard'' benchmark instances, we notice a degraded performance in the algorithm caused by premature convergence to local minima. To alleviate this problem, a sequence of modifications are implemented ranging from changes in input representation to systematic local search. The most recent version, called {$\backslash$m union GA}, incorporates the features of union cross-over, greedy replacement, and diversity enhancement. It shows a marked speed-up in the number of iterations required to find a given solution, as well as some improvement in the clique size found. We discuss issues related to the SIMD implementation of the genetic algorithms on a Thinking Machines CM-5, which was necessitated by the intrinsically high time complexity ($O(n^3)$) of the serial algorithm for computing one iteration. Our preliminary conclusions are: (1) a genetic algorithm needs to be heavily customized to work ``well'' for the clique problem; (2) a GA is computationally very expensive, and its use is only recommended if it is known to find larger cliques than other algorithms; (3) although our customization effort is bringing forth continued improvements, there is no clear evidence, at this time, that a GA will have better success in circumventing local minima.} } @techreport{BUCS-TR-1993-016, author = {A.J. Kfoury and M. Wymann-Boeni}, title = {{An Algebraic Characterization of First-Order Definability}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-016}, month = {November}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-016-fo-definability.ps.Z}, abstract = { We give a variable-free relational calculus which defines exactly all first-order definable relations in a arbitrary structure. We then show that, over an arbitrary class $\C$ of finite ordered structures with signature $\{ \LE, R\_1, \ldots, R\_\alpha \}$, the unary relations uniformly defined by this calculus over $\C$ are characterized by a another simplified variable-free calculus which we call $\Q$. $\Q$ is the least set of formal expressions such that: \begin{eqnarray*} \Q &\supseteq&\ \{ \varnothing, R\_1,\ldots, R\_\alpha \}\ \cup\ & &\ \{ (Q\PLUS x)\ |\ Q\in\Q, x\in\omega \cup \{\infty\} \}\ \cup \ \{ (Q\MINUS x)\ |\ Q\in\Q, x\in\omega \cup \{\infty\} \}\ \cup \ & &\ \{ (\NOT Q)\ |\ Q\in\Q\}\ \cup \ \{ (Q\_1\AND Q\_2)\ |\ Q\_1,Q\_2\in\Q\}\ \cup \ \{ (Q\_1\OR Q\_2)\ |\ Q\_1,Q\_2\in\Q\}\ .\ $\backslash$nd{eqnarray*} where $\PLUS$ and $\MINUS$ are ``shift'' operators defined in Section 3. $\backslash$nd{abstract}} } @techreport{BUCS-TR-1993-017, author = {Joe Wells}, title = {{A Direct Algorithm for Type Inference in the Rank 2 Fragment of the Second-Order Lambda-Calculus}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-017}, month = {November}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-017-finite-rank.ps.Z}, abstract = { We study the problem of type inference for a family of polymorphic type disciplines containing the power of Core-ML. This family comprises all levels of the stratification of the second-order lambda-calculus by ``rank'' of types. We show that typability is an undecidable problem at every rank k >= 3 of this stratification. While it was already known that typability is decidable at rank <= 2, no direct and easy-to-implement algorithm was available. To design such an algorithm, we develop a new notion of reduction and show how to use it to reduce the problem of typability at rank 2 to the problem of acyclic semi-unification. A by-product of our analysis is the publication of a simple solution procedure for acyclic semi-unification.} } @techreport{BUCS-TR-1993-018, author = {Said Jahama and A.J. Kfoury}, title = {{A General Theory of Semi-Unification}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-018}, month = {December}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-018-gsureport.ps.Z}, abstract = { Various restrictions on the terms allowed for substitution give rise to different cases of semi-unification. Semi-unification on finite and regular terms has already been considered in the literature. We introduce a general case of semi-unification where substitutions are allowed on non-regular terms, and we prove the equivalence of this general case to a well-known undecidable data base dependency problem, thus establishing the undecidability of general semi-unification. We present a unified way of looking at the various problems of semi-unification. We give some properties that are common to all the cases of semi-unification. We also the principality property and the solution set for those problems. We prove that semi-unification on general terms has the principality property. Finally, we present a recursive inseparability result between semi-unification on regular terms and semi-unification on general terms.} } @techreport{BUCS-TR-1993-019, author = {Said Jahama}, title = {{Type Reconstruction in the Presence of Polymorphic Recursion and Recursive Types}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-019}, month = {December}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-019-recursivetype.ps.Z}, abstract = { We establish the equivalence of type reconstruction with polymorphic recursion and recursive types is equivalent to regular semi-unification which proves the undecidability of the corresponding type reconstruction problem. We also establish the equivalence of type reconstruction with polymorphic recursion and positive recursive types to a special case of regular semi-unification which we call positive regular semi-unification. The decidability of positive regular semi-unification is an open problem.} } @techreport{BUCS-TR-1993-020, author = {Azer Bestavros and Mohammad Makarechian}, title = {{{AIDA}-based Distributed File System}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1993-020}, month = {December}, year = {1993}, url = {http://www.cs.bu.edu/techreports/1993-020-aida-dfs.ps.Z}, abstract = { This paper describes a prototype implementation of a Distributed File System (DFS) based on the Adaptive Information Dispersal Algorithm (AIDA). Using AIDA, a file block is encoded and dispersed into smaller blocks stored on a number of DFS nodes distributed over a network. The implementation devises file creation, read, and write operations. In particular, when reading a file, the DFS accepts an optional timing constraint, which it uses to determine the level of redundancy needed for the read operation. The tighter the timing constraint, the more nodes in the DFS are queried for encoded blocks. Write operations update all blocks in all DFS nodes--with future implementations possibly including the use of read and write quorums. This work was conducted under the supervision of Professor Azer Bestavros (best@cs.bu.edu) in the Computer Science Department as part of Mohammad Makarechian's Master's project.} } @techreport{BUCS-TR-1994-001, author = {Steve Homer and Marcus Peinado}, title = {{On the Performance of Polynomial-time {CLIQUE} Algorithms on Very Large Graphs}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-001}, month = {January}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-001-maxclique.ps.Z}, abstract = { The performance of a randomized version of the subgraph-exclusion algorithm (called Ramsey) for CLIQUE by Boppana and Halld{\'{ }}{o}rsson is studied on very large graphs. We compare the performance of this algorithm with the performance of two common heuristic algorithms, the greedy heuristic and a version of simulated annealing. These algorithms are tested on graphs with up to 10,000 vertices on a workstation and graphs as large as 70,000 vertices on a Connection Machine. Our implementations establish the ability to run clique approximation algorithms on very large graphs. We test our implementations on a variety of different graphs. Our conclusions indicate that on randomly generated graphs minor changes to the distribution can cause dramatic changes in the performance of the heuristic algorithms. The Ramsey algorithm, while not as good as the others for the most common distributions, seems more robust and provides a more even overall performance. In general, and especially on deterministically generated graphs, a combination of simulated annealing with either the Ramsey algorithm or the greedy heuristic seems to perform best. This combined algorithm works particularly well on large Keller and Hamming graphs and has a competitive overall performance on the DIMACS benchmark graphs.} } @techreport{BUCS-TR-1994-002, author = {Zhixiang Chen and Steven Homer}, title = {{On Learning Counting Functions With Queries}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-002}, month = {February}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-002-counting.ps.Z}, abstract = { We investigate the problem of learning disjunctions of counting functions, which are general cases of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number $p$, the class of disjunctions of integer-weighted counting functions with modulus $p$ over the domain $Z^{n}\_{q}$ (or $Z^{n}$) for any given integer $q \ge 2$ is polynomial time learnable using at most $n+1$ equivalence queries, where the hypotheses issued by the learner are disjunctions of at most $n$ counting functions with weights from $Z\_{p}$. The result is obtained through learning linear systems over an arbitrary field. In general a counting function may have a composite modulus. We prove that, for any given integer $q \ge 2$, over the domain $Z\_{2}^{n}$, the class of read-once disjunctions of Boolean-weighted counting functions with modulus $q$ is polynomial time learnable with only one equivalence query, and the class of disjunctions of $\log \log n$ Boolean-weighted counting functions with modulus $q$ is polynomial time learnable.tions, which are general cases Finally, we present an algorithm for learning graph-based counting functions.} } @techreport{BUCS-TR-1994-003, author = {Abdelsalam Heddaya and Kihong Park}, title = {{Mapping parallel iterative algorithms onto workstation networks}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-003}, month = {February}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-003-parallel-comm.ps.Z}, abstract = { For communication-intensive parallel applications, the maximum degree of concurrency achievable is limited by the communication throughput made available by the network. In previous work, we showed experimentally that the performance of certain parallel applications running on a workstation network can be enhanced significantly if a congestion control protocol is used to enhance network performance. In this paper, we characterize and analyze the communication requirements of a large class of supercomputing applications that fall under the category of fixed-point problems, amenable to solution by parallel iterative methods. This results in a set of interface and architectural features sufficient for the efficient implementation of the application over a large-scale distributed system. In particular, we propose a direct link between the application and network layer, supporting congestion control actions at both ends. This in turn enhances the system's responsiveness to network congestion, improving performance. Preliminary results of a prototype system are summarized showing the efficacy of our scheme to support large-scale parallel computations. We conclude with a description of a full implementation in progress.} } @techreport{BUCS-TR-1994-004, author = {Marwan Shaban}, title = {{A Hybrid {GLR} Algorithm for Parsing with Epsilon Grammars}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-004}, month = {{March 22}}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-004-e-grammar-parser.ps.Z}, abstract = { We give a hybrid algorithm for parsing $$\backslash$psilon$-grammars based on Tomita's non-$$\backslash$psilon$-grammar parsing algorithm (\cite{tomi86}) and Nozohoor-Farshi's $$\backslash$psilon$-grammar recognition algorithm (\cite{fars91}). The hybrid parser handles the same set of grammars handled by Nozohoor-Farshi's recognizer. The algorithm's details and an example of its use are given. We also discuss the deployment of the hybrid algorithm within a GB parser, and the reason an $$\backslash$psilon$-grammar parser is needed in our GB parser.} } @techreport{BUCS-TR-1994-005, author = {Marwan Shaban}, title = {{Structure Sharing and Parallelization in a {GB} Parser}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-005}, month = {{March 22}}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-005-structure-sharing.ps.Z}, abstract = { By utilizing structure sharing among its parse trees, a GB parser can increase its efficiency dramatically. Using a GB parser which has as its phrase structure recovery component an implementation of Tomita's algorithm (as described in \cite{tomi86}), we investigate how a GB parser can preserve the structure sharing output by Tomita's algorithm. In this report, we discuss the implications of using Tomita's algorithm in GB parsing, and we give some details of the structure-sharing parser currently under construction. We also discuss a method of parallelizing a GB parser, and relate it to the existing literature on parallel GB parsing. Our approach to preserving sharing within a shared-packed forest is applicable not only to GB parsing, but anytime we want to preserve structure sharing in a parse forest in the presence of features.} } @techreport{BUCS-TR-1994-006, author = {A.J. Kfoury and J.B. Wells}, title = {{Adding Polymorphic Abstraction to {ML} (Detailed Abstract)}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-006}, month = {May}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-006-polymorphic-abstraction.ps.Z}, abstract = { The ML programming language restricts type polymorphism to occur only in the ``let-in'' construct and requires every occurrence of a formal parameter of a function (a lambda abstraction) to have the same type. Milner in 1978 refers to this restriction (which was adopted to help ML achieve automatic type inference) as a serious limitation. We show that this restriction can be relaxed enough to allow universal polymorphic abstraction without losing automatic type inference. This extension is equivalent to the rank-2 fragment of system F. We precisely characterize the additional program phrases (lambda terms) that can be typed with this extension and we describe typing anomalies both before and after the extension. We discuss how macros may be used to gain some of the power of rank-3 types without losing automatic type inference. We also discuss user-interface problems in how to inform the programmer of the possible types a program phrase may have.} } @techreport{BUCS-TR-1994-007, author = {Azer Bestavros and Spyridon Braoudakis}, title = {{Timeliness via Speculation for Real-Time Databases}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-007}, month = {May}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-007-rtdbs-timeliness.ps.Z}, abstract = { Various concurrency control algorithms differ in the time when conflicts are detected, and in the way they are resolved. In that respect, the Pessimistic and Optimistic Concurrency Control (PCC and OCC) alternatives represent two extremes. PCC locking protocols detect conflicts as soon as they occur and resolve them using {$\backslash$m blocking}. OCC protocols detect conflicts at transaction commit time and resolve them using {$\backslash$m rollbacks} (restarts). For real-time databases, blockages and rollbacks are hazards that increase the likelihood of transactions missing their deadlines. We propose a {$\backslash$m Speculative} Concurrency Control (SCC) technique that minimizes the impact of blockages and rollbacks. SCC relies on the use of added system resources to {$\backslash$m speculate} on potential serialization orders and to ensure that if such serialization orders materialize, the hazards of blockages and roll-backs are minimized. We present a number of SCC-based algorithms that differ in the level of speculation they introduce, and the amount of system resources (mainly memory) they require. We show the performance gains (in terms of number of satisfied timing constraints) to be expected when a representative SCC algorithm (SCC-2S) is adopted.} } @techreport{BUCS-TR-1994-008, author = {Azer Bestavros}, title = {{Towards Physically-Correct Specifications of Embedded Real-Time Systems}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-008}, month = {May}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-008-physical-correctness.ps.Z}, abstract = { Predictability (the ability to foretell that an implementation will not violate a set of specified reliability and timeliness requirements) is a crucial, highly desirable property of responsive embedded systems. This paper overviews a development methodology for responsive systems, which enhances predictability by eliminating potential hazards resulting from physically-unsound specifications. The backbone of our methodology is a formalism that restricts expressiveness in a way that allows the specification of only reactive, spontaneous, and causal computation. Unrealistic systems (possessing properties such as clairvoyance, caprice, infinite capacity, or perfect timing) cannot even be specified. We argue that this ``ounce of prevention'' at the specification level is likely to spare a lot of time and energy in the development cycle of responsive systems -- not to mention the elimination of potential hazards that would have gone, otherwise, unnoticed.} } @techreport{BUCS-TR-1994-009, author = {Kihong Park}, title = {{A lower-bound result on the power of a genetic algorithm}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-009}, month = {{October 12}}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-009-lowerbound-ga.ps.Z}, abstract = { This paper presents a lower-bound result on the computational power of a genetic algorithm in the context of combinatorial optimization. We describe a new genetic algorithm, the merged genetic algorithm, and prove that for the class of monotonic functions, the algorithm finds the optimal solution, and does so with an exponential convergence rate. The analysis pertains to the ideal behavior of the algorithm where the main task reduces to showing convergence of probability distributions over the search space of combinatorial structures to the optimal one. We take exponential convergence to be indicative of efficient solvability for the sample-bounded algorithm, although a sampling theory is needed to better relate the limit behavior to actual behavior. The paper concludes with a discussion of some immediate problems that lie ahead.} } @techreport{BUCS-TR-1994-010, author = {Robert Carter and Kihong Park}, title = {{On the effectiveness of genetic search in combinatorial optimization}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-010}, month = {{November 10}}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-010-genetic\_search.ps.Z}, abstract = { In this paper, we study the efficacy of genetic algorithms in the context of combinatorial optimization. In particular, we isolate the effects of cross-over, treated as the central component of genetic search. We show that for problems of nontrivial size and difficulty, the contribution of cross-over search is marginal, both synergistically when run in conjunction with mutation and selection, or when run with selection alone, the reference point being the search procedure consisting of just mutation and selection. The latter can be viewed as another manifestation of the Metropolis process. Considering the high computational cost of maintaining a population to facilitate cross-over search, its marginal benefit renders genetic search inferior to its singleton-population counterpart, the Metropolis process, and by extension, simulated annealing. This is further compounded by the fact that many problems arising in practice may inherently require a large number of state transitions for a near-optimal solution to be found, making genetic search infeasible given the high cost of computing a single iteration in the enlarged state-space.} } @techreport{BUCS-TR-1994-011, author = {Spyridon Braoudakis}, title = {{Concurrency Control Protocols for Real-Time Databases, Phd Thesis}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-011}, month = {{November 12}}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-011-realtime-databases.ps.Z}, abstract = { Concurrency control methods developed for traditional database systems are not appropriate for real-time database systems (RTDBS), where, in addition to database consistency requirements, satisfying timing constraints is an integral part of the correctness criterion. Most real-time concurrency control protocols considered in the literature combine time-critical scheduling with traditional concurrency control methods to conform to transaction timing constraints. These methods rely on either transaction blocking or restarts, both of which are inappropriate for real-time concurrency control because of the unpredictability they introduce. Moreover, RTDBS performance objectives differ from those of conventional database systems in that maximizing the number of transactions that complete before their deadlines becomes the decisive performance objective, rather than merely maximizing concurrency (or throughput). Recently, Speculative Concurrency Control (SCC) was proposed as a categorically different approach to concurrency control for RTDBS. SCC relies on the use of redundant processes ( shadows), which speculate on alternative schedules, once conflicts that threaten the consistency of the database are detected. SCC algorithms utilize added system resources to ensure that correct (serializable) executions are discovered and adopted as early as possible, thus increasing the likelihood of the timely commitment of transactions. This dissertation starts by reviewing the Order-Based SCC (SCC-OB) algorithm which associates almost as many shadows as there are serialization orders of transactions. After demonstrating SCC-OB's excessive use of redundancy, a host of novel SCC-based protocols is introduced. Conflict-Based SCC (SCC-CB) reduces the number of shadows that a running transaction needs to keep by maintaining one shadow per uncommitted conflicting transaction. It is shown that the quadratic number of shadows maintained by SCC-CB is optimal, covering all serialization orders produced by SCC-OB. SCC-CB's correctness is established by showing that it admits only serializable histories. Next, the trade-off between the number of shadows and timeliness is considered. A generic SCC algorithm (SCC-kS) that operates under a limited redundancy assumption is presented; it allows no more than a constant number $k$ of shadows to coexist on behalf of any uncommitted transaction. Next, a novel technique is proposed that incorporates additional information such as deadline, priority and criticalness within the SCC methodology. SCC with Deferred Commit (SCC-DC) utilizes this additional information to improve the timeliness through the controlled deferment of transaction commitments. A probabilistic Value Induced Shadow Allocation (VISA) policy is developed which aims at preserving the most valuable shadows for each system transaction. The thesis of this dissertation is that SCC-based algorithms offer a new dimension, redundancy, to improve the timeliness of RTDBS. SCC-based algorithms are efficient (quadratic number of shadows is optimal), scalable (redundancy can be traded-off for timeliness), and easily amendable (deadline and priority information can be incorporated). (Major Advisor: Azer Bestavros)} } @techreport{BUCS-TR-1994-012, author = {Abdelsalam Heddaya and Amr Fahmy}, title = {{{OS} Support for Portable Bulk Synchronous Parallel Programs}}, institution = {Computer Science Department, Boston University Computer Science Department, Harvard University}, number = {BUCS-TR-1994-012}, month = {{December 5}}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-012-bsp-os.ps.Z}, abstract = { For parallel programs to become portable, they must be executable with uniform efficiency on a variety of hardware platforms, which is not the case at present. In 1990, Valiant proposed Bulk-Synchronous Parallelism (BSP) as a model on which portable parallel programs can be built. We argue that shared-memory BSP is efficiently implementable on a wide variety of parallel hardware, and that BSP forms a useful basis for providing an even higher level programming interface based on Sequential Consistency (SC). A list of memory and thread management features needed to support BSP and SC parallel programs are given, under the assumption that the parallel computer is space-shared among multiple parallel task, rather than time-shared. Known techniques to realize efficiently the most important of these features are sketched.} } @techreport{BUCS-TR-1994-013, author = {Alberto Oliart}, title = {{An Algorithm for Inferring Quasi-Static Types}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-013}, month = {November}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-013-quasi-static-types.ps.Z}, abstract = { This report presents an algorithm, and its implementation, for doing type inference in the context of Quasi-Static Typing (QST) ["Quasy-static Typing." Satish Thatte Proc. ACM Symp. om Principles of Programming Languages, 1988]. The package infers types a la ``QST'' for the simply typed lambda-calculus.} } @techreport{BUCS-TR-1994-014, author = {A.J. Kfoury and J.B. Wells}, title = {{New Notions of Reduction and Non-Semantic Proofs of Beta-Strong Normalization in Typed Lambda-Calculi}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-014}, month = {{December 19}}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-014-strong-normalization.ps.Z}, abstract = { Two new notions of reduction for terms of the lambda-calculus are introduced and the question of whether a lambda-term is beta-strongly normalizing is reduced to the question of whether a lambda-term is merely normalizing under one of the new notions of reduction. This leads to a new way to prove beta-strong normalization for typed lambda-calculi. Instead of the usual semantic proof style based on Girard's ``candidats de r{\'{ }}eductibilit{\'{ }}e'', termination can be proved using a decreasing metric over a well-founded ordering in a style more common in the field of term rewriting. This new proof method is applied to the simply-typed lambda-calculus and the system of intersection types.} } @techreport{BUCS-TR-1994-015, author = {S. Sclaroff and A.P. Pentland}, title = {{Search by Shape Examples: Modeling Nonrigid Deformation}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-015}, month = {October}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-015-search-by-shape-example.ps.Z}, abstract = { We describe our work on shape-based image database search using the technique of modal matching. Modal matching employs a deformable shape decomposition that allows users to select example objects and have the computer efficiently sort the set of objects based on the similarity of their shape. Shapes are compared in terms of the types of nonrigid deformations (differences) that relate them. The modal decomposition provides deformation ``control knobs'' for flexible matching and thus allows for selecting weighted subsets of shape parameters that are deemed significant for a particular category or context. We demonstrate the utility of this approach for shape comparison in 2-D image databases; however, the general formulation is applicable to signals of any dimensionality.} } @techreport{BUCS-TR-1994-016, author = {S. Sclaroff and A.P. Pentland}, title = {{Physically-Based Combinations of Views: Representing Rigid and Nonrigid Motion}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1994-016}, month = {November}, year = {1994}, url = {http://www.cs.bu.edu/techreports/1994-016-phys-based-comb-of-views.ps.Z}, abstract = { Nonrigid motion can be described as morphing or blending between extremal shapes, e.g., heart motion can be described as transitioning between the systole and diastole states. Using physically-based modeling techniques, shape similarity can be measured in terms of forces and strain. This provides a physically-based coordinate system in which motion is characterized in terms of physical similarity to a set of extremal shapes. Having such a low-dimensional characterization of nonrigid motion allows for the recognition and the comparison of different types of nonrigid motion.} } @techreport{BUCS-TR-1995-001, author = {David Durand and Anja Haake and David Hicks and Fabio Vitali}, title = {{Proceedings of the Workshop on Versioning in Hypertext Systems}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-001}, month = {{February 7}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-001-hypertext-versioning-workshop}, abstract = { This report contains 9 papers presented at a workshop on version management and hypertext, as well as a summary introduction by the organizers. These papers address requirements, solutions, and research issues related to the management of hypertext databases. Version management is not only a key application requirement in some domains (like design journals and electronic manuals) but provides a way to preserve the integrity of links in a changing hyperbase.} } @techreport{BUCS-TR-1995-002, author = {Azer Bestavros and Robert Carter and Mark Crovella and Carlos Cunha and Abdelsalam Heddaya and Sulaiman Mirdad}, title = {{Application-Level Document Caching in the Internet}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-002}, month = {{February 15}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-002-web-client-caching.ps.Z}, abstract = { With the increasing demand for document transfer services such as the World Wide Web comes a need for better resource management to reduce the latency of documents in these systems. To address this need, we report on the potential for document caching at the application level in document transfer services. We collected traces of over 250 executions of Mosaic, reflecting actual user requests for WWW documents. Using those traces, we study the tradeoffs between caching at three levels in the system, and the potential for use of application-level information in the caching system. Our traces show that while a high hit rate in terms of URLs is achievable, a much lower hit rate is possible in terms of bytes, because most profitably-cached documents are small. We considered the performance of caching when applied at the level of individual user sessions, at the level of individual hosts, and at the level of a collection of hosts on a single LAN. We show that the performance gain achievable by caching at the session level (which is straightforward to implement) is nearly all of that achievable at the LAN level (where caching is more difficult to implement). However, when resource requirements are considered, LAN level caching becomes much more desirable, since it can achieve a given level of caching performance using a much smaller amount of cache space. Finally, we consider the use of organizational boundary information as an example of the potential for use of application-level information in caching. We show that while it is desirable to cache local documents at the LAN level, the opposite is true at the session level, where remote documents are more profitably cached.} } @techreport{BUCS-TR-1995-003, author = {Azer Bestavros}, title = {{Demand-based Document Dissemination for the World-Wide Web}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-003}, month = {{February 15}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-003-web-server-dissemination.ps.Z}, abstract = { We analyzed the logs of the cs-www.bu.edu HTTP server for the month of January 1995. Our analysis showed that remote HTTP accesses were confined to a small subset of documents. Using an analytical model of server popularity and file access profiles, we show that by disseminating the most popular documents on servers (proxies) closer to the clients, network traffic could be reduced considerably, while server loads are balanced. We argue that this process could be generalized so as to provide for an automated demand-based duplication of documents. We believe that such server-based information dissemination protocols will be more effective at reducing both network bandwidth and document retrieval times than client-based caching protocols.} } @techreport{BUCS-TR-1995-004, author = {Jerzy Tiuryn}, title = {{Equational Axiomatization of Bicoercibility for Polymorphic Types}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-004}, month = {{February 16}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-004-coercibility.ps.Z}, abstract = { Two polymorphic types \sigma and \tau are said to be bicoercible if there is a coercion from \sigma to \tau and conversely. We give a complete equational axiomatization of bicoercible types and prove that the relation of bicoercibility is decidable.} } @techreport{BUCS-TR-1995-005, author = {Azer Bestavros and Spyridon Braoudakis}, title = {{Speculative Concurrency Control with Deferred Commitment for Real-Time Databases}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-005}, month = {{February 20}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-005-scc-dc.ps.Z}, abstract = { A problem with Speculative Concurrency Control algorithms and other common concurrency control schemes using forward validation is that committing a transaction as soon as it finishes validating, may result in a value loss to the system. Haritsa showed that by making a lower priority transaction wait after it is validated, the number of transactions meeting their deadlines is increased, which may result in a higher value-added to the system. SCC-based protocols can benefit from the introduction of such delays by giving optimistic shadows with high value-added to the system more time to execute and commit instead of being aborted in favor of other validating transactions, whose value-added to the system is lower. In this paper we present and evaluate an extension to SCC algorithms that allows for commit deferments.} } @techreport{BUCS-TR-1995-006, author = {Azer Bestavros}, title = {{Using Speculation to Reduce Server Load and Service Time on the {WWW}}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-006}, month = {{February 21}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-006-speculative-service.ps.Z}, abstract = { Speculative service implies that a client's request for a document is serviced by sending, in addition to the document requested, a number of other documents that the server speculates will be requested by the client in the near future. This speculation is based on statistical information that the server maintains for each document it serves. The notion of speculative service is analogous to prefetching, which is used to improve cache performance in distributed/parallel shared memory systems, with the exception that servers (not clients) control when and what to prefetch. Using trace simulations based on the logs of our departmental HTTP server http://cs-www.bu.edu, we show that both server load and service time could be reduced considerably, if speculative service is used. This is above and beyond what is currently achievable using client-side caching and server-side dissemination. We identify a number of parameters that could be used to fine-tune the level of speculation performed by the server based on the level of lookahead, the state of the network, the tradeoffs between bulk and individual transmission of documents, and the relative popularity of documents, among other factors.} } @techreport{BUCS-TR-1995-007, author = {A.J. Kfoury and J.B. Wells}, title = {{Addendum to ``New Notions of Reduction and Non-Semantic Proofs of Beta Strong Normalization in Typed Lambda Calculi''}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-007}, month = {March}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-007-strong-normalization-addendum.ps.Z}, abstract = { This is an addendum to our technical report BUCS TR-94-014 of December 19, 1994. It clarifies some statements, adds information on some related research, includes a comparison with research be de Groote, and fixes two minor mistakes in a proof.} } @techreport{BUCS-TR-1995-008, author = {S. Sclaroff and A.P. Pentland}, title = {{Modal Matching for Correspondence and Recognition}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-008}, month = {March}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-008-modal-matching.ps.Z}, abstract = { Modal matching is a new method for establishing correspondences and computing canonical descriptions. The method is based on the idea of describing objects in terms of generalized symmetries, as defined by each object's eigenmodes. The resulting modal description is used for object recognition and categorization, where shape similarities are expressed as the amounts of modal deformation energy needed to align the two objects. In general, modes provide a global-to-local ordering of shape deformation and thus allow for selecting which types of deformations are used in object alignment and comparison. In contrast to previous techniques, which required correspondence to be computed with an initial or prototype shape, modal matching utilizes a new type of finite element formulation that allows for an object's eigenmodes to be computed directly from available image information. This improved formulation provides greater generality and accuracy, and is applicable to data of any dimensionality. Correspondence results with 2-D contour and point feature data are shown, and recognition experiments with 2-D images of hand tools and airplanes are described.} } @techreport{BUCS-TR-1995-009, author = {Peter Gacs}, title = {{A New Version of Toom's Proof}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-009}, month = {{March 27}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-009-toom-proof.ps.Z}, abstract = { There are several proofs now for the stability of Toom's example of a two-dimensional stable cellular automaton and its application to fault-tolerant computation. Simon and Berman simplified and strengthened Toom's original proof: the present report is simplified exposition of their proof.} } @techreport{BUCS-TR-1995-010, author = {Carlos Cunha and Azer Bestavros and Mark Crovella}, title = {{Characteristics of {WWW} Client-based Traces}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-010}, month = {{April 1}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-010-www-client-traces.ps.Z}, abstract = { The explosion of WWW traffic necessitates an accurate picture of WWW use, and in particular requires a good understanding of client requests for WWW documents. To address this need, we have collected traces of actual executions of NCSA Mosaic, reflecting over half a million user requests for WWW documents. In this paper we present a descriptive statistical summary of the traces we collected, which identifies a number of trends and reference patterns in WWW use. In particular, we show that many characteristics of WWW use can be modelled using power-law distributions, including the distribution of document sizes, the popularity of documents as a function of size, the distribution of user requests for documents, and the number of references to documents as a function of their overall rank in popularity (Zipf's law). In addition, we show how the power-law distributions derived from our traces can be used to guide system designers interested in caching WWW documents. --- Our client-based traces are available via FTP from http://www.cs.bu.edu/techreports/1995-010-www-client-traces.tar.gz http://www.cs.bu.edu/techreports/1995-010-www-client-traces.a.tar.gz} } @techreport{BUCS-TR-1995-011, author = {Azer Bestavros and Carlos Cunha}, title = {{A Prefetching Protocol Using Client Speculation for the {WWW}}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-011}, month = {{May 8}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/0000-000-TBA.html}, abstract = { In an earlier paper, the potential of speculation (server-initiated prefetching) in distributed information systems (such as the WWW) was investigated and shown to be effective in reducing service time and server load. This speculation was based on statistical information that the server maintains for each document it serves. In this paper we study the performance of a client-initiated prefetching protocol, whereby speculation is based on past user-specific access patterns. In this paper we present results of trace-driven simulation experiments we performed using extensive user traces.} } @techreport{BUCS-TR-1995-012, author = {Patrick Cai and Azer Bestavros}, title = {{Object-Oriented Animation on the World Wide Web}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-012}, month = {{May 8}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-012-mosaic-animation.ps.Z}, abstract = { We propose that video/audio animation be considered as a first-class object on the World Wide Web. Animation is a very "bandwidth-efficient" alternative to using video streams, especially for presentations involving mathematical objects and interactions. We present an object-oriented model that supports drawing-based and frame-based animation. Based on that model, we describe an extension of the HyperText Markup Language to support these capabilities. BU-NCSA Mosanim, a modified version of the NCSA Mosaic for X(v2.5), was developed and is available for distribution via anonymous FTP to demonstrate the concepts and potentials of animation in presentations and interactive game playing over the web.} } @techreport{BUCS-TR-1995-013, author = {Azer Bestavros and Yueh-Lin Liu}, title = {{Simulation of Hardware Dynamic Scheduling on the {DLX} Architecture}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-013}, month = {{June 6}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-013-dynamic-scheduling-dlxsim.html}, abstract = { We describe our extention of the existing DLX simulator (DLXsim), available from the University of California at Berkeley, which allows the simulation of two hardware dynamic scheduling techniques. There are two DLXsim-like interactive simulators developed as part of this project. DLXscore simulates the operation of a DLX architecture equipped with scoreboarding hardware. DLXscore provides the status of instructions, scoreboard tables, and statistics. DLXtomasulo simulates the operation of a DLX architecture equipped with a hardware implementation of Tomasulo's algorithm. DLXtomasulo provides the status of instructions, reservation stations, and statistics. Both programs allow the user to configure the number of functional units and the latency of floating point operations.} } @techreport{BUCS-TR-1995-014, author = {Mark Crovella and Robert Carter}, title = {{Dynamic Server Selection in the Internet}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-014}, month = {{June 30}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-014-dynamic-server-selection.ps.Z}, abstract = { As distributed information services like the World Wide Web become increasingly popular on the Internet, problems of scale are clearly evident. A promising technique that addresses many of these problems is service (or document) replication. However, when a service is replicated, clients then need the additional ability to find a ``good'' provider of that service. In this paper we report on techniques for finding good service providers without a priori knowledge of server location or network topology. We consider the use of two principal metrics for measuring distance in the Internet: hops, and round-trip latency. We show that these two metrics yield very different results in practice. Surprisingly, we show data indicating that the number of hops between two hosts in the Internet is {$\backslash$m not\/} strongly correlated to round-trip latency. Thus, the distance in hops between two hosts is not necessarily a good predictor of the expected latency of a document transfer. Instead of using known or measured distances in hops, we show that the extra cost at runtime incurred by dynamic latency measurement is well justified based on the resulting improved performance. In addition we show that selection based on dynamic latency measurement performs much better in practice that any static selection scheme. Finally, the difference between the distribution of hops and latencies is fundamental enough to suggest differences in algorithms for server replication. We show that conclusions drawn about service replication based on the distribution of hops need to be revised when the distribution of latencies is considered instead.} } @techreport{BUCS-TR-1995-015, author = {Mark Crovella and Azer Bestavros}, title = {{Explaining World Wide Web Traffic Self-Similarity}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-015}, month = {{August 29}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-015-explaining-web-self-similarity.ps.Z}, abstract = { Recently the notion of self-similarity has been shown to apply to wide-area and local-area network traffic. In this paper we examine the mechanisms that give rise to self-similar network traffic. We present an explanation for traffic self-similarity by using a particular subset of wide area traffic: traffic due to the World Wide Web (WWW). Using an extensive set of traces of actual user executions of NCSA Mosaic, reflecting over half a million requests for WWW documents, we show evidence that WWW traffic is self-similar. Then we show that the self-similarity in such traffic can be explained based on the underlying distributions of WWW document sizes, the effects of caching and user preference in file transfer, the effect of user ``think time'', and the superimposition of many such transfers in a local area network. To do this we rely on empirically measured distributions both from our traces and from data independently collected at over thirty WWW sites.} } @techreport{BUCS-TR-1995-016, author = {Stan Sclaroff}, title = {{World Wide Web Image Search Engines}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-016}, month = {{May 27}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-016-www-image-search-engines.ps.Z}, abstract = { (white paper presented at the NSF Workshop on Visual Information Management, MIT, June 1995) We propose the development of a world wide web image search engine that crawls the web collecting information about the images it finds, computes the appropriate image decompositions and indices, and stores this extracted information for searches based on image content. Indexing and searching images need not require solving the image understanding problem. Instead, the general approach should be to provide an arsenal of image decompositions and discriminants that can be precomputed for images. At search time, users can select a weighted subset of these decompositions to be used for computing image similarity measurements. While this approach avoids the search-time-dependent problem of labeling what is important in images, it still holds several important problems that require further research in the area of query by image content. We briefly explore some of these problems as they pertain to shape.} } @techreport{BUCS-TR-1995-017, author = {Stan Sclaroff}, title = {{Deformable Prototypes for Encoding Shape Categories in Image Databases}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-017}, month = {{Sept 12}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-017-deformable-prototypes.ps.Z}, abstract = { We describe a method for shape-based image database search that uses deformable prototypes to represent categories. Rather than directly comparing a candidate shape with all shape entries in the database, shapes are compared in terms of the types of nonrigid deformations (differences) that relate them to a small subset of representative prototypes. To solve the shape correspondence and alignment problem, we employ the technique of {$\backslash$m modal matching}, an information-preserving shape decomposition for matching, describing, and comparing shapes despite sensor variations and nonrigid deformations. In modal matching, shape is decomposed into an ordered basis of orthogonal principal components. We demonstrate the utility of this approach for shape comparison in 2-D image databases.} } @techreport{BUCS-TR-1995-018, author = {Peter Gacs}, title = {{Deterministic Computations Whose Hisrtory is Independent of the Order of Updating}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-018}, month = {{November 18}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-018-commut.ps.Z}, abstract = { Consider a network of processors (sites) in which each site has finitely many neighbors. Each site has some transition function computing its next state from the states of the neighbors. These transitions (updates) are applied in arbitrary order, one or many at a time. If the state of site x at time t is r(x,t) then let us define the sequence r'(x,0),r'(x,1),... by taking the sequence r(x,0),r(x,1),... and deleting each repetition, i.e. each element equal to the preceding one. The system of transition functions is said to support asynchrony if the sequence r'(x,i), (while it lasts, in case it is finite) depends only on the initial configuration, not on the order of updates. This paper gives a simple characterization of transition functions supporting asynchrony. The characterization says that it is equivalent to the following seemingly weaker commutativity condition: For any configuration, for any pair x,y of neighbors, if the updating would change both s(x) and s(y) then the result of updating first x and then y is be the same as the result of doing this in the reverse order.} } @techreport{BUCS-TR-1995-019, author = {J.B. Wells}, title = {{Title: The Undecidability of Mitchell's Subtyping Relationship}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1995-019}, month = {{December 10}}, year = {1995}, url = {http://www.cs.bu.edu/techreports/1995-019-subtyping-undecidable.ps.Z}, abstract = { Mitchell defined and axiomatized a subtyping relationship (also known as containment , coercibility , or subsumption over the types of System F (with "arrow" and "forall"). This subtyping relationship is quite simple and does not involve bounded quantification. Tiuryn and Urzyczyn quite recently proved this subtyping relationship to be undecidable. This paper supplies a new undecidability proof for this subtyping relationship. First, a new syntax-directed axiomatization of the subtyping relationship is defined. Then, this axiomatization is used to prove a reduction from the undecidable problem of semi-unification to subtyping. The undecidability of subtyping implies the undecidability of type checking for System F extended with Mitchell's subtyping, also known as F plus eta.} } @techreport{BUCS-TR-1996-001, author = {Azer Bestavros}, title = {{{AIDA}-based Real-Time Fault-Tolerant Broadcast Disks}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-001}, month = {{January 5}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-001-aida-broadcast-disks.ps.Z}, abstract = { The proliferation of mobile computers and wireless networks requires the design of future distributed real-time applications to recognize and deal with the significant asymmetry between downstream and upstream communication capacities, and the significant disparity between server and client storage capacities. Recent research work proposed the use of Broadcast Disks as a scalable mechanism to deal with this problem. In this paper, we propose a new broadcast disks protocol, based on our Adaptive Information Dispersal Algorithm (AIDA). Our protocol is different from previous broadcast disks protocols in that it improves communication timeliness, fault-tolerance, and security, while allowing for a finer control of multiplexing of prioritized data (broadcast frequencies). We start with a general introduction of broadcast disks. Next, we propose broadcast disk organizations that are suitable for real-time applications. Next, we present AIDA and show its fault-tolerance and security properties. We conclude the paper with the description and analysis of AIDA-based broadcast disks organizations that achieve both timeliness and fault-tolerance, while preserving downstream communication capacity.} } @techreport{BUCS-TR-1996-002, author = {Azer Bestavros and Sue Nagy}, title = {{An Admission Control Paradigm for Real-Time Databases}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-002}, month = {{January 15}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-002-rtdbs-admission-control.ps.Z}, abstract = { We propose and evaluate an admission control paradigm for RTDBS, in which a transaction is submitted to the system as a pair of processes: a primary task, and a recovery block. The execution requirements of the primary task are not known a priori, whereas those of the recovery block are known a priori. Upon the submission of a transaction, an Admission Control Mechanism is employed to decide whether to admit or reject that transaction. Once admitted, a transaction is guaranteed to finish executing before its deadline. A transaction is considered to have finished executing if exactly one of two things occur: Either its primary task is completed (successful commitment), or its recovery block is completed (safe termination). Committed transactions bring a profit to the system, whereas a terminated transaction brings no profit. The goal of the admission control, and scheduling protocols (e.g., concurrency control, I/O scheduling, memory management) employed in the system is to maximize system profit. We describe a number of admission control strategies and contrast (through simulations) their relative performance.} } @techreport{BUCS-TR-1996-003, author = {Azer Bestavros}, title = {{Advances in Real-Time Database Systems Research: Special Section on {RTDBS} of {ACM} {SIGMOD} Record 25(1), March 1996.}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-003}, month = {{January 15}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-003-rtdbs-sigmod-record}, abstract = { A Real-Time DataBase System (RTDBS) can be viewed as an amalgamation of a conventional DataBase Management System (DBMS) and a real-time system. Like a DBMS, it has to process transactions and guarantee ACID database properties. Furthermore, it has to operate in real-time, satisfying time constraints imposed on transaction commitments. A RTDBS may exist as a stand-alone system or as an embedded component in a larger multidatabase system. The publication in 1988 of a special issue of ACM SIGMOD Record on Real-Time DataBases signaled the birth of the RTDBS research area---an area that brings together researchers from both the database and real-time systems communities. Today, almost eight years later, I am pleased to present in this special section of ACM SIGMOD Record a review of recent advances in RTDBS research. There were 18 submissions to this special section, of which eight papers were selected for inclusion to provide the readers of ACM SIGMOD Record with an overview of current and future research directions within the RTDBS community. In this paper, I will summarize these directions and provide the reader with pointers to other publications for further information.} } @techreport{BUCS-TR-1996-004, author = {Virgilio Almeida and Adriana Oliveira}, title = {{On the Fractal Nature of {WWW} and Its Application to Cache Modeling}}, institution = {Computer Science Department, Boston University (Depto. de Ciencia da Computacao da UFMG, Brazil)}, number = {BUCS-TR-1996-004}, month = {{February 5}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-004-www-caching-fractals.ps.Z}, abstract = { The World Wide Web (WWW or Web) is growing rapidly on the Internet. Web users want fast response time and easy access to a enormous variety of information across the world. Thus, performance is becoming a main issue in the Web. Fractals have been used to study fluctuating phenomena in many different disciplines, from the distribution of galaxies in astronomy to complex physiological control systems. The Web is also a complex, irregular, and random system. In this paper, we look at the document reference pattern at Internet Web servers and use fractal-based models to understand aspects (e.g. caching schemes) that affect the Web performance.} } @techreport{BUCS-TR-1996-005, author = {Abdelsalam Heddaya and Himanshu Sinha}, title = {{Distributed Parallel Computing in Mermera: Mixing Noncoherent Shared Memories}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-005}, month = {{March 7}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-005-mermera-model-system.ps.Z}, abstract = { Programmers of parallel processes that communicate through shared globally distributed data structures (DDS) face a difficult choice. Either they must explicitly program DDS management, by partitioning or replicating it over multiple distributed memory modules, or be content with a high latency coherent (sequentially consistent) memory abstraction that hides the DDS' distribution. We present Mermera, a formalism and system that enables a smooth spectrum of noncoherent shared memory behaviors to coexist between the above two extremes. Our approach allows us to define known noncoherent memories in a new simple way, to identify new memory behaviors, and to characterize generic mixed-behavior computations. The latter are useful for programming using multiple behaviors that complement each others' advantages, and for programming by step-wise refinement. On the practical side, we show that the large class of programs that use asynchronous iterative methods (AIM) can run correctly on slow memory, one of the weakest, and hence most efficient and fault-tolerant, noncoherence conditions. An example AIM program to solve linear equations, is developed to illustrate the need for concurrently mixing memory behaviors, and the performance gains attainable via noncoherence. Other program classes tolerate weak memory consistency by synchronizing in such a way as to yield executions indistinguishable from coherent ones. AIM computations on noncoherent memory yield noncoherent, yet correct, computations. We present performance data that illustrate the benefits of noncoherence, in terms of raw memory performance, as well as application speed.} } @techreport{BUCS-TR-1996-006, author = {Robert Carter and Mark Crovella}, title = {{Measuring Bottleneck Link Speed in Packet-Switched Networks}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-006}, month = {{March 15}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-006-measuring-bottleneck-link.ps.Z}, abstract = { The quality of available network connections can often have a large impact on the performance of distributed applications. For example, document transfer applications such as FTP, Gopher and the World Wide Web suffer increased response times as a result of network congestion. For these applications, the document transfer time is directly related to the available bandwidth of the connection. Available bandwidth depends on two things: 1) the underlying capacity of the path from client to server, which is limited by the bottleneck link; and 2) the amount of other traffic competing for links on the path. If measurements of these quantities were available to the application, the current utilization of connections could be calculated. Network utilization could then be used as a basis for selection from a set of alternative connections or servers, thus providing reduced response time. Such a dynamic server selection scheme would be especially important in a mobile computing environment in which the set of available servers is frequently changing. In order to provide these measurements at the application level, we introduce two tools: bprobe, which provides an estimate of the uncongested bandwidth of a path; and cprobe, which gives an estimate of the current congestion along a path. These two measures may be used in combination to provide the application with an estimate of available bandwidth between server and client thereby enabling application-level congestion avoidance. In this paper we discuss the design and implementation of our probe tools, specifically illustrating the techniques used to achieve accuracy and robustness. We present validation studies for both tools which demonstrate their reliability in the face of actual Internet conditions; and we give results of a survey of available bandwidth to a random set of WWW servers as a sample application of our probe technique. We conclude with descriptions of other applications of our measurement tools, several of which are currently under development.} } @techreport{BUCS-TR-1996-007, author = {Robert Carter and Mark Crovella}, title = {{Dynamic Server Selection using Bandwidth Probing in Wide-Area Networks}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-007}, month = {{March 18}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-007-dss-using-bandwidth.ps.Z}, abstract = { Replication is a commonly proposed solution to problems of scale associated with distributed services. However, when a service is replicated, each client must be assigned a server. Prior work has generally assumed that assignment to be static. In contrast, we propose dynamic server selection, and show that it enables application-level congestion avoidance. To make dynamic server selection practical, we demonstrate the use of three tools. In addition to direct measurements of round-trip latency, we introduce and validate two new tools: bprobe, which estimates the maximum possible bandwidth along a given path; and cprobe, which estimates the current congestion along a path. Using these tools we demonstrate dynamic server selection and compare it to previous static approaches. We show that dynamic server selection consistently outperforms static policies by as much as 50%. Furthermore, we demonstrate the importance of each of our tools in performing dynamic server selection.} } @techreport{BUCS-TR-1996-008, author = {Azer Bestavros and Marina Chen and Mark Crovella and Abdelsalam Heddaya and Stan Sclaroff and James Cowie}, title = {{Responsive Web Computing: Resource Management, Protocol Techniques, and Applications ({A} research statement)}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-008}, month = {{March 21}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-008-rwc.ps.Z}, abstract = { The exploding demand for services like the World Wide Web reflects the potential that is presented by globally distributed information systems. The number of WWW servers world-wide has doubled every 3 to 5 months since 1993, outstripping even the growth of the Internet. At each of these self-managed sites, the Common Gateway Interface (CGI) and Hypertext Transfer Protocol (HTTP) already constitute a rudimentary basis for contributing local resources to remote collaborations. However, the Web has serious deficiencies that make it unsuited for use as a true medium for metacomputing --- the process of bringing hardware, software, and expertise from many geographically dispersed sources to bear on large scale problems. These deficiencies are, paradoxically, the direct result of the very simple design principles that enabled its exponential growth. There are many symptoms of the problems exhibited by the Web: disk and network resources are consumed extravagantly; information search and discovery are difficult; protocols are aimed at data movement rather than task migration, and ignore the potential for distributing computation. However, all of these can be seen as aspects of a single problem: as a distributed system for metacomputing, the Web offers unpredictable performance and unreliable results. The goal of our project is to use the Web as a medium (within either the global Internet or an enterprise intranet) for metacomputing in a reliable way with performance guarantees. We attack this problem one four levels: (1) Resource Management Services: Globally distributed computing allows novel approaches to the old problems of performance guarantees and reliability. Our first set of ideas involve setting up a family of real-time resource management models organized by the Web Computing Framework with a standard Resource Management Interface (RMI), a Resource Registry, a Task Registry, and resource management protocols to allow resource needs and availability information be collected and disseminated so that a family of algorithms with varying computational precision and accuracy of representations can be chosen to meet realtime and reliability constraints. (2) Middleware Services: Complementary to techniques for allocating and scheduling available resources to serve application needs under realtime and reliability constraints, the second set of ideas aim at reduce communication latency, traffic conjestion, server work load, etc. We develop customizable middleware services to exploit application characteristics in traffic analysis to drive new server/browser design strategies (e.g., exploit self-similarity of Web traffic), derive document access patterns via multiserver cooperation, and use them in speculative prefetching, document caching, and aggressive replication to reduce server load and bandwidth requirements. (3) Communication Infrastructure: Finally, to achieve any guarantee of quality of service or performance, one must get at the network layer that can provide the basic guarantees of bandwidth, latency, and reliability. Therefore, the third area is a set of new techniques in network service and protocol designs. (4) Object-Oriented Web Computing Framework A useful resource management system must deal with job priority, fault-tolerance, quality of service, complex resources such as ATM channels, probabilistic models, etc., and models must be tailored to represent the best tradeoff for a particular setting. This requires a family of models, organized within an object-oriented framework, because no one-size-fits-all approach is appropriate. This presents a software engineering challenge requiring integration of solutions at all levels: algorithms, models, protocols, and profiling and monitoring tools. The framework captures the abstract class interfaces of the collection of cooperating components, but allows the concretization of each component to be driven by the requirements of a specific approach and environment.} } @techreport{BUCS-TR-1996-009, author = {David Hicks and Anja Haake and David Durand and Fabio Vitali}, title = {{Proceedings of the {ECSCW}'95: Workshop on the Role of Version Control in {CSCW} Applications}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-009}, month = {{April 26}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-009-ecscw95-proceedings}, abstract = { The workshop entitled "The Role of Version Control in Computer Supported Cooperative Work Applications" was held on September 10, 1995 in Stockholm, Sweden in conjunction with the ECSCW'95 conference. Version control, the ability to manage relationships between successive instances of artifacts, organize those instances into meaningful structures, and support navigation and other operations on those structures, is an important problem in CSCW applications. It has long been recognized as a critical issue for inherently cooperative tasks such as software engineering, technical documentation, and authoring. The primary challenge for versioning in these areas is to support opportunistic, open-ended design processes requiring the preservation of historical perspectives in the design process, the reuse of previous designs, and the exploitation of alternative designs. This report contains a summary in which the workshop organizers report the major results of the workshop. The summary is followed by a section that contains the position papers that were accepted to the workshop. The position papers provide more detailed information describing recent research efforts of the workshop participants as well as current challenges that are being encountered in the development of CSCW applications. A list of workshop participants is provided at the end of the report.} } @techreport{BUCS-TR-1996-010, author = {Euthimios Panagos}, title = {{Client-Based Logging: {A} New Paradigm For Distributed Transaction Management}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-010}, month = {{June 13}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-010-client-based-logging.ps.Z}, abstract = { The proliferation of inexpensive workstations and networks has created a new era in distributed computing. At the same time, non-traditional applications such as computer-aided design (CAD), computer-aided software engineering (CASE), geographic- information systems (GIS), and office-information systems (OIS) have placed increased demands for high-performance transaction processing on database systems. The combination of these factors gives rise to significant challenges in the design of modern database systems. In this thesis, we propose novel techniques whose aim is to improve the performance and scalability of these new database systems. These techniques exploit client resources through client-based transaction management. Client-based transaction management is realized by providing logging facilities locally even when data is shared in a global environment. This thesis presents several recovery algorithms which utilize client disks for storing recovery related information (i.e., log records). Our algorithms work with both coarse and fine-granularity locking and they do not require the merging of client logs at any time. Moreover, our algorithms support fine-granularity locking with multiple clients permitted to concurrently update different portions of the same database page. The database state is recovered correctly when there is a complex crash as well as when the updates performed by different clients on a page are not present on the disk version of the page, even though some of the updating transactions have committed. This thesis also presents the implementation of the proposed algorithms in a memory-mapped storage manager as well as a detailed performance study of these algorithms using the OO1 database benchmark. The performance results show that client- based logging is superior to traditional server-based logging. This is because client-based logging is an effective way to reduce dependencies on server CPU and disk resources and, thus, prevents the server from becoming a performance bottleneck as quickly when the number of clients accessing the database increases.} } @techreport{BUCS-TR-1996-011, author = {Virgilio Almeida and Azer Bestavros and Mark Crovella and Adriana deOliveira}, title = {{Characterizing Reference Locality in the {WWW}}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-011}, month = {{June 21}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-011-www-reference-locality.ps.Z}, abstract = { As the World Wide Web (Web) is increasingly adopted as the infrastructure for large-scale distributed information systems, issues of performance modeling become ever more critical. In particular, locality of reference is an important property in the performance modeling of distributed information systems. In the case of the Web, understanding the nature of reference locality will help improve the design of middleware, such as caching, prefetching, and document dissemination systems. For example, good measurements of reference locality would allow us to generate synthetic reference streams with accurate performance characteristics, would allow us to compare empirically measured streams to explain differences, and would allow us to predict expected performance for system design and capacity planning. In this paper we propose models for both temporal and spatial locality of reference in streams of requests arriving at Web servers. We show that simple models based only on document popularity (likelihood of reference) are insufficient for capturing either temporal or spatial locality. Instead, we rely on an equivalent, but numerical, representation of a reference stream: a stack distance trace. We show that temporal locality can be characterized by the marginal distribution of the stack distance trace, and we propose models for typical distributions and compare their cache performance to our traces. We also show that spatial locality in a reference stream can be characterized using the notion of self-similarity. Self-similarity describes long-range correlations in the dataset, which is a property that previous researchers have found hard to incorporate into synthetic reference strings. We show that stack distance strings appear to be stongly self-similar, and we provide measurements of the degree of self-similarity in our traces. Finally, we discuss methods for generating synthetic Web traces that exhibit the properties of temporal and spatial locality that we measured in our data. Keywords: Self-similarity; Long-range dependence; Distance strings; Reference locality; Caching; Performance modeling.} } @techreport{BUCS-TR-1996-012, author = {Amr Fahmy and Abdelsalam Heddaya}, title = {{Management of Communicable Memory and Lazy Barriers for Bulk Synchronous Parallelism in BSPk}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-012}, month = {{July 2}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-012-bspk-design.ps.Z}, abstract = { Communication and synchronization stand as the dual bottlenecks in the performance of parallel systems, and especially those that attempt to alleviate the programming burden by incurring overhead in these two domains. We formulate the notions of communicable memory and lazy barriers to help achieve efficient communication and synchronization. These concepts are developed in the context of BSPk, a toolkit library for programming networks of workstations---and other distributed memory architectures in general---based on the Bulk Synchronous Parallel (BSP) model. BSPk, whose design is the subject of this paper, emphasizes efficiency in communication by minimizing local memory-to-memory copying, and in barrier synchronization by not forcing a process to wait unless it needs remote data. Both the message passing (MP) and distributed shared memory (DSM) programming styles are supported in BSPk, for the former helps processes exchange short-lived unnamed data values, while the latter permits communication through long-lived named variables.} } @techreport{BUCS-TR-1996-013, author = {Azer Bestavros and Kwei-Jay Lin and Sang Son}, title = {{Real-Time Databases: Issues and Applications ({RTDB}'96 Workshop Report)}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-013}, month = {{July 3}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-013-rtdb96-report.ps.Z}, abstract = { This report summarizes the technical presentations and discussions that took place during RTDB'96: the First International Workshop on Real-Time Databases, which was held on March 7 and 8, 1996 in Newport Beach, California. The main goals of this project were to (1) review recent advances in real-time database systems research, (2) to promote interaction among real-time database researchers and practitioners, and (3) to evaluate the maturity and directions of real-time database technology.} } @techreport{BUCS-TR-1996-014, author = {Azer Bestavros and Gitae Kim}, title = {{{TCP} Boston: {A} Fragmentation-tolerant {TCP} Protocol for {ATM} Networks}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-014}, month = {{July 15}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-014-tcp-boston.ps.Z}, abstract = { The popularity of TCP/IP coupled with the premise of high speed communication using Asynchronous Transfer Mode (ATM) technology have prompted the network research community to propose a number of techniques to adapt TCP/IP to ATM network environments. ATM offers Available Bit Rate (ABR) and Unspecified Bit Rate (UBR) services for best-effort traffic, such as conventional file transfer. However, recent studies have shown that TCP/IP, when implemented using ABR or UBR, leads to serious performance degradations, especially when the utilization of network resources (such as switch buffers) is high. Proposed techniques---switch-level enhancements, for example---that attempt to patch up TCP/IP over ATMs have had limited success in alleviating this problem. The major reason for TCP/IP's poor performance over ATMs has been consistently attributed to packet fragmentation, which is the result of ATM's 53-byte cell-oriented switching architecture. In this paper, we present a new transport protocol, TCP Boston, that turns ATM's 53-byte cell-oriented switching architecture into an advantage for TCP/IP. At the core of TCP Boston is the Adaptive Information Dispersal Algorithm (AIDA), an efficient encoding technique that allows for dynamic redundancy control. AIDA makes TCP/IP's performance less sensitive to cell losses, thus ensuring a graceful degradation of TCP/IP's performance when faced with congested resources. In this paper, we introduce AIDA and overview the main features of TCP Boston. We present detailed simulation results that show the superiority of our protocol when compared to other adaptations of TCP/IP over ATMs. In particular, we show that TCP Boston improves TCP/IP's performance over ATMs for both network-centric metrics (e.g., effective throughput) and application-centric metrics (e.g., response time).} } @techreport{BUCS-TR-1996-015, author = {Kihong Park}, title = {{Ergodicity and mixing rate of one-dimensional cellular automata}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-015}, month = {{July 22}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-015-park-phdthesis.ps.Z}, abstract = { One-and two-dimensional cellular automata which are known to be fault-tolerant are very complex. On the other hand, only very simple cellular automata have actually been proven to lack fault-tolerance, i.e., to be mixing. The latter either have large noise probability $$\backslash$ps$ or belong to the small family of two-state nearest-neighbor monotonic rules which includes local majority voting. For a certain simple automaton $L$ called the soldiers rule, this problem has intrigued researchers for the last two decades since $L$ is clearly more robust than local voting: in the absence of noise, $L$ eliminates any finite island of perturbation from an initial configuration of all 0's or all 1's. The same holds for a 4-state monotonic variant of $L$, $K$, called two-line voting. We will prove that the probabilistic cellular automata $K\_$\backslash$ps$ and $L\_$\backslash$ps$ asymptotically lose all information about their initial state when subject to small, strongly biased noise. The mixing property trivially implies that the systems are ergodic. The finite-time information-retaining quality of a mixing system can be represented by its relaxation time $\Relax(\cdot)$, which measures the time before the onset of significant information loss. This is known to grow as $(1/$\backslash$ps)^c$ for noisy local voting. The impressive error-correction ability of $L$ has prompted some researchers to conjecture that $\Relax(L\_$\backslash$ps)=2^{c/$\backslash$ps}$. We prove the tight bound $2^{c\_1\log^2 1/$\backslash$ps} < \Relax(L\_$\backslash$ps) < 2^{c\_2\log^2 1/$\backslash$ps}$ for a biased error model. The same holds for $K\_$\backslash$ps$. Moreover, the lower bound is independent of the bias assumption. The strong bias assumption makes it possible to apply sparsity/renormalization techniques, the main tools of our investigation, used earlier in the opposite context of proving fault-tolerance.} } @techreport{BUCS-TR-1996-016, author = {Kihong Park and Gitae Kim and Mark Crovella}, title = {{On the relationship between file sizes, transport protocols, and self-similar network traffic}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-016}, month = {{July 30}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-016-self-similar-cause.ps.Z}, abstract = { Recent measurements of local-area and wide-area traffic have shown that network traffic exhibits variability at a wide range of scales---self-similarity. In this paper, we examine a mechanism that gives rise to self-similar network traffic and present some of its performance implications. The mechanism we study is the transfer of files or messages whose size is drawn from a heavy-tailed distribution. We examine its effects through detailed transport-level simulations of multiple TCP streams in an internetwork. First, we show that in a ``realistic'' client/server network environment---i.e., one with bounded resources and coupling among traffic sources competing for resources---the degree to which file sizes are heavy-tailed can directly determine the degree of traffic self-similarity at the link level. We show that this causal relationship is not significantly affected by changes in network resources (bottleneck bandwidth and buffer capacity), network topology, the influence of cross-traffic, or the distribution of interarrival times. Second, we show that properties of the transport layer play an important role in preserving and modulating this relationship. In particular, the reliable transmission and flow control mechanisms of TCP (Reno, Tahoe, or Vegas) serve to maintain the long-range dependency structure induced by heavy-tailed file size distributions. In contrast, if a non-flow-controlled and unreliable (UDP-based) transport protocol is used, the resulting traffic shows little self-similar characteristics: although still bursty at short time scales, it has little long-range dependence. If flow-controlled, unreliable transport is employed, the degree of traffic self-similarity is positively correlated with the degree of throttling at the source. Third, in exploring the relationship between file sizes, transport protocols, and self-similarity, we are also able to show some of the performance implications of self-similarity. We present data on the relationship between traffic self-similarity and network performance as captured by performance measures including packet loss rate, retransmission rate, and queueing delay. Increased self-similarity, as expected, results in degradation of performance. Queueing delay, in particular, exhibits a drastic increase with increasing self-similarity. Throughput-related measures such as packet loss and retransmission rate, however, increase only gradually with increasing traffic self-similarity as long as reliable, flow-controlled transport protocol is used.} } @techreport{BUCS-TR-1996-017, author = {Azer Bestavros}, title = {{Load Profiling in Distributed Real-Time Systems}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-017}, month = {{August 1}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-017-load-profiling.ps.Z}, abstract = { Load balancing is often used to ensure that nodes in a distributed systems are equally loaded. In this paper, we show that for real-time systems, load balancing is not desirable. In particular, we propose a new load-profiling strategy that allows the nodes of a distributed system to be unequally loaded. Using load profiling, the system attempts to distribute the load amongst its nodes so as to maximize the chances of finding a node that would satisfy the computational needs of incoming real-time tasks. To that end, we describe and evaluate a distributed load-profiling protocol for dynamically scheduling time-constrained tasks in a loosely-coupled distributed environment. When a task is submitted to a node, the scheduling software tries to schedule the task locally so as to meet its deadline. If that is not feasible, it tries to locate another node where this could be done with a high probability of success, while attempting to maintain an overall load profile for the system. Nodes in the system inform each other about their state using a combination of multicasting and gossiping. The performance of the proposed protocol is evaluated via simulation, and is contrasted to other dynamic scheduling protocols for real-time distributed systems. Based on our findings, we argue that keeping a diverse availability profile and using passive bidding (through gossiping) are both advantageous to distributed scheduling for real-time systems.} } @techreport{BUCS-TR-1996-018, author = {Virgilio Almeida and Jussara Almeida and Cristina Murta}, title = {{Performance Analysis of a {WWW} Server}}, institution = {Computer Science Department, Boston University and UFMG}, number = {BUCS-TR-1996-018}, month = {{August 5}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-018-www-performance-analysis.ps.Z}, abstract = { The WWW has experienced a phenomenal growth and has become the most popular Internet application. As a consequence of its large popularity, the Internet has suffered from various performance problems, such as network congestion and overloaded servers. These days, it is not uncommon to find servers refusing connections because they are overloaded. Performance has always been a key issue in the design and operation of on-line systems. With regard to Internet, performance is also critical, because users want fast and easy access to all objects (e.g., documents, graphics, audio, and video) available on the net. Thus, it is important to understand WWW performance issues. This paper focuses on the performance analysis of Web servers. Using a synthetic benchmark (WebStone) and standard operating systems monitoring tools, it analyzes three different Web server software running on top of a Windows NT platform and performing some typical WWW tasks. It also discusses the main steps needed to carry out a WWW performance analysis effort and shows relations between the workload characteristics and system resource usage.} } @techreport{BUCS-TR-1996-019, author = {A.J. Kfoury}, title = {{Beta-Reduction as Unification}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-019}, month = {{July 8}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-019-beta-unification.ps.Z}, abstract = { We define a unification problem ^UP with the property that, given a pure lambda-term M, we can derive an instance Gamma(M) of ^UP from M such that Gamma(M) has a solution if and only if M is beta-strongly normalizable. There is a type discipline for pure lambda-terms that characterizes beta-strong normalization; this is the system of intersection types (without a ``top'' type that can be assigned to every lambda-term). In this report, we use a lean version LAMBDA of the usual system of intersection types. Hence, ^UP is also an appropriate unification problem to characterize typability of lambda-terms in LAMBDA. It also follows that ^UP is an undecidable problem, which can in turn be related to semi-unification and second-order unification (both known to be undecidable).} } @techreport{BUCS-TR-1996-020, author = {A.J. Kfoury and A.P. Stolboushkin}, title = {{An Infinite Pebble Game and Applications}}, institution = {Computer Science Department, Boston University and Mathematics Department, UCLA}, number = {BUCS-TR-1996-020}, month = {{August 15}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-020-infinite-pebble-game.ps.Z}, abstract = { We generalize the well-known pebble game to infinite dag's, and we use this generalization to give new and shorter proofs of results in different areas of computer science (as diverse as ``logic of programs'' and ``formal language theory''). Our applications here include a proof of a theorem due to Salomaa, asserting the existence of a context-free language with infinite index, and a proof of a theorem due to Tiuryn and Erimbetov, asserting that unbounded memory increases the power of logics of programs. The original proofs by Salomaa, Tiuryn, and Erimbetov, are fairly technical. The proofs by Tiuryn and Erimbetov also involve advanced techniques of model theory, namely, back-and-forth constructions based on a variant of Ehrenfeucht-Fraisse games. By contrast, our proofs are not only shorter, but also elementary. All we need is essentially finite induction and, in the case of the Tiuryn-Erimbetov result, the compactness and completeness of first-order logic.} } @techreport{BUCS-TR-1996-021, author = {A.J. Kfoury}, title = {{A Linearization of the Lambda Calculus and Consequences}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-021}, month = {{August 19}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-021-linearization-lambda-calculus.ps.Z}, abstract = { If every lambda-abstraction in a lambda-term M binds at most one variable occurrence, then M is said to be "linear". Many questions about linear lambda-terms are relatively easy to answer, e.g. they all are beta-strongly normalizing and all are simply-typable. We extend the syntax of the standard lambda-calculus L to a non-standard lambda-calculus L^ satisfying a linearity condition generalizing the notion in the standard case. Specifically, in L^ a subterm Q of a term M can be applied to several subterms R1,...,Rk in parallel, which we write as (Q. R1 \wedge ... \wedge Rk). The appropriate notion of beta- reduction beta^ for the calculus L^ is such that, if Q is the lambda- abstraction (\lambda x.P) with m\geq 0 bound occurrences of x, the reduction can be carried out provided k = max(m,1). Every M in L^ is thus beta^-SN. We relate standard beta-reduction and non-standard beta^-reduction in several different ways, and draw several consequences, e.g. a new simple proof for the fact that a standard term M is beta-SN iff M can be assigned a so-called ``intersection'' type (``top'' type disallowed).} } @techreport{BUCS-TR-1996-022, author = {J.B. Wells}, title = {{Typability is Undecidable for {F}+Eta}}, institution = {Computer Science Department, Boston University}, number = {BUCS-TR-1996-022}, month = {{March 9}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-022-f+eta-typability-undecidable.ps.Z}, abstract = { System F is the well-known polymorphically-typed lambda calculus with universal quantifiers. F+eta is System F extended with the eta rule, which says that if term M can be given type tau and M eta-reduces to N , then N can also be given the type tau. Adding the eta rule to System F is equivalent to adding the subsumption rule using the subtyping (containment) relation that Mitchell defined and axiomatized [Mit88]. The subsumption rule says that if M can be given type tau and tau is a subtype of type sigma, then M can be given type sigma. Mitchell's subtyping relation involves no extensions to the syntax of types, i.e., no bounded polymorphism and no supertype of all types, and is thus unrelated to the system "F-sub". Typability for F+eta is the problem of determining for any term M whether there is any type tau that can be given to it using the type inference rules of F+eta. Typability has been proven undecidable for System F [Wel94] (without the eta rule), but the decidability of typability has been an open problem for F+eta. Mitchell's subtyping relation has recently been proven undecidable [TU95,Wel95b], implying the undecidability of "type checking" for F+eta. This paper reduces the problem of subtyping to the problem of typability for F+eta, thus proving the undecidability of typability. The proof methods are similar in outline to those used to prove the undecidability of typability for System F, but the fine details differ greatly.} } @techreport{BUCS-TR-1996-023, author = {Sanjoy Baruah and Azer Bestavros}, title = {{Pinwheel Scheduling for Fault-tolerant Broadcast Disks in Real-time Database Systems}}, institution = {EE/CS Department, University of Vermont; CS Department, Boston University}, number = {BUCS-TR-1996-023}, month = {{August 22}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-023-pinwheel-bdisks.ps.Z}, abstract = { The design of programs for broadcast disks which incorporate real-time and fault-tolerance requirements is considered. A generalized model for real-time fault-tolerant broadcast disks is defined. It is shown that designing programs for broadcast disks specified in this model is closely related to the scheduling of pinwheel task systems. Some new results in pinwheel scheduling theory are derived, which facilitate the efficient generation of real-time fault-tolerant broadcast disk programs.} } @techreport{BUCS-TR-1996-024, author = {Abdelsalam Heddaya and Sulaiman Mirdad}, title = {{WebWave: Globally Load Balanced Fully Distributed Caching of Hot Published Documents}}, institution = {CS Department, Boston University}, number = {BUCS-TR-1996-024}, month = {{October 10}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-024-webwave-theory.ps.Z}, abstract = { Document publication service over such a large network as the Internet challenges us to harness available server and network resources to meet fast growing demand. In this paper, we show that large-scale dynamic caching can be employed to globally minimize server idle time, and hence maximize the aggregate throughput of the whole service. Given the distributed nature of the system, a successful caching mechanism must satisfy three properties: (1) that it maximize the global throughput of the system, (2) that it be completely distributed in the sense of operating only on the basis of local information, and (3) that it require no naming service that introduces a scalability bottleneck. In this paper, we develop a precise definition, which we call "tree load-balance", of what it means for a mechanism to satisfy these three goals, and present two algorithms that achieve them. Both algorithms compute the request rate that should be allocated to each cache server, so that global throughput is maximized. The first algorithm, WebFold, is a centralized one that is provably optimal with respect to throughput. The second algorithm, WebWave, whose optimality is evidenced by simulation, is a fully distributed diffusion-based protocol. Both algorithms assume that cache copies are placed on the routing tree that connects the cached document's home server with its clients. As a consequence, document requests can find cache copies without resorting to a cache directory of any kind. The results herein apply only to immutable documents; we do not consider the cache consistency problem.} } @techreport{BUCS-TR-1996-025, author = {Jussara Almeida and Virgilio Almeida and David Yates}, title = {{Measuring the Behavior of a World-Wide Web Server}}, institution = {CS Department, Boston University}, number = {BUCS-TR-1996-025}, month = {{October 29}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-025-web-server-measurements.ps.Z}, abstract = { Server performance has become a crucial issue for improving the overall performance of the World-Wide Web. This paper describes Webmonitor, a tool for evaluating and understanding server performance, and presents new results for a realistic workload. Webmonitor measures activity and resource consumption, both within the kernel and in HTTP processes running in user space. Webmonitor is implemented using an efficient combination of sampling and event-driven techniques that exhibit low overhead. Our initial implementation is for the Apache World-Wide Web server running on the Linux operating system. We demonstrate the utility of Webmonitor by measuring and understanding the performance of a Pentium-based PC acting as a dedicated WWW server. Our workload uses a file size distribution with a heavy tail. This captures the fact that Web servers must concurrently handle some requests for large audio and video files, and a large number of requests for small documents, containing text or images. Our results show that in a Web server saturated by client requests, over 90% of the time spent handling HTTP requests is spent in the kernel. Furthermore, keeping TCP connections open, as required by TCP, causes a factor of 2-9 increase in the elapsed time required to service an HTTP request. Data gathered from Webmonitor provide insight into the causes of this performance penalty. Specifically, we observe a significant increase in resource consumption along three dimensions: the number of HTTP processes running at the same time, CPU utilization, and memory utilization. These results emphasize the important role of operating system and network protocol implementation in determining Web server performance.} } @techreport{BUCS-TR-1996-026, author = {David M. Martin and Sivaramakrishnan Rajagopalan and Aviel D. Rubin}, title = {{Blocking Java Applets at the Firewall}}, institution = {CS Department, Boston University}, number = {BUCS-TR-1996-026}, month = {{November 14}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-026-java-firewalls.ps.Z}, abstract = { This paper explores the problem of protecting a site on the Internet against hostile external Java applets while allowing trusted internal applets to run. With careful implementation, a site can be made resistant to current Java security weaknesses as well as those yet to be discovered. In addition, we describe a new attack on certain sophisticated firewalls that is most effectively realized as a Java applet.} } @techreport{BUCS-TR-1996-027, author = {Azer Bestavros}, title = {{Proceedings of the 17th Real-Time Systems Symposium {WIP} Session}}, institution = {CS Department, Boston University}, number = {BUCS-TR-1996-027}, month = {{December 4}}, year = {1996}, url = {http://www.cs.bu.edu/techreports/1996-027-ieee-rtss96-wip}, abstract = { This technical report includes 14 short papers presented during the WIP session of the 17th Real-Time Systems Symposium, held in Washington DC on December 4-6, 1996. The title and authors are included below. ------ (1) A Specialized Specification and Verification System for Timed Automata Myla Archer and Constance Heitmeyer Naval Research Laboratory, USA Abstract: Assuring the correctness of specifications of real-time systems can involve significant human effort. The use of a mechanical theorem prover to encode such specifications and to verify their properties could significantly reduce this effort. A barrier to routinely encoding and mechanically verifying specifications has been the need first to master the specification language and logic of a general theorem proving system. Our approach to overcoming this barrier is to provide mechanical support for producing specifications and verifying proofs, specialized for particular mathematical models and proof techniques. We are currently developing a mechanical verification system called TAME (Timed Automata Modeling Environment), which provides this specialized support using SRI's Prototype Verification System (PVS). Our system is intended to permit steps in reasoning similar to those in hand proofs that use model-specific techniques. TAME has recently been used to detect errors in a realistic example. ------ (2) Scheduling Slack in MetaH Pam Binns Honeywell Technology Center, USA Abstract: A real-time implementation for allocating slack to aperiodic proceesses in MetaH is nearing completion. The slack scheduling algorithm is based on the slack stealer originally proposed in "An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems" with practical extensions to allow for support of process criticalities, multiple process streams (of different criticalities) competing for pooled slack and inclusion of run-time overheads in the slack functions. Areas in need of future work are also identified. ------ (3) AFTER: A case tool to assist in Fine-tuning of embedded real-time systems Gaurav Arora and David Stewart University of Maryland, USA Abstract: AFTER (Assist in Fine-Tuning of Embedded Real-time systems) is an interactive analysis and predictor tool for embedded systems. It helps designers quickly identify timing problems and systematically fine-tune an application during and after the implementation phase of a product's lifecycle. The tool begins with raw timing data collected from an embedded system. It analyzes the data to provide a temporal image of the current implementation, highlighting actual and potential problems. The user then interacts with AFTER to obtain predictions on what overall effect can be expected if small adjustments are made to configuration parameters or to the timing properties of specific software components. The tool integrates and extends prior research in scheduling, task monitoring, and operating system design for real-time systems. ------ (4) Genericity and Upgradability in Ultra-Dependable Real-Time Architectures Andy Wellings, Ljerka Beus-Dukis, Alan Burns, and David Powell LAAS-CNRS, France and University of York, UK Abstract: We report on the ideas currently being developed within the European GUARDS project to develop a generic upgradable architecture for real-time dependable systems. After a brief introduction and overview of the architecture, we outline the GUARDS approach for scheduling real-time replicated computation. ------ (5) Challenges in Engineering Distributed Shipboard Control System L.Welch, B.Ravindran, R.Harrison, L.Madden, M.W.Masters and W.Mills Naval Surface Warfare Center and University of Texas at Arlington, USA Abstract: In response to the need to develop high capacity, scalable computer systems for shipboard use, a program called the High Performance Distributed Computing Program (HiPer-D), was created. HiPer-D is intended to provide the technical design concepts and engineering data needed to enable the Navy to capitalize on commercial computing products. The program, conducted jointly by the Defense Advanced Research Projects Agency (DARPA) and the Aegis Shipbuilding Program, consists of simultaneous top down engineering studies and large-scale critical experiments using new computer technology. ------ (6) Issues for realizing a scalable Real Time Kernel for function-distributed Multiprocessors Hiroaki Takada, Cai-Dong Wang, and ken Sakamura University of Tokyo, Japan Abstract: In multiprocessor systems, the worst-case execution time of a task that exclusively accesses a shared resource is unavoidably prolonged as the number of contending processors is increased. In case of function-distributed multiprocessors, because many of the tasks can be processed within a processor, it is advantageous that their worst-case behavior are independent of the number of processors in the system. This paper summarizes the required properties on scalable real-time kernels and discusses their realization techniques. What we have solved so far are described, and the remaining problem to be solved is presented. ------ (7) The design and implementation of the CPU power regulator for multimedia operating systems Giun-Haur Huang, Shie-Kai Ni, and Tei-Wei Kuo National Chung Cheng University, Taiwan Abstract: This paper describes a Windows NT/95 utility, the CPU Power Regulator (CPR), which improves the capability of Windows NT/95 in servicing time-critical applications. CPR considers a distance model [4] to service time-critical applications such as multimedia softwares and electronic games in a timely fashion. Distinct from the past work [7, 8, 9], CPR adopts a user-level control mechanism to manage the resource