The Self-Paced Learning Increases Retention and Capacity (SPARC) project is responding to the well-documented surge in CS enrollment by creating a self-paced learning environment that blends online learning, automated assessment, collaborative practice, and peer-supported learning. SPARC delivers educational material online, encourages students to practice programming in groups, frees them to learn material at their own pace, and allows them to demonstrate proficiency at any time. This model contrasts with traditional course offerings, which impose a single schedule of due dates and exams for all students. SPARC allows students to complete courses faster or slower at a pace tailored to the individual, thereby allowing universities to teach more students with the same or fewer resources. This paper describes the goals and elements of the SPARC model as applied to CS1. We present results so far and discuss the future of the project.

Wireless sensor networks (WSNs) are increasingly used in many applications, such as volcano and fire monitoring, urban sensing, and perimeter surveillance. In a large WSN, in-network data aggregation (i.e., combining partial results at intermediate nodes during message routing) significantly reduces the amount of communication overhead and energy consumption. The research community proposed a loss-resilient aggregation framework called synopsis diffusion, which uses duplicate-insensitive algorithms on top of multipath routing schemes to accurately compute aggregates (e.g., predicate count or sum). However, this aggregation framework does not address the problem of false subaggregate values contributed by compromised nodes. This attack may cause large errors in the aggregate computed at the base station, which is the root node in the aggregation hierarchy. In this paper, we make the synopsis diffusion approach secure against the above attack launched by compromised nodes. In particular, we present an algorithm to enable the base station to securely compute predicate count or sum even in the presence of such an attack. Our attack-resilient computation algorithm computes the true aggregate by filtering out the contributions of compromised nodes in the aggregation hierarchy. Extensive analysis and simulation study show that our algorithm outperforms other existing approaches.

In this paper, we investigate the issues that arise in the use of network capabilities to facilitate DoS prevention and mitigation in mobile ad hoc networks. Most proposals for capability-based protocols in wired networks depend upon routers on the path between the sender and receiver maintaining state that enables them to verify a capability. Frequent route changes make it necessary for any capability-based protocol for MANETs to re-establish this state as efficiently as possible. We propose EPIC, a method based on reverse-disclosure hash chains to support the establishment of path-independent capabilities and show how they can be efficiently maintained in a high mobility environment. Simulation results show that EPIC provides a 25.9% increase in performance and a 38.3% increase in efficiency over route-dependent capabilities.

In a large sensor network, in-network data aggregation significantly reduces the amount of communication and energy consumption. Recently, the research community has proposed a robust aggregation framework called synopsis diffusion which combines multipath routing schemes with duplicate-insensitive algorithms to accurately compute aggregates (e.g., predicate Count, Sum) in spite of message losses resulting from node and transmission failures. However, this aggregation framework does not address the problem of false subaggregate values contributed by compromised nodes resulting in large errors in the aggregate computed at the base station, which is the root node in the aggregation hierarchy. This is an important problem since sensor networks are highly vulnerable to node compromises due to the unattended nature of sensor nodes and the lack of tamper-resistant hardware.

We analyze the security vulnerabilities of PEAS, ASCENT, and CCP, three well-known topology maintenance protocols (TMPs) for sensor networks. These protocols aim to increase the lifetime of the sensor network by only maintaining a subset of nodes in an active or awake state. The design of these protocols assumes that the sensor nodes will be deployed in a trusted, nonadversarial environment, and does not take into account the impact of attacks launched by malicious insider or outsider nodes. We propose a metaprotocol (Meta-TMP) to represent the class of topology maintenance protocols. The Meta-TMP provides us with a better understanding of the characteristics and of how a specific TMP works, and it can be used to study the vulnerabilities of a specific TMP. We describe various types of malicious behavior and actions that can be carried out by an adversary to attack a wireless sensor network by exploiting the TMP being used in the network. We describe three attacks against these protocols that may be used to reduce the lifetime of the sensor network, or to degrade the functionality of the sensor application by reducing the network connectivity and the sensing coverage that can be achieved. Further, we describe countermeasures that can be taken to increase the robustness of the protocols and make them resilient to such attacks.

