112612
Fair service for mice in the presence of elephants
We show how randomized caches can be used in resource-poor partial-state routers to provide a fair share of bandwidth to short-lived flows that are known as mice when long-lived flows known as elephants are present.
9646078
Parallel hashing algorithms on BSP and QSM models
Summary form only given. We study two parallel computing models - the bulk synchronous parallel (BSP) and the queued shared memory (QSM) - as alternatives to the PRAM model to provide more accurate performance predictions and analyses, and compares the two models in detail. As a case study, we consider a simple hashing problem, design the two versions - the message passing version and the shared memory version - of the algorithm, and compare their run time analytically. The message passing version of the algorithm is implemented and the experiments are performed to display the accuracy and the limitations of the predicted performance analysis.
8052541
Applications of probabilistic quorums to iterative algorithms
Presents a definition of a read-write register that sometimes returns out-of-date values, shows that the definition is implemented by the probabilistic quorum algorithm of D. Malkhi et al. (1997), and shows how to program with such registers using the framework of A. U/spl uml/resin and M. Dubois (1990). Consequently, existing iterative algorithms for an interesting class of problems (including finding shortest paths, constraint satisfaction and transitive closure) converge with high probability if executed in a system in which the shared data is implemented with registers satisfying the new definition. Furthermore, the algorithms in this framework inherit positive attributes concerning load and availability from the underlying register implementation. A monotone version of the new register definition is specified and implemented; it can provide improved expected convergence time and message complexity for iterative algorithms.
6784159
Randomized registers and iterative algorithms
Abstract.We present three different specifications of a read-write register that may occasionally return out-of-date values - namely, a (basic) random register, a P-random register, and a monotone random register. We show that these specifications are implemented by the probabilistic quorum algorithm of Malkhi, Reiter, Wool, and Wright, and we illustrate how to program with such registers in the framework of Bertsekas, using the notation of Üresin and Dubois. Consequently, existing iterative algorithms for a significant class of problems (including solving systems of linear equations, finding shortest paths, constraint satisfaction, and transitive closure) will converge with high probability if executed in a system in which the shared data is implemented with registers satisfying the new specifications. Furthermore, the algorithms in this framework will inherit positive attributes concerning load and fault-tolerance from the underlying register implementation. The expected convergence time for iterative algorithms using the monotone implementation is analyzed and shown experimentally to improve on that of the original implementation. The message complexity for iterative algorithms using the monotone probabilistic quorum implementation is shown to improve on that of non-probabilistic implementations in a quantifiable situation.
8279890
Location tracking using quorums in mobile ad hoc networks
Abstract We explore applications of quorum systems to the problem of tracking locations of mobile users in mobile ad hoc networks (MANETs). The location tracking system uses biquorum systems, a generalization of traditional quorum systems. We performed extensive simulations of the location tracking system. The simulation results show that our strict biquorum implementation has better performance than the traditional strict quorum implementations. Moreover, our results show that randomized dynamic quorum implementations have better overall performance than strict (bi)quorum implementations.
8884680
Using Segmented Objects in Ostensive Video Shot Retrieval
This paper presents a system for video shot retrieval in which shots are retrieved based on matching video objects using a combination of colour, shape and texture. Rather than matching on individual objects, our system supports sets of query objects which in total reflect the user's object-based information need. Our work also adapts to a shifting user information need by initiating the partitioning of a user's search into two or more distinct search threads, which can be followed by the user in sequence. This is an automatic process which maps neatly to the ostensive model for information retrieval in that it allows a user to place a virtual checkpoint on their search, explore one thread or aspect of their information need and then return to that checkpoint to then explore an alternative thread. Our system is fully functional and operational and in this paper we illustrate several design decisions we have made in building it.
19026342
Eager writeback - a technique for improving bandwidth utilization
Modern high-performance processors utilize multi-level cache structures to help tolerate the increasing latency of main memory. Most of these caches employ either a writeback or a write-through strategy to deal with store operations. Write-through caches propagate data to more distant memory levels at the time each store occurs, which requires a very large bandwidth between the memory hierarchy levels. Writeback caches can significantly reduce the bandwidth requirements between caches and memory by marking cache lines as dirty when stores are processed and writing those lines to the memory system only when that dirty line is evicted. Unfortunately, for applications that experience significant numbers of cache misses due to streaming data, writeback cache designs can degrade overall system performance by clustering bus activity when dirty lines contend with data being fetched into the cache. In this paper we present a new technique called Eager Writeback, which re-distributes and balances memory traffic by writing and "cleaning" dirty cache lines prior to their eviction. Eager Writeback can be viewed as a compromise between write-through and writeback policies, in which dirty lines are written later than write-through, but prior to writeback. We will show that this approach can reduce the large number of writes seen in a write-through design, while avoiding the performance degradation caused by clustering bus traffic in a writeback approach.
21234984
A distributed utility max-min flow control algorithm
A fair allocation of utility (application-layer performance) is essential in providing QoS (Quality of Service) guarantee. However, there have been few researches in the literature of utility-fair network resource allocation scheme. In this paper, we propose a distributed utility max-min flow control algorithm which accommodates application diversity in that it does not require the concavity of utility functions, and is scalable in that it does not require any per-flow operation in the network. The algorithm is proved to be convergent under the assumption that there exists a single bottleneck link and the communication delay between any two links in the network is bounded. Although the convergence of the algorithm is analyzed only for the case of a single bottleneck link, we show through simulations that the proposed algorithm works as designed for the case of multiple bottleneck links as well.
15685762
Why gulling software colleagues is popular
A few months ago, a 550-person software company in Oregon cut a significant part of its developer workforce to reduce expenses and align its salaries with industry averages. It had already streamlined its software development practices, which increased productivity and improved product reliability. During the year-long streamlining program, the company had mapped existing processes to make explicit exactly how software was being developed and then carefully refined the processes to reduce the cost and time required. Implementing these changes required people to relocate into multidisciplinary teams and eliminate tasks that added no value. The majority of staff, facilitated by consultants, participated in this process. At the end of these initiatives, our research team did a follow-up survey and investigation to gauge how well the company was now organized to let staff attain their corporate goals. We found room for more improvement, but also some interesting results regarding employees' attitudes toward staff reductions.
2331504
Centroidal Voronoi Tessellation-Based Reduced-Order Modeling of Complex Systems
\noindent A reduced-order modeling methodology based on centroidal Voronoi tessellations (CVTs) is introduced. CVTs are special Voronoi tessellations for which the generators of the Voronoi diagram are also the centers of mass (means) of the corresponding Voronoi cells. For discrete data sets, CVTs are closely related to the h-means and k-means clustering techniques. A discussion of reduced-order modeling for complex systems such as fluid flows is given to provide a context for the application of reduced-order bases. Then, detailed descriptions of CVT-based reduced-order bases and how they can be constructed from snapshot sets and how they can be applied to the low-cost simulation of complex systems are given. Subsequently, some concrete incompressible flow examples are used to illustrate the construction and use of CVT-based reduced-order bases. The CVT-based reduced-order modeling methodology is shown to be effective for these examples.