When: 10:00 - 11:00 AM, October 2
Where: 1257 Anthony Hall
Who: Andres Ramirez
Abstract: Increasingly, applications need to be able to self-reconfigure in response to changing requirements and environmental conditions. Autonomic computing has been proposed as a means for automating software maintenance tasks. As the complexity of adaptive and autonomic systems grows, designing and managing the set of reconfiguration rules becomes increasingly challenging and may produce inconsistencies. This paper proposes an approach to leverage genetic algorithms in the decision-making process of an autonomic computing system. This approach enables a system to dynamically evolve target reconfigurations at run time that balance tradeoffs between functional and non-functional requirements in response to changing requirements and environmental conditions. A key feature of this approach is incorporating system and environmental monitoring information into the genetic algorithm such that specific changes in the environment autonomically drive the evolutionary process towards new viable solutions. We have applied this genetic-algorithm based approach to the dynamic reconfiguration of a collection of remote data mirrors, with the goal of diffusing data and minimizing operational costs while maximizing data reliability and network performance, even in the presence of link failures.
When: 10:00 - 11:00 AM, October 9
Where: 1257 Anthony Hall
Who: Chad R. Meiners
Abstract: Ternary Content Addressable Memories (TCAMs) have become the de facto standard in industry for fast packet classification. Unfortunately, TCAMs have limitations of small capacity, high power consumption, high heat generation, and high cost. The well-known range expansion problem exacerbates these limitations as each classifier rule typically has to be converted to multiple TCAM rules. One method for coping with these limitations is to use compression schemes to reduce the number of TCAM rules required to represent a classifier. Unfortunately, all existing compression schemes only produce prefix classifiers. Thus, they all miss the compression opportunities created by non-prefix ternary classifiers.
In this paper, we propose bit weaving, the first non-prefix compression scheme. Bit weaving is based on the observation that TCAM entries that have the same decision and whose predicates differ by only one bit can be merged into one entry by replacing the bit in question with *. Bit weaving consists of two new techniques, bit swapping and bit merging, to first identify and then merge such rules together. The key advantages of bit weaving are that it runs fast, it is effective, and it is composable with other TCAM optimization methods as a pre/post-processing routine.
We implemented bit weaving and conducted experiments on both real-world and synthetic packet classifiers. Our experimental results show the following: (i) bit weaving is an effective stand-alone compression technique (it achieves an average compression ratio of 23.6%) and (ii) bit weaving finds compression opportunities that other methods miss. Specifically, bit weaving improves the prior TCAM optimization techniques of TCAM Razor and Topological Transformation by an average of 12.8% and 36.5%, respectively.
When: 10:00 - 11:00 AM, October 16
Where: 1257 Anthony Hall
Who: Brian Connelly
Abstract: Cooperative behaviors are pervasive in the natural world, yet how organisms can evolve stable strategies that incorporate such costly behaviors is a difficult problem. In my talk, I'll highlight some of the difficulties of cooperation and introduce some of the explanations that have been developed to address them. I'll then introduce some of the work that people have done in this area using digital evolution, focusing on my work examining at the roles that kin selection and dispersal play in evolving cooperative behaviors and two continuations of this work studying the effects of resource limitation and migration.
When: 10:00 - 11:00 AM, October 23
Where: 1257 Anthony Hall
Who: Matt McGill
Abstract: Software tools that analyze and generate code from ORM conceptual schemas are highly susceptible to feature interaction bugs. When testing such tools, test suites are needed that cover many combinations of features, including combinations that rarely occur in practice. Manually creating such a test suite is extremely labor- intensive, and the tester may fail to cover feasible feature combinations that are counter-intuitive or that rarely occur. This paper describes ATIG, a prototype tool for automatically generating test suites that cover diverse combinations of ORM features. ATIG makes use of combinatorial testing to optimize coverage of select feature combinations within constraints imposed by the need to keep the sizes of test suites manageable. We have applied ATIG to generate test inputs for an industrial strength ORM-to-Datalog code generator. Initial results suggest that it is useful for finding feature interaction errors in tools that operate on ORM models.
When: 10:00 - 11:00 AM, October 30
Where: 1257 Anthony Hall
Who: Fuad Abu-Jarad
Abstract: Given the non-determinism and race conditions in distributed programs, the ability to provide assurance about them is crucial. Our work focuses on incremental synthesis where we modify existing (fault-intolerant) distributed programs to add self-stabilization. We concentrate on reducing the time complexity of such synthesis using parallelism. We apply these techniques in the context of constraint satisfaction. In particular, incremental synthesis of self-stabilizing programs requires adding recovery actions to satisfy the constraint that are true in the legitimate states. We consider two approaches to speedup the synthesis algorithm: first, the use of the distributed nature of the programs being synthesized; second, the use of the multiple constraints that have to be satisfied during synthesis. We show that our approaches provide significant reductions in the synthesis time.
When: 10:00 - 11:00 AM, November 6
Where: 1257 Anthony Hall
Who: Fei Chen
Abstract: The architecture of two-tiered sensor networks, where storage nodes serve as an intermediate tier between sensors and a sink for storing data and processing queries, has been widely adopted because of the benefits of power and storage saving for sensors as well as the efficiency of query processing. However, the importance of storage nodes also makes them attractive to attackers. In this paper, we propose SafeQ, a protocol that prevents attackers from gaining information from both sensor collected data and sink issued queries. SafeQ also allows a sink to detect compromised storage nodes when they misbehave. To preserve privacy, SafeQ uses a novel technique to encode both data and queries such that a storage node can correctly process encoded queries over encoded data without knowing their actual values. To preserve integrity, we propose a new data structure called neighborhood chaining that allows a sink to verify whether the result of a query contains exactly the data items that satisfy the query. In addition, we propose a solution to adapt SafeQ for event-driven sensor networks.
When: 10:00 - 11:00 AM, November 13
Where: 1257 Anthony Hall
Who: Jingshu Chen
Abstract: In this paper, we classify multitolerant systems, i.e., systems that tolerate multiple classes of faults and provide potentially different levels of tolerance to them in terms of {\em strong} and {\em weak} multitolerance. Intuitively, this classification is based upon the guarantees provided by the program when one class of faults occurs while it is `recovering' from another class of faults. We focus on automated synthesis of {\em weak} multitolerant programs. Such \weak multitolerance becomes necessary when it is impossible to provide \strong multitolerance and/or when the probability of one class of faults occurring while the program is `recovering' from a fault from another class is negligible. By considering the levels of fault-tolerance provided to each class of faults, we evaluate five possible combinations for \weak multitolerance. We find a counterintuitive result that if masking fault-tolerance is desired for one class of faults and masking (or failsafe) fault-tolerance is desired for the second class of faults then the problem is NP-hard. This result is surprising since the corresponding problem for \strong multitolerance can be solved in polynomial time. Also, we show that the problem of synthesizing \weak multitolerance for other combinations is in P. More broadly, this result demonstrates the role of assumptions, e.g., independence of occurrences of faults from different classes, in the complexity of automated synthesis.
When: 10:00 - 11:00 AM, November 20
Where: 1257 Anthony Hall
Who: Yi Huang
Abstract: Thread synchronization is a key issue for developing reliable and efficient IP telecommunication services (IPT services). On the one hand, fixed synchronization protocols are not appropriate for all IPT services. They may degrade performance or even introduce unrecoverable deadlocks. On the other hand, manually coding synchronization---while flexible---is prone to errors. The logic to both infer the resources a thread requires and then lock the required resources is complex and cross-cutting. This complex "synchronization logic" can easily obscure an IPT service's "business logic." Interleaving synchronization code with business code makes an IPT service difficult to maintain and extend.
In this talk, I will present the research we are working on to address this issue. Specifically, I will elaborate key dimensions of the thread synchronization problem. I will also describe a novel synchronization model, which addresses these dimensions in a more comprehensive fashion than any existing model that we know of. This synchronization model is highly efficient and flexible. It introduces abstractions to promote correctness, safety, maintainability, and extensibility. I will describe a reference framework that implements these abstractions. I will also give an evaluation result of this framework applied to a realistic IPT service.