In this paper, we introduce the concept ofwitness anonymityfor peer-to-peer systems, as well as other systems with the peer-to-peer nature. Witness anonymity combines the seemingly conflicting requirements of anonymity (for honest peers who report on the misbehavior of other peers) and accountability (for malicious peers that attempt to misuse the anonymity feature to slander honest peers). We propose theSecure Deep Throat(SDT) protocol to provide anonymity for the witnesses of malicious or selfish behavior to enable such peers to report on this behavior without fear of retaliation. On the other hand, in SDT, the misuse of anonymity is restrained in such a way that any malicious peer attempting to send multiple claims against the same innocent peer for the same reason (i.e., the same misbehavior type) can be identified. We also describe how SDT can be used in two modes. The active mode can be used in scenarios with real-time requirements, e.g., detecting and preventing the propagation of peer-to-peer worms, whereas the passive mode is suitable for scenarios without strict real-time requirements, e.g., query-based reputation systems. We analyze the security and overhead of SDT, and present countermeasures that can be used to mitigate various attacks on the protocol. Moreover, we show how SDT can be easily integrated with existing protocols/mechanisms with a few examples. Our analysis shows that the communication, storage, and computation overheads of SDT are acceptable in peer-to-peer systems.

Due to the poor physical protection of sensor nodes, it is generally assumed that an adversary can capture and compromise a small number of sensors in the network. In a node replication attack, an adversary can take advantage of the credentials of a compromised node to surreptitiously introduce replicas of that node into the network. Without an effective and efficient detection mechanism, these replicas can be used to launch a variety of attacks that undermine many sensor applications and protocols. In this paper, we present a novel distributed approach called Localized Multicast for detecting node replication attacks. The efficiency and security of our approach are evaluated both theoretically and via simulation. Our results show that, compared to previous distributed approaches proposed by Parno et al., Localized Multicast is more efficient in terms of communication and memory costs in large-scale sensor networks, and at the same time achieves a higher probability of detecting node replicas.

This paper presents CORD, a reliable bulk data dissemination protocol for propagating a large data object to all the nodes in a large scale sensor network. Unlike well- known reliable data dissemination protocols such as Deluge whose primary design criterion is to reduce the latency of object propagation, CORD's primary goal is to minimize energy consumption. To achieve its goals CORD employs a two phase approach in which the object is delivered to a subset of nodes in the network that form a connected dominating set in the first phase, and to the remaining nodes in the second phase. Further, CORD installs a coordinated sleep schedule on the nodes in the network whereby nodes that are not involved in receiving or transmitting data can turn off their radios to reduce their energy consumption. We evaluated the performance of CORD experimentally on both an indoor and outdoor sensor network testbed and via extensive simulations. Our results show that in comparison to Deluge (the de facto network reprogramming protocol for TinyOS) CORD significantly reduces the energy consumption for reliable data dissemination while achieving a comparable latency.

Wireless Sensor Networks (WSNs) have proven to be useful in many applications, such as military surveillance and environment monitoring. To meet the severe energy constraints in WSNs, some researchers have proposed to use the in-network data aggregation technique (i.e., combining partial results at intermediate nodes during message routing), which significantly reduces the communication overhead. Given the lack of hardware support for tamper resistance and the unattended nature of sensor nodes, sensor network protocols need to be designed with security in mind. Recently, researchers proposed algorithms for securely computing a few aggregates, such as Sum (the sum of the sensed values), Count (number of nodes) and Average. However, to the best of our knowledge, there is no prior work which securely computes the Median, although the Median is considered to be an important aggregate. The contribution of this paper is twofold. We first propose a protocol to compute an approximate Median and verify if it has been falsified by an adversary. Then, we design an attack-resilient algorithm to compute the Median even in the presence of a few compromised nodes. We evaluate the performance and cost of our approach via both analysis and simulation. Our results show that our approach is scalable and efficient.

Wireless sensor nodes lack hardware support for tamper- resistance and are often deployed in unattended environments, thus leaving them vulnerable to capture and compromise by an adversary. In a node replication attack, an adversary uses the credentials of a compromised node to surreptitiously introduce replicas of that node into the network. These replicas are then used to launch a variety of attacks that subvert the goal of the sensor application, and the operation of the underlying protocols. We present a novel distributed approach called Localized Multicast for detecting node replication attacks. We evaluate the performance and security of our approach both theoretically and via simulation. Our results show that Localized Multicast is more efficient than previous distributed approaches in terms of communication and memory costs. Further, in our approach, the probability of detecting node replicas is much higher than that achieved in previous distributed protocols.

