Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 16 of 16
Full-Text Articles in Physical Sciences and Mathematics
The Impact Of Multicast Layering On Network Fairness, Jim Kurose
The Impact Of Multicast Layering On Network Fairness, Jim Kurose
Computer Science Department Faculty Publication Series
Many definitions of fairness for multicast networks assume that sessions are single-rate, requiring that each multicast session trans- mits data to all of its receivers at the same rate. These defini- tions do not account for multi-rate approaches, such as layering, that permit receiving rates within a session to be chosen indepen- dently. We identify four desirable fairness properties for multicast networks, derived from properties that hold within the max-min fair allocations of unicast networks. We extend the definition of multicast max-min fairness to networks that contain multi-rate sessions, and show that all four fairness properties hold in a multi- …
Bounded Depth Arithmetic Circuits: Counting And Closure, Eric Allender
Bounded Depth Arithmetic Circuits: Counting And Closure, Eric Allender
Computer Science Department Faculty Publication Series
Constant-depth arithmetic circuits have been defined and studied in [AAD97,ABL98]; these circuits yield the function classes #AC0 and GapAC0. These function classes in turn provide new characterizations of the computational power of threshold circuits, and provide a link between the circuit classes AC0 (where many lower bounds are known) and TC0 (where essentially no lower bounds are known). In this paper, we resolve several questions regarding the closure properties of #AC0 and GapAC0 and characterize #AC0 in terms of counting paths in a family of bounded-width graphs.
Strategy-Based Interactive Cluster Visualization For Information Retrieval, Anton Leuski, James Allan
Strategy-Based Interactive Cluster Visualization For Information Retrieval, Anton Leuski, James Allan
Computer Science Department Faculty Publication Series
In this paper we investigate a general purpose interactive information organization system. The system organizes documents by placing them into 1-, 2-, or 3- dimensional space based on their similarity and a springembedding algorithm. We begin by developing a method for estimating the quality of the organization when it is applied to a set of documents returned in response to a query. We show how the relevant documents tend to clump together in space. We proceed by presenting amethod for measuring the amount of structure in the organization and explain how this knowledge can be used to refine the system. …
Coordinating Agent Activities In Knowledge Discovery Processes, David Jensen
Coordinating Agent Activities In Knowledge Discovery Processes, David Jensen
Computer Science Department Faculty Publication Series
No abstract provided.
Design Considerations For Integrated Proxy Servers, Sambit Sahu
Design Considerations For Integrated Proxy Servers, Sambit Sahu
Computer Science Department Faculty Publication Series
Proxy servers reduce client access times as well as load on servers and networks by caching frequently accessed web objects. In this paper, we argue that the growing heterogeneity of data stored on web servers coupled with the increasing diversity in application requirements have made existing proxy servers inadequate. We examine the architecture and mechanisms required by integrated proxy servers that address this heterogeneity in application requirements and data characteristics. Finally, we briefly describe the architecture of an integrated proxy server that is currently being built in our research lab.
Scheduling Straight-Line Code Using Reinforcement Learning And Rollouts, Amy Mcgovern, Eliot Moss, Andrew G. Barto
Scheduling Straight-Line Code Using Reinforcement Learning And Rollouts, Amy Mcgovern, Eliot Moss, Andrew G. Barto
Computer Science Department Faculty Publication Series
The execution order of a block of computer instructions on a pipelined machine can make a difference in its running time by a factor of two or more. In order to achieve the best possible speed, compilers use heuristic schedulers appropriate to each specific architecture implementation. However, these heuristic schedulers are time-consuming and expensive to build. We present empirical results using both rollouts and reinforcement learning to construct heuristics for scheduling basic blocks. In simulation, the rollout scheduler outperformed a commercial scheduler, and the reinforcement learning scheduler performed almost as well as the commercial scheduler.
Using Self-Diagnosis To Adapt Organizational Structures, Bryan Horling, Brett Benyo, Victor Lesser
Using Self-Diagnosis To Adapt Organizational Structures, Bryan Horling, Brett Benyo, Victor Lesser
Computer Science Department Faculty Publication Series
The specific organization used by a multi-agent system is crucial for its effectiveness and efficiency. In dynamic environments, or when the objectives of the system shift, the organization must therefore be able to change as well. In this abstract we propose using a general diagnosis engine to drive this process of adaptation, using the TÆMS modeling language as the primary representation of organizational information.
An Efficient Algorithm For Computing Mhp Information For Concurrent Java Programs, Gleb Naumovich
An Efficient Algorithm For Computing Mhp Information For Concurrent Java Programs, Gleb Naumovich
Computer Science Department Faculty Publication Series
Information about which statements in a concurrent program may happen in parallel (MHP) has a number of important applications. It can be used in program optimization, debugging, program understanding tools, improving the accuracy of data flow approaches, and detecting synchronization anomalies, such as data races. In this paper we propose a data flow algorithm for computing a conservative estimate of the MHP information for Java programs that has a worstcase time bound that is cubic in the size of the program.We present a preliminary experimental comparison between our algorithm and a reachability analysis algorithm that determines the ”ideal” static MHP …
Improving Reliable Multicast Using Active Parity Encoding Services (Apes), Dan Rubenstein
Improving Reliable Multicast Using Active Parity Encoding Services (Apes), Dan Rubenstein
Computer Science Department Faculty Publication Series
We propose and evaluate novel reliable multicast protocols that combine active repair service (a.k.a. local recovery) and parity encoding (a.k.a. forward error correction or FEC) techniques. We show that, compared to other repair service protocols, our protocols require less buffer inside the network, maintain the low bandwidth requirements of previously proposed repair service / FEC combination protocols, and reduce the amount of FEC processing at repair servers, moving more of this processing to the end-hosts. We also examine repair service / FEC combination protocols in an environment where loss rates differ across domains within the network. We find that repair …
Deriving Deadlines And Periods For Real-Time Update Transactions, Ming Xiong, Krithi Ramamritham
Deriving Deadlines And Periods For Real-Time Update Transactions, Ming Xiong, Krithi Ramamritham
Computer Science Department Faculty Publication Series
Typically, temporal validity of real-time data is maintained by periodic update transactions. In this paper, we examine the problem of period and deadline assignment for these update transactions such that (1) these transactions can be guaranteed to complete by their deadlines and (2) the imposed workload is minimized. To this end, we propose a novel approach, named More-Less principle. By applying this principle, updates occur with a period which is more than the period obtained through traditional approaches but with a deadline which is less than the traditional period. We show that the More-Less principle is better than existing approaches …
Mirror: A State-Conscious Concurrency Control Protocol For Replicated Real-Time Databases, Ming Xiong, Krithi Ramamritham, Jayant Haritsa, John A. Stankovic
Mirror: A State-Conscious Concurrency Control Protocol For Replicated Real-Time Databases, Ming Xiong, Krithi Ramamritham, Jayant Haritsa, John A. Stankovic
Computer Science Department Faculty Publication Series
Data replication is one of the main techniques by which database systems can hope to meet the stringent temporal constraints of current time-critical applications, especially Web-based directory and electronic commerce services. A pre-requisite for realizing the benefits of replication, however, is the development of high-performance concurrency control mechanisms. We present in this paper MIRROR (Managing Isolation in Replicated Realtime Object Repositories), a concurrency control protocol specifically designed for firm-deadline applications operating on replicated real-time databases. MIRROR augments the optimistic two-phase locking (O2PL) algorithm developed for non real-time databases with a novel and simple to implement state-based conflict resolution mechanism to …
Discovering Dynamics Using Bayesian Clustering, Paola Sebastiani, Marco Ramoni, Paul Cohen, John Warwick, James Davis
Discovering Dynamics Using Bayesian Clustering, Paola Sebastiani, Marco Ramoni, Paul Cohen, John Warwick, James Davis
Computer Science Department Faculty Publication Series
This paper introduces a Bayesian method for clustering dy-namic processes and applies it to the characterization of the dynamics of a military scenario. The method models dynamics as Markov chains and then applies an agglomerative clustering procedure to discover the most probable set of clusters capturing the different dynamics. To increase effciency, the method uses an entropy-based heuristic search strategy.
Guidelines For Data-Parallel Cycle-Stealing In Networks Of Workstations, Ii: On Maximizing Guaranteed Output, Arnold L. Rosenberg
Guidelines For Data-Parallel Cycle-Stealing In Networks Of Workstations, Ii: On Maximizing Guaranteed Output, Arnold L. Rosenberg
Computer Science Department Faculty Publication Series
We derive efficient guidelines for scheduling dataparallel computations within a draconian mode of cyclestealing in networks of workstations wherein an interruption by the owner of the “borrowed” workstation kills all jobs currently in progress. We derive both adaptive and non-adaptive scheduling guidelines that maximize, up to low-order additive terms, the amount of work that one is guaranteed to accomplish during a cycle-stealing opportunity, no matter when the opportunity is interrupted—up to a prespecified number of times.
Learning Situation-Specific Coordination In Cooperative Multi-Agent Systems, M. V. Nagendra Prasad, Victor R. Lesser
Learning Situation-Specific Coordination In Cooperative Multi-Agent Systems, M. V. Nagendra Prasad, Victor R. Lesser
Computer Science Department Faculty Publication Series
Achieving effective cooperation in a multi-agent system is a difficult problem for a number of reasons such as limited and possiblyout-dated views of activitiesof other agents and uncertainty about the outcomes of interacting non-local tasks. In this paper, we present a learning system called COLLAGE, that endows the agents with the capability to learn how to choose the most appropriate coordination strategy from a set of available coordination strategies. COLLAGE relies onmeta-level information about agents’ problemsolving situations to guide themtowards a suitable choice for a coordination strategy. We present empirical results that strongly indicate the effectiveness of the learning algorithm.
Efficient Concurrency Control For Broadcast Environments, Jayavel Shanmugasundaram
Efficient Concurrency Control For Broadcast Environments, Jayavel Shanmugasundaram
Computer Science Department Faculty Publication Series
A crucial consideration in environments where data is broadcast to clients is the low bandwidth available for clients to communicate with servers. Advanced applications in such environments do need to read data that is mutually consistent as well as current. However, given the asymmetric communication capabilities and the needs of clients in mobile environments, traditional serializability-based approaches are too restrictive, unnecessary, and impractical. We thus propose the use of a weaker correctness criterion called update consistency and outline mechanisms based on this criterion that ensure (1) the mutual consistency of data maintained by the server and read by clients, and …
Natural Semantics For A Mobile Robot, Paul R. Cohen, Carole R. Beal
Natural Semantics For A Mobile Robot, Paul R. Cohen, Carole R. Beal
Computer Science Department Faculty Publication Series
Functionalism is the view that a system (or system component) grasps the meaning of its inputs to the extent that it produces the right outputs. If a system retrieves all and only relevant documents in response to a query, we say it understands the query. If a robot avoids bumping into walls, we say it understands its sensors and its environment. If a chess program beats the world champion, we say it understands the game. One kind of functionalism, conventional functionalism, is currently very popular and productive in artificial intelligence and the other cognitive sciences, but it requires humans to …