We provide a simplified proof of the 3-competitiveness of the greedy algorithm for scheduling weighted packets in the multi-FIFO buffer model. Azar and Richter provided a proof using the zero-one principle (Azar and Richter, STOC 2004). We use a different approach and we hope our approach can lead to an improved FIFO buffering algorithm.
One promising technique for defending software systems against vulnerabilities involves the use of self-healing. Such efforts, however, carry a great deal of risk because they largely bypass the cycle of human-driven patching and testing used to vet both vendor and internally developed patches. In particular, it is difficult to predict if a repair will keep the behavior of the system consistent with "normal" behavior. Assuring that post-repair behavior does not deviate from normal behavior is a major challenge to which no satisfactory solutions exist. We investigate the feasibility of automatically measuring behavioral deviations in software that has undergone a self-healing repair. We provide a first examination of the problem of assessing a repair's impact on execution behavior, and we define a model for representing post-repair behavior using machine-level intraprocedural control flow. In essence, we advocate performing anomaly detection on an application's execution
How does one repeatedly choose actions so as to be fairest to the multiple beneficiaries of those actions? We examine approaches to discovering sequences of actions for which the worst-off beneficiaries are treated maximally well, then secondarily the second-worst-off, and so on. We formulate the problem for the situation where the sequence of action choices continues forever; this problem may be reduced to a set of linear programs. We then extend the problem to situations where the game ends at some unknown finite time in the future. We demonstrate that an optimal solution is NP-hard, and present two good approximation algorithms.
Solutions to non-cooperative multiagent systems often require achieving a joint policy which is as fair to all parties as possible. There are a variety of methods for determining the fairest such joint policy. One approach,
This document describes the preferred formatting of technical reports and submission guidelines. This document itself is formatted according to the preferred formatting rules.