Sensor networks are often deployed in unattended environments, thus leaving these networks vulnerable to false data injection attacks in which an adversary injects false data into the network with the goal of deceiving the base station or depleting the resources of the relaying nodes. Standard authentication mechanisms cannot prevent this attack if the adversary has compromised one or a small number of sensor nodes. We present three interleaved hop-by-hop authentication schemes that guarantee that the base station can detect injected false data immediately when no more than t nodes are compromised, where t is a system design parameter. Moreover, these schemes enable an intermediate forwarding node to detect and discard false data packets as early as possible. Our performance analysis shows that our scheme is efficient with respect to the security it provides, and it also allows a tradeoff between security and performance. A prototype implementation of our scheme indicates that our scheme is practical and can be deployed on the current generation of sensor nodes.

In this paper, we introduce the concept of witness anonymity for peer-to-peer systems. Witness anonymity combines the seemingly conflicting requirements of anonymity (for honest peers who report on the misbehavior of other peers) and accountability (for malicious peers that attempt to misuse the anonymity feature to slander honest peers). We propose the Secure Deep Throat (SDT) protocol to provide anonymity for witnesses of malicious or selfish behavior to enable such peers to report on this behavior without fear of retaliation. On the other hand, in SDT the misuse of anonymity is restrained in such a way that any malicious peer that attempts to send multiple claims against the same innocent peer for the same reason (i.e., the same misbehavior type) can be identified. We also describe how SDT can be used in two modes. The active mode can be used in scenarios with real-time requirements, e.g., detecting and preventing the propagation of peer-to-peer worms, whereas the passive mode is suitable for scenarios without strict real-time requirements, e.g., query-based reputation systems. We analyze the security and overhead of SDT and present countermeasures that can be used to mitigate various attacks on the protocol. Our analysis shows that the communication, storage, and computation overheads of SDT are acceptable in peer-to-peer systems.

We present GKMPAN, an efficient and scalable group rekeying protocol for secure multicast in ad hoc networks. Our protocol exploits the property of ad hoc networks that each member of a group is both a host and a router, and distributes the group key to member nodes via a secure hop-by-hop propagation scheme. A probabilistic scheme based on pre-deployed symmetric keys is used for implementing secure channels between members for group key distribution. GKMPAN also includes a novel distributed scheme for efficiently updating the pre-deployed keys. GKMPAN has three attractive properties. First, it is significantly more efficient than group rekeying schemes that were adapted from those proposed for wired networks. Second, GKMPAN has the property of partial statelessness; that is, a node can decode the current group key even if it has missed a certain number of previous group rekeying operations. This makes it very attractive for ad hoc networks where nodes may lose packets due to transmission link errors or temporary network partitions. Third, in GKMPAN the key server does not need any information about the topology of the ad hoc network or the geographic location of the members of the group. We study the security and performance of GKMPAN through detailed analysis and simulation; we have also implemented GKMPAN in a sensor network testbed.

We describe LEAP+ (Localized Encryption and Authentication Protocol), a key management protocol for sensor networks that is designed to support in-network processing, while at the same time restricting the security impact of a node compromise to the immediate network neighborhood of the compromised node. The design of the protocol is motivated by the observation that different types of messages exchanged between sensor nodes have different security requirements, and that a single keying mechanism is not suitable for meeting these different security requirements. LEAP+ supports the establishment of four types of keys for each sensor node: an individual key shared with the base station, a pairwise key shared with another sensor node, a cluster key shared with multiple neighboring nodes, and a global key shared by all the nodes in the network. LEAP+ also supports (weak) local source authentication without precluding in-network processing. Our performance analysis shows that LEAP+ is very efficient in terms of computational, communication, and storage costs. We analyze the security of LEAP+ under various attack models and show that LEAP+ is very effective in defending against many sophisticated attacks, such as HELLO flood attacks, node cloning attacks, and wormhole attacks. A prototype implementation of LEAP+ on a sensor network testbed is also described.

This paper presents McTorrent and McSynch, two multichannel sensor network protocols for data dissemination. Both protocols are designed to take advantage of the spatial multiplexing properties of the half-duplex radio transceivers available on the current generation of sensor nodes. McTorrent is used for reliable end-to-end dissemination of a large data object. Compared to existing protocols, we show that McTorrent significantly reduces the amount of time required to propagate a large data object throughout a sensor network. McSynch is used to achieve data object synchronization within a local cluster of nodes. By using a scheduled channel access approach and an appropriate number of transmission channels, McSynch can significantly reduce the amount of time required to update a local cluster. We also describe our experiences implementing a multichannel system, and report on lessons learned for channel and frequency settings.

Abstract — Most of the multicast routing protocols proposed for ad hoc networks assume a trusted, non-adversarial environment and do not take security issues into account in their design. In this paper, we investigate the security of MAODV (Multicast Ad hoc On-Demand Distance Vector protocol), a well-known multicast routing protocol, and identify several attacks on it. We show, via simulation, that these attacks can have a significant impact on the performance of MAODV. We present an authentication framework for MAODV and propose countermeasures that can prevent or mitigate the impact of these attacks. I.

We analyze the security vulnerabilities of PEAS, ASCENT, and CCP, three well-known topology maintenance protocols for sensor networks. These protocols aim to increase the lifetime of the sensor network by maintaining only a subset of nodes in an active or awake state. The design of these protocols assumes that the sensor nodes will be deployed in a trusted non-adversarial environment, and does not take into account the impact of attacks launched by malicious insider and outsider nodes. We describe three attacks against these protocols that can be used to reduce the lifetime of the sensor network, or to degrade the functionality of the sensor application by reducing the network connectivity and sensing coverage that can be achieved. Further, we describe counter-measures that can be used to increase the robustness of the protocols and make them resilient to such attacks.

We present GKMPAN, an efficient and scalable group rekeying protocol for secure multicast in ad hoc networks. Our protocol exploits the property of ad hoc networks that each member of a group is both a host and a router, and distributes the group key to member nodes via a secure hop-by-hop propagation scheme. A probabilistic scheme based on predeployed symmetric keys is used for implementing secure channels between members for group key distribution. GKMPAN also includes a novel distributed scheme for efficiently updating the predeployed keys. GKMPAN has three attractive properties. First, it is significantly more efficient than group rekeying schemes that were adapted from those proposed for wired networks. Second, GKMPAN has the property of partial statelessness; that is, a node can decode the current group key even if it has missed a certain number of previous group rekeying operations. This makes it very attractive for ad hoc networks where nodes may lose packets due to transmission link errors or temporary network partitions. Third, in GKMPAN the key server does not need any information about the topology of the ad hoc network or the geographic location of the members of the group. We study the security and performance of GKMPAN through detailed analysis and simulation.

Sensor networks are often deployed in unattended environments, thus leaving these networks vulnerable to false data injection attacks in which an adversary injects false data into the network with the goal of deceiving the base station or depleting the resources of the relaying nodes. Standard authentication mechanisms cannot prevent this attack if the adversary has compromised one or a small number of sensor nodes. In this paper, we present an interleaved hop-by-hop authentication scheme that guarantees that the base station will detect any injected false data packets when no more than a certain number t nodes are compromised. Further, our scheme provides an upper bound B for the number of hops that a false data packet could be forwarded before it is detected and dropped, given that there are up to t colluding compromised nodes. We show that in the worst case B is O(t/sup 2/). Through performance analysis, we show that our scheme is efficient with respect to the security it provides, and it also allows a tradeoff between security and performance.

In this paper, we describe LEAP (Localized Encryption and Authentication Protocol), a key management protocol for sensor networks that is designed to support in-network processing, while at the same time restricting the security impact of a node compromise to the immediate network neighborhood of the compromised node. The design of the protocol is motivated by the observation that different types of messages exchanged between sensor nodes have different security requirements, and that a single keying mechanism is not suitable for meeting these different security requirements. LEAP supports the establishment of four types of keys for each sensor node -- an individual key shared with the base station, a pairwise key shared with another sensor node, a cluster key shared with multiple neighboring nodes, and a group key that is shared by all the nodes in the network. The protocol used for establishing and updating these keys is communication- and energy-efficient, and minimizes the involvement of the base station. LEAP also includes an efficient protocol for inter-node traffic authentication based on the use of one-way key chains. A salient feature of the authentication protocol is that it supports source authentication without precluding in-network processing and passive participation. We analyze the performance and the security of our scheme under various attack models and show our schemes are very efficient in defending against many attacks.

Recently, many group key management approaches based on the use of logical key trees have been proposed to address the issue of scalable group rekeying that is needed to support secure communications for large and dynamic groups. In this paper, we present two optimizations for logical key tree organizations that utilize information about the characteristics of group members to further reduce the overhead of group rekeying. First, we propose a partitioned key tree organization that exploits the temporal patterns of group member joins and departures to reduce the overhead of rekeying. Using an analytic model, we show that our optimization can achieve up to 31.4% reduction in key server bandwidth overhead over the unoptimized scheme. Second, we propose an approach under which the key tree is organized based on the loss probabilities of group members. Our analysis shows this optimization can reduce the rekeying overhead by up to 12.1%.

A prerequisite for a secure communication between two nodes in an ad hoc network is that the nodes share a key to bootstrap their trust relationship. In this paper, we present a scalable and distributed protocol that enables two nodes to establish a pairwise shared key on the fly, without requiring the use of any on-line key distribution center. The design of our protocol is based on a novel combination of two techniques - probabilistic key sharing and threshold secret sharing. Our protocol is scalable since every node only needs to possess a small number of keys, independent of the network size, and it is computationally efficient because it only relies on symmetric key cryptography based operations. We show that a pairwise key established between two nodes using our protocol is secure against a collusion attack by up to a certain number of compromised nodes. We also show through a set of simulations that our protocol can be parameterized to meet the desired levels of performance, security and storage for the application under consideration.

In this paper, we describe LEAP (Localized Encryption and Authentication Protocol), a key management protocol for sensor networks that is designed to support in-network processing techniques such as passive participation. LEAP includes support for multiple symmetric keying mechanisms including individual keys, pairwise shared keys, cluster keys, and a group key. This design is based on the observation that different types of messages exchanged between sensor nodes have different security requirements, and a single keying mechanism is not suitable for meeting these different security requirements.

The authors describe a novel approach to scalable group re-keying for secure multicast. Our approach, which we call Kronos, is based upon the idea of periodic group re-keying. We first motivate our approach by showing that if a group is re-keyed on each membership change, as the size of the group increases and/or the rate at which members leave and join the group increases, the frequency of rekeying becomes the primary bottle neck for scalable group re-keying. In contrast, Kronos can scale to handle large and dynamic groups because the frequency of re-keying is independent of the size and membership dynamics of the group. Next, we describe how Kronos can be used in conjunction with distributed key management frameworks such as IGKMP (T. Hardjono et al., 1998) that use a single group-wide session key for encrypting communications between members of the group. Using a detailed simulation, we compare the performance tradeoffs between Kronos and other key management protocols.

In this paper, we present the design and implementation of Dodo, an efficient user-level system for harvesting idle memory in off-the-shelf clusters of workstations. Dodo enables data-intensive applications to use remote memory in a cluster as an intermediate cache between local memory and disk. It requires no modifications to the operating system and/or processor firmware and is hence portable to multiple platforms. Further, the memory recruitment policy used by Dodo is designed to minimize any delays experienced by the owner of desktop machines whose memory is harvested by Dodo. Our implementation of Dodo is operational and currently runs on Linux 2.0.35. For communication, Dodo can use either UDP/IP or U-Net, the low-latency user-level network architecture developed by von Eicken et al. (1995). We evaluated the performance improvements that can be achieved by using Dodo for two real applications and three synthetic benchmarks. Our results show that speedups obtained for an application are highly dependent on its I/O access pattern and data set sizes. Significant speedups (between 2 and 3) were obtained for applications whose working sets are larger than the local memory on a workstation but smaller than aggregate memory available on the cluster and for applications that can benefit from the zero-seek nature of remote memory.

In this paper, we examine the availability and utility of idle memory in workstation clusters.We attempt to answer the following questions.First, how much of the total memory in a workstation cluster can be expected to be idle?This provides an estimate of the opportunity for hosting guest data.Second, how much memory can be expected to be idle on individual workstations?This helps determine the recruitment policy -how much memory should be recruited on individual hosts?Third, what is the distribution of memory idle-times?This indicates how long guest data can be expected to survive; applications that access their data-sets frequently within the expected life-time of guest data are more likely to benefit from exploiting idle memory.Fourth, how much performance improvement can be achieved for offthe-shelf clusters without customizing the operating system and/or the processor firmware?Finally, how long and how frequently might a user have to wait to reclaim her machine if she volunteers to host guest pages on her machine?This helps answer the question of social acceptability.To answer the questions relating to the availability of idle memory, we have analyzed two-week long traces from two workstation pools with different sizes, locations, and patterns of use.To evaluate the expected benefits and costs, we have simulated five data-intensive applications (0.5 GB-5 GB) on these workstation pools.

Most concurrency control algorithms for multilevel secure databases based on kernelized architecture prevent covert channels between transactions at different security levels by preempting the high security transaction in the event of a data conflict with a lower security transaction. In environments with moderate to high levels of contention between low and high security transactions, this can lead to poor performance and even starvation of high security transactions. We examine this problem of unfairness in concurrency control mechanisms for secure databases. Based on an analysis of the performance of a secure version of two phase locking, we propose three different modifications to the protocol that address the problem of starvation of high security transactions. Through a detailed simulation study, we examine the fairness and performance of these approaches for a variety of workloads.

No abstract available.

The constrained 2D cutting stock problem is an irregular problem with dynamic data structures, highly variable amounts of computation per task, and unpredictable amounts and patterns of communication. This paper describes the design and implementation of a parallel solution to this problem on a cluster of workstations and a distributed memory multicomputer. The key element of our parallel solution is the replication of an important data structure on all processors. By exploiting properties of the cutting stock problem which allow the use of relaxed consistency mechanisms, our approach is able to reduce the overheads for communication and synchronization in comparison to approaches that partition the data structure among processors. A token-based lazy release consistency protocol is used to ensure mutual exclusion and maintain consistency, and a randomized work-stealing protocol is employed to dynamically balance work among processors. Good speedups are reported for three benchmark problems executed on two distributed memory platforms: a cluster of workstations interconnected by a 10 Mbit/s Ethernet and an Intel Paragon. © 1998 John Wiley & Sons, Ltd.

Clusters of workstations are increasingly being viewed as a cost effective alternative to parallel supercomputers. However, resource management and scheduling on workstations clusters is complicated by the fact that the number of idle workstations available for executing parallel applications is constantly fluctuating. We present a case for scheduling parallel applications on non dedicated workstation clusters using dynamic space sharing, a policy under which the number of processors allocated to an application can be changed during its execution. We describe an approach that uses application level checkpointing and data repartitioning for supporting dynamic space sharing and for handling the dynamic reconfiguration triggered when failure or owner activity is detected on a workstation being used by a parallel application. The performance advantages of dynamic space sharing are quantified through a simulation study, and experimental results are presented for the overhead of dynamic reconfiguration of a grid oriented data parallel application using our approach.

Gang scheduling is a job scheduling policy for parallel computers that combines elements of space-sharing and time-sharing. In this paper we analyze the performance of gang scheduling policies that allow the remapping of an executing job to a new set of processors. Most previously proposed gang-scheduling policies do not allow such job remapping under the assumption that it is prohibitively expensive. Through a detailed trace-driven simulation, we analyze the tradeoff between the benefits and overheads of such job relocation. Our results show that gang-scheduling policies that support such job relocation offer significant performance gains over policies that do not use remapping.

The paper describes the design and implementation of a solution to the constrained 2D cutting stock problem on a cluster of workstations. The constrained 2D cutting stock problem is an irregular problem with a dynamically modified global data set and irregular amounts and patterns of communication. A replicated data structure is used for the parallel solution since the ratio of reads to writes is known to be large. Mutual exclusion and consistency are maintained using a token based lazy consistency mechanism, and a randomized protocol for dynamically balancing the distributed work queue is employed. Speedups are reported for three benchmark problems executed on a cluster of workstations interconnected by a 10 Mbps Ethernet.

We examine the tradeoff between message overhead and data availability that arises in the design of fault-tolerant algorithms for replicated data management in distributed systems. We propose a property called asymptotically high resiliency which is useful for evaluating the fault-tolerance of replica control algorithms and distributed mutual exclusion algorithms. We present a new algorithm for replica control that can be tailored (through a design parameter) to achieve the desired balance between low message overhead and high data availability. Further, we show that for a message overhead of O(/spl radic/(Nlog N)), our algorithm can achieve asymptotically high resiliency.

A main objective of scheduling independent jobs composed of multiple sequential tasks in shared-memory and distributed-memory multiprocessor computer systems is the assignment of these tasks to processors in a manner that ensures efficient operation of the system. Achieving this objective requires the analysis of a fundamental tradeoff between maximizing parallel execution, suggesting that the tasks of a job be spread across all system processors, and minimizing synchronization and communication overheads, suggesting that the job's tasks be executed on a single processor. The authors consider a class of scheduling policies that represent the essential aspects of this processor allocation tradeoff, and model the system as a distributed fork-join queueing system. They derive an approximation for the expected job response time, which includes the important effects of various parallel processing overheads (such as task synchronization and communication) induced by the processor allocation policy.>

The authors analyze three general classes of scheduling policies under a workload typical of large-scale scientific computing. These policies differ in the manner in which processors are partitioned among the jobs as well as the way in which jobs are prioritized for execution on the partitions. The results indicate that existing static schemes to not perform well under varying workloads. Adaptive policies tend to make better scheduling decisions, but their ability to adjust to workload changes is limited. Dynamic partitioning policies, on the other hand, yield the best performance and can be tuned to provide desired performance differences among jobs with varying resource demands.

Multicomputers, consisting of many processing nodes connected through a high speed interconnection network, have become an important and common platform for a large body of scientific computations. These parallel systems have traditionally executed programs in batch mode, or have at most space-shared the processors among multiple programs using a static partitioning policy. This, however, can result in relatively low system utilization and throughput for important classes of scientific applications.In this paper we consider "a class of scheduling policies that attempt to increase processor utilization and system throughput by timesharing a partition of processors among multiple programs. We compare the system performance under this multiprogramming policy with that of static partitioning for a variety of workloads via both analytic and simulation modeling. Our results show that timesharing a partition can provide significant improvements in performance, particularly at moderate to heavy loads. The performance gains of the multiprogrammed policy depend upon the inherent efficiency of the parallel programs that comprise the workload, decreasing with increasing program efficiency. Our analysis also provides the regions over which one scheduling policy outperforms the other, as a function of system load.

The problem of managing replicated copies of data in a distributed database is considered. Quorum consensus methods for managing replicated data require that an operation proceed only if a group of copies form a quorum. For example, in a majority voting scheme, for a write operation to proceed, a majority of the copies have to form a quorum. The authors first introduce a performance measure for measuring the performance of fault-tolerant algorithms for this problem. They then propose a quorum-based method which is highly fault tolerant and has a low message overhead. The algorithm can tradeoff fault tolerance for lower message overhead. The algorithm is compared to existing algorithms.>

A disk cache is typically used in file systems to reduce average access time for data storage and retrieval. The 'periodic update' write policy, widely used in existing computer systems, is one in which dirty cache blocks are written to a disk on a periodic basis. The average response time for disk read requests when the periodic update write policy is used is determined. Read and write load, cache-hit ratio, and the disk scheduler's ability to reduce service time under load are incorporated in the analysis, leading to design criteria that can be used to decide among competing cache write policies. The main conclusion is that the bulk arrivals generated by the periodic update policy cause a traffic jam effect which results in severely degraded service. Effective use of the disk cache and disk scheduling can alleviate this problem, but only under a narrow range of operating conditions. Based on this conclusion, alternate write packages that retain the periodic update policy's advantages and provide uniformly better service are proposed.>