Adam is arguably one of the most commonly used approach in deep learning and machine learning. With good regret bounds and empirical convergence proofs, the approach has produced many state-of-the-art models over a variety of problems. However, the method only uses gradient information at each iterate in addition to some moving averaged gradients and its corresponding moments from the past. In this paper, we propose a method that builds upon Adam and incorporates quasi-Newton matrices for approximating second derivatives. These Hessian approximations satisfy the so-called secant equation, which is the first-order Taylor series expansion of the gradient along the direction of the change in iterates. Judicious choices of quasi-Newton matrices can lead to guaranteed descent in the objective function and improved convergence. In this work, we integrate search directions obtained from using these quasi-Newton Hessian approximations with the Adam optimization algorithm. We provide convergence guarantees and demonstrate improved performance through an extensive experimentation on a variety of applications.

LoRa has become one of the most promising networking technologies for Internet-of-Things applications. Distant end devices have to use a low data rate to reach a LoRa gateway, causing long in-the-air transmission time and high energy consumption. Compared with the end devices using high data rates, they will drain the batteries much earlier and the network may be broken early. Such an energy unfairness can be mitigated by deploying more gateways. However, with more gateways, more end devices may choose small spreading factors to reach closer gateways, increasing the collision probability. In this paper, we propose a networking solution for LoRa networks, EF-LoRa, that can achieve energy fairness among end devices by carefully allocating network resources, including frequency channels, spreading factors and transmission power. We develop a LoRa network model to study the energy consumption of the end devices, considering the unique features of LoRa networks such as LoRaWAN MAC protocol and the capacity limitation of a gateway. We formulate the energy fairness allocation as an optimization problem, and propose a greedy allocation algorithm to achieve max-min fairness of energy efficiency. Simulation results show that EF-LoRa can improve the energy fairness of the state-of-the-art works by 177.8%.

Machine learning models are vulnerable to data poisoning attacks whose purpose is to undermine the model’s integrity. However, the current literature on data poisoning attacks mainly focuses on ad hoc techniques that are generally limited to either binary classifiers or to gradient-based algorithms. To address these limitations, we propose a novel model-free label-flipping attack based on the multi-modality of the data, in which the adversary targets the clusters of classes while constrained by a label-flipping budget. The complexity of our proposed attack algorithm is linear in time over the size of the dataset. Also, the proposed attack can increase the error up to two times for the same attack budget. Second, a novel defense technique is proposed based on the Synthetic Reduced Nearest Neighbor model. The defense technique can detect and exclude flipped samples on the fly during the training procedure. Our empirical analysis demonstrates that (i) the proposed attack technique can deteriorate the accuracy of several models drastically, and (ii) under the proposed attack, the proposed defense technique significantly outperforms other conventional machine learning models in recovering the accuracy of the targeted model.

Decision trees are a convenient and established approach for any supervised learning task. Decision trees are trained by greedily splitting a leaf nodes, into two leaf nodes until a specific stopping criterion is reached. Splitting a node consists of finding the best feature and threshold that minimizes a criterion. The criterion minimization problem is solved through a costly exhaustive search algorithm. This paper proposes a novel stochastic approach for criterion minimization. The algorithm is compared with several other related state-of-the-art decision tree learning methods, including the baseline non-stochastic approach. We apply the proposed algorithm to learn a Haar tree over MNIST dataset that consists of over 200, 000 features and 60, 000 samples. The result is comparable to the performance of oblique trees while providing a significant speed-up in both inference and training times.

Synthetic Reduced Nearest Neighbor is a nearest neighbor model that is constrained on synthetic samples (i.e., prototypes). The body of work on such models includes proposals for improving the interpretability and optimization of SRNN models using expectation maximization. Motivated by the promise of this paradigm, we propose a novel Expectation Maximization approach for Synthetic Reduced Nearest Neighbors leveraging neural networks. Furthermore, we compare the performance of our proposed technique to classical state-of-the-art machine learning methods such as random forest and ensemble models. The empirical results demonstrate the advantages of using neural networks in lieu of an expectation maximization algorithm.

Recurrent neural networks (RNNs) are traditionally used for machine learning applications for temporal sequences such as natural language processing. Its application to image processing is relatively new. In this paper, we apply RNNs to denoise images corrupted by mixed Poisson and Gaussian noise. The motivation for using an RNN comes from viewing the denoising of the Poisson-Gaussian realization as a temporal process. The network then attempts to trace back the steps that create the noisy realization in order to arrive at the noiseless reconstruction. Numerical experiments demonstrate that our proposed RNN approach outperforms convolutional autoen-coder methods for denoising and upsampling low-resolution images from the CIFAR-10 dataset.

In this paper, we propose a novel machine learning technique to detect and correctly classify adversarially modified images. Our approach takes advantage of the adversarial training objective (to influence the prediction with small perturbations to the original image) by searching for large discrepancies in the model’s output relative to the input image. We find clusters in each space, and for an image whose clusters do not agree with each other, we flag the image as potentially adversarial and use the input space cluster’s prediction in place of the attacked model’s output. We have found that this method tends to find adversarial samples which are more likely to be misclassified by the attacked model, and that simply deferring to the input cluster’s prediction on such samples is enough to increase accuracy on adversarial data, even when the attacked model is adversarially trained.

Synthetic Reduced Nearest Neighbor (SRNN) is a Nearest Neighbor model which is constrained to have K synthetic samples (prototypes/centroids). There has been little attempt toward direct optimization and interpretability of SRNN with proper guarantees like convergence. To tackle these issues, this paper, inspired by K-means algorithm, provides a novel optimization of Synthetic Reduced Nearest Neighbor based on Expectation Maximization (EM-SRNN) that always converges while also monotonically decreases the objective function. The optimization consists of iterating over the centroids of the model and assignment of training samples to centroids. The EM-SRNN is interpretable since the centroids represent sub-clusters of the classes. Such type of interpretability is suitable for various studies such as image processing and epidemiological studies. In this paper, analytical aspects of problem are explored and linear complexity of optimization over the trainset is shown. Finally, EM-SRNN is shown to have superior or similar performance when compared with several other interpretable and similar state-of-the-art models such trees and kernel SVMs.

LoRa has recently become one of the most promising networking technologies for the Internet of Things applications. Distant end devices have to use a low data rate to reach a LoRa gateway, which can cause long in-the-air transmission time and high energy consumption. Compared with the end devices using high data rate, they will drain the batteries much earlier and the network may be broken. Such an energy unfairness can be mitigated by deploying more gateways, since it allows end devices to reach closer gateways with higher data rates. However, multiple gateways may not solve the energy unfairness problem efficiently due to the collision problem caused by the chirp spread spectrum modulation of LoRa networks. Spreading factors of LoRa links can determine both data rate and multiplexing of different transmissions. With more gateways, more end devices may choose low spreading factors and reach closer gateways, which increase the collision probability. In this paper, we propose a networking solution for LoRa networks named EF-LoRa that can achieve fair energy consumption among end devices by carefully allocating different network resources, including frequency channels, spreading factors and transmission power, to achieve fair energy consumption among end devices in LoRa networks. We develop a LoRa network model to study the energy consumption of all the end devices in a network by considering the unique features of LoRa networks, such as LoRaWAN MAC protocol, spreading factors, interference, and the capacity limitation of a LoRa gateway. We formulate the energy fairness problem as an optimization problem and finally propose a greedy resource allocation algorithm to achieve the max-min fairness of energy efficiency in the LoRa networks. Simulation results show that the proposed solution EF-LoRa can improve the energy fairness of legacy LoRa networks by 177.8%.

Enabling robots to act according to human preferences across diverse environments is a crucial task, extensively studied by both roboticists and machine learning researchers. To achieve it, human preferences are often encoded by a reward function which the robot optimizes for. This reward function is generally static in the sense that it does not vary with time or the interactions. Unfortunately, such static reward functions do not always adequately capture human preferences, especially, in non-stationary environments: Human preferences change in response to the emergent behaviors of the other agents in the environment. In this work, we propose learning reward dynamics that can adapt in non-stationary environments with several interacting agents. We define reward dynamics as a tuple of reward functions, one for each mode of interaction, and mode-utility functions governing transitions between the modes. Reward dynamics thereby encodes not only different human preferences but also how the preferences change. Our contribution is in the way we adapt preference-based learning into a hierarchical approach that aims at learning not only reward functions but also how they evolve based on interactions. We derive a probabilistic observation model of how people will respond to the hierarchical queries. Our algorithm leverages this model to actively select hierarchical queries that will maximize the volume removed from a continuous hypothesis space of reward dynamics. We empirically demonstrate reward dynamics can match human preferences accurately.

We propose adaptive online application runtime prediction methods to improve application latency in clouds. Scheduling algorithms are highly sensitive to the value of application runtime. %Currently available schedulers rely on inaccurate user predictions as well as inaccurate over the shelf forecasting tools. Predicting the application runtime values in the cloud is challenging because of highly dynamic nature of application runtime values, the requirement of real-time prediction and scarcity of training data. To provide an accurate and fast online prediction model, we first analyze available HPC traces and design hybrid models from adaptive online generative models known as State Space Models. We show how State Space Models are generalizations of widely used methods for application runtime prediction in HPC clusters including exponential smoothing and recursive least square. To overcome high variance of application runtimes in the cloud, our proposed methods facilitate on-the-fly automated model selection and model switching. Our machine learning prediction results on HPC application traces show that our adaptive online prediction models predict the runtimes 33% to 80% more accurately than existing prediction approaches. Besides, our extensive trace-based scheduling simulations show that our predicted runtimes improve the performance (wait time) by 25%.

We focus on learning the desired objective function for a robot. Although trajectory demonstrations can be very informative of the desired objective, they can also be difficult for users to provide. Answers to comparison queries, asking which of two trajectories is preferable, are much easier for users, and have emerged as an effective alternative. Unfortunately, comparisons are far less informative. We propose that there is much richer information that users can easily provide and that robots ought to leverage. We focus on augmenting comparisons with feature queries, and introduce a unified formalism for treating all answers as observations about the true desired reward. We derive an active query selection algorithm, and test these queries in simulation and on real users. We find that richer, feature-augmented queries can extract more information faster, leading to robots that better match user preferences in their behavior.

Deploying applications in containers has several advantages, such as rapid development, portability across different machines, and simplified maintenance. In a cloud computing environment, container scheduling algorithms coordinate with different aspects of physical systems, such as memory allocation for tasks of different users. The scheduled containers on a host may process sensitive data. For instance, containers may process healthcare information. In that case, diverse cloud environments with different components and subsystems may lead to a potential personal health information leakage and violation of data privacy. In this paper, we introduce a novel compliance-aware analysis model for provisioning containers in the cloud, that provides a HIPAA compliance model. The proposed method dynamically analyzes different requirements of HIPAA complaint containers (HIPAA parameters) and their associated risk values. Based on the risk optimization of the compliance parameters for data security and data privacy of the containers, our proposed method determines scheduling of containers that offer the lowest risk to healthcare data and to the compliance posture of the container. The model describes the resources that are associated with highlevel risks and provides real-time resource recommendation for a container scheduler to decrease the risk of HIPAA compliance violation.

Software Defined Networking (SDN) is increasingly being used in data centers as well as enterprise networks. In an environment that has strict compliance requirements, such as HIPAA compliance, a critical role for an SDN controller is to route all data packets while considering data privacy preservation and compliance-preservation. In this paper, we address this problem by proposing a routing protocol for SDN which is an efficient risk-based swarm routing protocol. The programmable capability of controllers is exploited in order to minimize privacy and compliance risks in data transmission. The proposed routing protocol is based on the Ant Colony Optimization technique and machine learning, while the data for learning is obtained from OVSDB and the OpenvSwitch Database management protocol. We collect a history of packet transfers for training purposes and learn from the training data to efficiently and intelligently route sensitive data packets while it preserves the target compliance. This routing is obtained by intelligent eviction of rules that are downloaded to the switches. We have implemented the proposed schemes based on an RYU controller.

With progress in enabling autonomous cars to drive safely on the road, it is time to start asking how they should be driving. A common answer is that they should be adopting their users' driving style. This makes the assumption that users want their autonomous cars to drive like they drive - aggressive drivers want aggressive cars, defensive drivers want defensive cars. In this paper, we put that assumption to the test. We find that users tend to prefer a significantly more defensive driving style than their own. Interestingly, they prefer the style they think is their own, even though their actual driving style tends to be more aggressive. We also find that preferences do depend on the specific driving scenario, opening the door for new ways of learning driving style preference.

Storage services are among the primary cloud computing offerings, providing advantages of scale, cost and availability to its customers. However, studies and past experiences show that large-scale storage service can be unreliable, and vulnerable to various internal and external threats that cause loss and/or corruption of customer data. In this work, we present a query authentication scheme for cloud-based storage system where the data is populated by multiple sources and retrieved by the clients. The system allows clients to verify the authenticity and integrity of the retrieved data in a scalable and efficient way, without requiring implicit trust on the storage service provider. The proposed mechanism is based on our recently proposed multi-trapdoor hash functions, using its properties to achieve near constant communication and computation overhead for authenticating query responses, regardless of the data size, or the number of sources. We develop a discrete log-based instantiation of the scheme and evaluate its security and performance. Our security analysis shows that forging the individual or aggregate authentication tags is infeasible under the discrete log assumption. Our performance evaluation demonstrates that the proposed scheme achieves superior efficiency and scalability compared to existing query authentication schemes offering support for multiple sources.

We consider the problem of scheduling jobs with varying demands on multiple servers. Each server has a certain computing capacity and can schedule multiple jobs simultaneously as long as the jobs' total demand does not exceed the server's capacity. This scenario arises commonly in virtualization, cloud computing, and MapReduce (or Hadoop). We study this problem with the requirement that jobs must be scheduled non-preemptively, meaning that every job must be completed without interruption once it gets started. Often, preemption is out of choice since preempting a job can be prohibitively costly or is not allowed due to system constraints. We focus on the popular objective of minimizing total completion time of jobs. This problem is NP hard hence we study heuristics with provable approximation guarantees. Succinctly, the interaction between two orthogonal quantities, jobs demands and sizes makes the scheduling decision significantly more challenging. In this paper we propose novel algorithms for scheduling jobs with non-uniform demands on multiple homogeneous servers without preemption. We first observe that the Smallest Volume First (SVF) algorithm that favors jobs with smaller volumes could perform very poorly in general. However, we show that SVF yields a nearly optimal schedule when the system is overloaded and jobs have demands considerably smaller than servers' capacities. This result supports the intuition that SVF should work well unless some jobs with high demands occupy the servers for long, blocking other jobs. Building on this intuition and using reduction to geometric packing problems, we develop algorithms that are constant approximation for all instances for the first time. Prior to our work, there was no theoretical study on this problem even for the single server case.

Cloud Computing technology offers new opportunities for outsourcing data, and outsourcing computation to individuals, start-up businesses, and corporations in health care. Although cloud computing paradigm provides interesting, and cost effective opportunities to the users, it is not mature, and using the cloud introduces new obstacles to users. For instance, vendor lock-in issue that causes a healthcare system rely on a cloud vendor infrastructure, and it does not allow the system to easily transit from one vendor to another. Cloud data privacy is another issue and data privacy could be violated due to outsourcing data to a cloud computing system, in particular for a healthcare system that archives and processes sensitive data. In this paper, we present a novel cloud computing platform based on a Service-Oriented cloud architecture. The proposed platform can be ran on the top of heterogeneous cloud computing systems that provides standard, dynamic and customizable services for eHealth systems. The proposed platform allows heterogeneous clouds provide a uniform service interface for eHealth systems that enable users to freely transfer their data and application from one vendor to another with minimal modifications. We implement the proposed platform for an eHealth system that maintains patients' data privacy in the cloud. We consider a data accessibility scenario with implementing two methods, AES and a light-weight data privacy method to protect patients' data privacy on the proposed platform. We assess the performance and the scalability of the implemented platform for a massive electronic medical record. The experimental results show that the proposed platform have not introduce additional overheads when we run data privacy protection methods on the proposed platform.

In mobile ad hoc and sensor networks, greedy-face-greedy (GFG) geographic routing protocols have been a topic of active research in recent years. Greedy routing is applied first and may fail at concave nodes, in which case, face routing is applied to recover from the greedy fail. This may cause extra hops in routing and decrease the routing efficiency in networks containing voids. In this paper, we propose a Hill-Area-Restricted (HAR) routing protocol. It avoids the extra hops as in the original GFG routing, which makes it more efficient in hop count. Compared with the previous work of Node Elevation Ad hoc Routing (NEAR), the proposed HAR guarantees the packet delivery and decreases the communication cost largely. Our simulation results show that the communication cost in bytes of all messages sent by each node in the proposed HAR is 99.2% less than that in NEAR. This makes the HAR more desirable for mobile ad hoc and sensor networks.

Digital streaming Internet applications such as online gaming, multimedia playback, presentations, news feeds, and stock quotes involve end-users with very low tolerance for high latency, low data rates, and playback interruption. To protect such delay-sensitive streams against malicious attacks, security mechanisms need to be designed to efficiently process long sequence of bits. We study the problem of efficient authentication for real-time and delay-sensitive streams commonly seen in content distribution, multicast, and peer-to-peer networks. We propose a novel signature amortization technique based on trapdoor hash functions for authenticating individual data blocks in a stream. Our technique provides: 1) Resilience against transmission losses of intermediate blocks in the stream; 2) Small and constant memory/compute requirements at the sender and receiver; 3) Minimal constant communication overhead needed for transmission of authenticating information. Our proposed technique renders authentication of digital streams practical and efficient. We substantiate this claim by constructing DL-SA, a discrete-log-based instantiation of the proposed technique. DL-SA provides adaptive stream verification, where the receiver has control over modulating computation cost versus buffer size. Our performance analysis demonstrates that DL-SA incurs the least per-block communication and signature generation overheads compared to existing schemes with comparable features.

Cloud computing is an emerging computing paradigm where computing resources are provided as services over Internet while residing in a large data center. Even though it enables us to dynamically provide servers with the ability to address a wide range of needs, this paradigm brings forth many new ch

Proxy signatures have found extensive use in authenticating agents acting on behalf of users in applications such as grid computing, communications systems, personal digital assistants, information management and e-commerce. Importance of proxy signatures has been repeatedly highlighted by applied cryptographers through different variations, namely threshold proxy signatures, blind proxy signatures and so forth. Unfortunately, most recent constructions of proxy signatures only improve on minor weaknesses of previously built schemes, and most often do not deliver formal security guarantees. In this study, the authors propose a technique to construct provably secure proxy signature schemes using trapdoor hash functions that can be used to authenticate and authorise agents acting on behalf of users in agent-based computing systems. They demonstrate the effectiveness of their approach for creating practical instances by constructing a discrete log-based instantiation of the proposed generic technique that achieves superior performance in terms of verification overhead and signature size compared with existing proxy signature schemes. Formal definitions, security specifications and a detailed theoretical analysis, including correctness, security and performance, of the proposed proxy signature scheme have been provided.

In mobile ad hoc and sensor networks, since all nodes are mobile and there is no fixed infrastructure, the design of routing protocols becomes one of the most challenging issues. In recent years, geographic routing protocols have been widely used. Most of them, e.g., greedy-face-greedy routing protocols, need nodes to construct planar graphs as the underlying graphs. In this paper, we propose an edge constrained localized Delaunay graph, denoted by ECLDel, as the underlying graph for geographic routing. We prove that the ECLDel is a planar t-spanner of the unit-disk graph. Geographic routing on ECLDel is as efficient as on the previous work of PLDel in terms of path length (hop count). However, the construction of ECLDel graph is far more simple and it converges faster. This is due to the following two reasons: First, we significantly reduce the number of messages broadcast by each node from five rounds (each round may contain several messages) to only two messages; second, we define two new types of edges, the intersecting Gabriel (IG) edges and the unaware intersection (UI) edges, which are constrained in the ECLDel graph. These edges help significantly reduce the size of messages broadcast by each node. The decrease of both the number and the size of messages broadcast by each node reduces the communication cost, and saves the network bandwidth and node power, which are desirable for mobile ad hoc and sensor networks. Our simulation results show that the average number of messages and the average size of messages broadcast by each node are, respectively, 65 and 42 percent less in the construction of ECLDel than that in PLDel.

Aggregate signatures can be a crucial building block for providing scalable authentication of a large number of users in several applications like building efficient certificate chains, authenticating distributed content management systems, and securing path vector routing protocols. Aggregate signatures aim to prevent resources (signature and storage elements, and computation) from growing linearly in the number of signers participating in a network protocol. In this paper, we present an efficient and scalable quasi-aggregate signature scheme, CLFSR, based on third-order linear feedback shift register (cubic LFSR) sequences that can be instantiated using both XTR and GH public key cryptosystems. In the proposed CLFSR construction, signers sign messages sequentially; however, the verfier need not know the order in which messages were signed. The proposed scheme offers constant length signatures, fast signing, aggregation, and verification operations at each node, and requires the least storage elements (public keys needed to verify the signature), compared to any other aggregate signature scheme. To the best of our knowledge, CLFSR is the first aggregate signature scheme to be constructed using LFSR sequences. We believe that the CLFSR signature scheme can be catalytic in improving the processing latency as well as reducing space requirements in building secure, large-scale distributed network protocols. We perform extensive theoretical analysis including correctness and security of CLFSR and also present a performance (computation and communication costs, storage overhead) comparison of the proposed scheme with well-known traditional constructions.

Abstract With sensor networks on the verge of deployment, security issues pertaining to the sensor networks are in the limelight. Though the security in sensor networks share many characteristics with wireless ad hoc networks, the two fields are rapidly diverging due to the fundamental differences between the make‐up and goals of the two types of networks. Perhaps the greatest dividing difference is the energy and computational abilities. Sensor nodes are typically smaller, less powerful, and more prone to failure than nodes in an ad hoc network. These differences indicate that protocols that are valid in the context of ad‐hoc networks may not be directly applicable for sensor networks. In this paper, we survey the state of art in securing wireless sensor networks. We review several protocols that provide security in sensor networks, with an emphasis on authentication, key management and distribution, secure routing, and methods for intrusion detection. Copyright © 2006 John Wiley & Sons, Ltd.

Traditionally, route discovery in MANETs operates in a source-initiated manner. This unilateral operation is unbalanced and inherently not ideal for MANETs. We propose a new scheme called bilateral route discovery (BRD), where both source and destination actively participate in a route discovery process. BRD has the potential to reduce the control overhead by one half. As an underlying protocol for BRD, we propose gratuitous route error reporting (GRER). GRER bypasses the failed link and notifies the destination of a broken route. The destination can thus play an active role in the upcoming route re-discovery. The results of an extensive simulation study confirm the effectiveness of the BRD approach.

In this paper, we propose an edge constrained localized Delaunay graph, ECLDel, as the underlying graph for geographic routing in mobile ad hoc networks. We prove that the ECLDel is a planar t-spanner of the original unit-disk graph. We give an algorithm to construct the ECLDel, which can be run by each node distributively with 1-hop neighborhood information. We define two new kinds of edges, the intersecting Gabriel (IG) edges and the unaware intersection (UI) edges, which are constrained in the ECLDel. This makes the construction of ECLDel more efficient and converges faster with less communication cost, compared to the previous work of constructing a planarized localized Delaunay graph, PLDel. The simulation results show that the average number of messages and the average size of messages (the number of neighbor nodes in the messages) broadcast by each node in construction of ECLDel is 65% and 42% less than that in construction of PLDel, respectively.

introduction Share on Introduction: Special issue of the IEEE SUTC'06 Editors: Jeffrey J. P. Tsai View Profile , Mukesh Singhal View Profile Authors Info & Claims ACM Transactions on Autonomous and Adaptive SystemsVolume 2Issue 3September 2007 pp 7–eshttps://doi.org/10.1145/1278460.1278461Online:01 September 2007Publication History 1citation385DownloadsMetricsTotal Citations1Total Downloads385Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present a lightweight hierarchical routing model, Way Point Routing (WPR), in which a number of intermediate nodes on a route are selected as waypoints and the route is divided into segments by the waypoints. Waypoints, including the source and the destination, run a high-level intersegment routing protocol, while the nodes on each segment run a low-level intrasegment routing protocol. One distinct advantage of our model is that when a node on the route moves out or fails, instead of discarding the whole original route and discovering a new route from the source to the destination, only the two waypoint nodes of the broken segment have to find a new segment. In addition, our model is lightweight because it maintains a hierarchy only for nodes on active routes. On the other hand, existing hierarchical routing protocols such as CGSR and ZRP maintain hierarchies for the entire network. We present an instantiation of WPR, where we use DSR as the intersegment routing protocol and AODV as the intrasegment routing protocol. This instantiation is termed DSR over AODV (DOA) routing protocol. Thus, DSR and AODV—two well-known on-demand routing protocols for MANETs—are combined into one hierarchical routing protocol and become two special cases of our protocol. Furthermore, we present two novel techniques for DOA: one is an efficient loop detection method and the other is a multitarget route discovery. Simulation results show that DOA scales well for large networks with more than 1,000 nodes, incurring about 60 percent-80 percent less overhead than AODV, while other metrics are better than or comparable to AODV and DSR.

Ad hoc networks, which do not rely on any infrastructure such as access points or base station, can be deployed rapidly and inexpensively even in situations with geographical or time constraints. So ad hoc networks have attractive applications in both military and disaster situations and also in commercial uses like sensor networks or conferencing. In ad hoc networks, each node acts both as a router and as a host. The topology of an ad hoc network may change dynamically, which makes it difficult to design an efficient routing protocol. Nowadays, more and more wireless devices are being used, which can form large ad hoc networks. It is important to design a scalable routing protocol for ad hoc networks. In this paper, we propose anchor-based routing protocol with cell ID management system (ARPC), a scalable routing protocol for ad hoc networks. ARPC is a hybrid routing protocol, which combines the advantages of table-based routing strategy and geographic routing strategy, and avoids the burden-GPS (Global Positioning System) (E. D. Kaplan, 1996) support. Simulation results show that ARPC is efficient and scales well to large networks. Especially for large networks (1000 and 1600 nodes), ARPC achieves 21 percent higher packet delivery ratio than AODV, and has 19 percent lower overhead. This denotes that ARPC has better scalability than AODV.

On-demand routing protocols are preferred in mobile ad hoc networks where resources such as energy and bandwidth are constrained. In these protocols, a source discovers a route to a destination typically by flooding the entire or a part of the network with a route request (RREQ) message. The destination sends a route reply (RREP) message to the source after receiving the RREQ. The RREP travels hop by hop on the discovered route in reverse direction or on another route to the source. Sometimes the RREP can not be sent to the intended next hop by an intermediate node due to the dynamic network topology or network congestion. Existing on-demand routing protocols handle the undeliverable RREP as a normal data packet - discard the packet and send a route error message to the destination (initiator of the RREP). This is highly unacceptable because a RREP message has a lot at stake - it is obtained by a large number of RREQ transmissions, which is an expensive and time-consuming process. Furthermore, the source may have to start another round of route discovery to establish the route because of the loss of the RREP. This will exacerbate the situation. In this paper, we propose the idea of salvaging route reply (SRR) to improve the performance of on-demand routing protocols. SRR attempts to salvage an undeliverable RREP in two possible ways: looking up the route cache for an alternate path and conducting a one-hop SRR route discovery. We present an implementation of SRR in AODV routing protocol. The results of an extensive simulation study confirm the performance improvement in all critical metrics, namely, packet delivery ratio, control overhead and end-to-end delay.

In mobile ad hoc networks (MANETs), nodes depend on each other for routing and forwarding packets. Cooperation among nodes is a key issue in such an environment. However, some of the nodes in MANETs may behave selfishly and may not forward packets to save battery and other resources. Since nodes in MANETs communicate on a peer-to-peer basis without any central authority (which can monitor selfish behavior of nodes), a centralized solution to stimulate cooperation is not suitable. In this paper, we present a fully distributed solution to force nodes' cooperation. The solution is light-weight in that neighbor monitoring is on-demand, and nodes work in promiscuous mode only part time to save battery. Besides, we provide fairness to nodes in the network by considering their battery status. We incorporate our light-weight solution for selfish node problems considering battery status in AODV. To evaluate the performance of our scheme, we conducted simulation using Glomosim. Simulation results show that the proposed scheme improves data forwarding capability substantially in presence of selfish nodes, identifies the selfish nodes accurately and has low overhead.

The hello protocol (Moy, J., 1994) is a fundamental protocol for wired and wireless networks. In mobile ad-hoc networks, a hello protocol helps nodes to establish a neighbor table for link detection. If nodes exchange position information in hello packets, then it also helps them in packet forwarding decisions. In ad-hoc networks, due to node mobility, neighbor relationships change frequently. To cope with mobility, and to have an up-to-date neighbor table, nodes advertise hello packets periodically. These hello packets create congestion, which may cause control and data packets to be dropped in the network. We study the impact of hello protocols on ad-hoc networks. We present three new hello protocols which reduce network congestion. The main idea behind all three protocols is to beacon as little as possible without compromising the accuracy of the neighbor table. To evaluate the performance of our protocols and their impact on ad-hoc networks, we simulated them in GloMoSim 2.03. Our results show that the proposed hello protocols incur much lower overhead and increase the network performance compared to a periodic hello protocol, while maintaining identical neighbor table accuracy.

In cellular networks, it is vital to allocate communication channels efficiently because the bandwidth allocated for cellular communication is limited. If channels are statically allocated, as is the case in current cellular networks, a cell may run out of channels when a large number of mobile hosts move to the cell. To overcome this problem, dynamic channel allocation approaches have been proposed. Under dynamic channel allocation, channels are allocated to cells on demand, thus increasing channel utilization. Such channel allocation approaches fall under two categories, namely, centralized and distributed. Centralized approaches are neither scalable nor reliable, while distributed approaches have the potential to be both reliable and scalable. In the distributed approaches, a mobile service station is responsible for allocating channels to mobile hosts in the same cell. In cellular networks, mobile service stations may fail. In addition, the network may encounter intermittent network congestion and/or link failures. It is desirable for a channel allocation algorithm to work well, even in the presence of network congestion, link failures, and/or mobile service station failures. In this paper, we present a distributed dynamic channel allocation scheme for cellular networks that is fault-tolerant. Our approach can tolerate the failure of mobile service stations, link failure, and network congestion, and make efficient reuse of channels. We also provide results of the performance evaluation of our algorithm.

Bluetooth ad hoc networks are constrained by a master/slave configuration, in which one device takes the role of master and controls the communication with the slave devices. Piconets are small Bluetooth networks containing one master and up to seven active slave devices. In order to build larger topologies, called scatternets, the piconets must be interconnected. Scatternets are formed by allowing certain piconet members to participate in several piconets by periodically switching between them. Due to the fact that there is no scatternet formation procedure in the Bluetooth specification, numerous different approaches have been proposed. We discuss criteria for different types of scatternets and establish general models of scatternet topologies. Then we describe the state-of-the-art for Bluetooth scatternets and compare and contrast the approaches.

Ad-hoc on-demand routing protocols like AODV establish and maintain routes on-demand. However, the paths established by on-demand protocols, which are optimal during the route establishment phase, become sub-optimal over time due to node mobility. We propose a path compression algorithm (PCA) that optimizes the established routes when feasible without incurring extra overhead. By utilizing a promiscuous mode of operation, nodes 'hear' hop counts embedded in the IP optional header of data packets to find shorter paths. PCA avoids unnecessary aggressive and ephemeral route updates, which improves the protocol performance. Routing path optimality is important as the optimal path reduces the packet drop ratio, the end-to-end delay, and the energy dissipation of end-to-end data transmission. We conducted simulations using GloMoSim to evaluate the performance of our algorithm and compared it with AODV and a related protocol in the literature - SHORT. Our simulation results show that PCA achieves high delivery rate, low control overhead, low end-to-end delivery and low average hop count compared to both AODV and SHORT.

The peer-to-peer (P2P) network model differs from the well established client-server model in that all members of the network are assigned an equal role. P2P networks are recently gaining increasing popularity. Providing security in distributed content sharing in P2P networks is an important challenge. This paper identifies security vulnerabilities in the protocols for sharing servants' reputations in the Gnutella P2P system, proposed recently. It demonstrates attacks on the protocols that allow an attacker to alter the results of the voting procedure. The paper then presents a protocol that is resilient to the attacks described. In the proposed protocol, enhanced security against various attacks is achieved using smart design and a combination of various techniques such as the use of digital signatures for message integrity and random numbers for message freshness.

This paper discusses the financial benefit of intrusion detection systems (IDS) deployment techniques and addresses the problems of bridging the gap between technical security solutions and the business need for it. This is an area of interest to both the research and the business community; most IDSes balance host and network monitoring, but the decision about how to adjust usage of each technique tends to be made in a rather ad-hoc way, or based upon effectiveness of detection only without regard to cost of technique. In practice, selections based on how well a strategy helps a company to perform are preferable and methodologies supporting a selection process of this type will assist an Information Technology officer to explain security mechanism selections more effectively to CEOs. In this context, the approach we propose could be applied when choosing one intrusion detection system over another based on which has a better or higher return on investment for the company. Through a case study, we illustrate the benefits of a better IDS management that leads to a positive Return on Investment (ROI) for IDS deployment. We conceive strategies and approaches to support effective decision-making about which techniques are appropriate for the cost effective management of the IDS in a given environment. It is our intent that this research will serve as a foundation for the formal description of cost structures, analysis, and selection of effective implementation approaches to support the management of IDS deployments.

Intrusion detection systems' (IDS) effectiveness requires balancing characteristics and elements so they fit together in appropriate compromises to create good network security systems. One major gauge for IDS effectiveness is the ability to detect attacks within operational specifications. Gigabit IDS sensors as opposed to Megabit IDS sensors promise dramatic increase in component performance and functional opportunities, possibly leading to dramatically changed system balance and overall performance. The research described here examines the system benefits of using a single Gigabit IDS sensor instead of multiple Megabit sensors for a wide range of defined system attacks, network traffic characteristics, and for their contexts of operational concepts and deployment techniques. The experimental results are analyzed in the context of practical experiences in the operation of these IDS systems. The difference in architectural designs, deployment strategies and operational concepts that characterized their performance in exploiting the strengths of attack systems are discussed.

Knot detection in a distributed graph is an important problem and finds applications in deadlock detection in several areas such as store-and-forward networks, distributed simulation, and distributed database systems. This paper presents an efficient distributed algorithm to detect if a node is part of a knot in a distributed graph. The algorithm requires 2e messages and a delay of 2(d+1) message hops to detect if a node in a distributed graph is in a knot (here, e is the number of edges in the reachable part of the distributed graph and d is its diameter). A significant advantage of this algorithm is that it not only detects if a node is involved in a knot, but also finds exactly which nodes are involved in the knot. Moreover, if the node is not involved in a knot, but is only involved in a cycle, then it finds the nodes that are in a cycle with that node. We illustrate the working of the algorithm with examples. The paper ends with a discussion on how the information about the nodes involved in the knot can be used for deadlock resolution and also on the performance of the algorithm.

A reliable multicast algorithm, called RMA, for mobile ad hoc networks is presented that is based on a new cost criterion, called link lifetime, for determining the optimal path between a pair of nodes. The algorithm has the characteristics of using an undirected graph for its routing operations rather than a fixed structure like a tree or a mesh. Previously proposed routing metrics for mobile ad hoc networks were designed for use in wired environments, where link stability is not a concern. We propose a new metric, called the lifetime, which is more appropriate for mobile ad hoc networks. The lifetime metric is dependent on the predicted future life of the link under consideration. We developed a simulator for the mobile ad hoc networks, which is portable and scalable to a large number of nodes. Using the simulator, we carried out a simulation study to analyze the effectiveness of the routing metrics and the performance of the proposed reliable multicast algorithm. The simulation results show that the lifetime metric helps achieve better performance in mobile ad hoc environments than the hop count metric.

Knot detection in a distributed graph is an important problem and finds applications in several areas such as packet switching, distributed simulation, and distributed database systems. The paper presents a distributed algorithm to efficiently detect the existence of a knot in a distributed graph. The algorithm requires 2e messages and a delay or 2(d+1) message hops to detect if a node in a distributed graph is in a knot (e is the number of edges in the reachable part of the distributed graph and d is its diameter). A significant advantage of this algorithm is that it not only detects if a node is in a knot but also finds exactly which nodes are involved in the knot.

Provision of QoS-related router functions such as traffic regulation, policy routing, and usage-based accounting requires that a flow table store state information for active flows. The design of such a flow table is not trivial for a high-speed Internet router (e.g., 100+ Gbps) with a large number of active flows (e.g., tens of millions) and a high packet arrival rate (e.g., tens of millions of packets per second). Targeting two different models (centralized and distributed) of router design, we propose a software-based design to be implemented on individual line cards, which is suitable for the distributed model, and a hardware-based design to be implemented in the main forwarding engine of a router, which is suitable for the centralized model. The software-based design, adapted from the hash table data structure, employs a practical and effective technique to solve the garbage collection problem caused by the expired flows. The hardware-based design, adapted from the architecture of an N-way set-associative cache, employs a novel dynamic set-associative scheme to reduce the overflow ratio that a traditional set-associative scheme incurs, by a high percentage, and a pipelined design to achieve a throughput of 100+ Gbps. The performance evaluation results from both trace-driven simulation and statistical analysis demonstrate that both designs are cost-effective for their targeted router models.

A high-confidence system is one in which the designers, implementers, and users have a high degree of assurance that the system will not fail or misbehave due to errors in the system, faults in the environment, or hostile attempts to compromise the system. Consequences of such system behavior are well understood and are predictable under an operational context envisioned by its creators. High-confidence systems (HCS) are highly secure and robust: they can withstand various threats, malicious attacks, and hardware/software component failures. Correctness, predictability, reliability, availability, security, and survivability are the key properties that constitute the basis of high confidence. We expect to have confidence in networked embedded software applications in our homes, workplaces, and vehicles. We need to understand well the implications of software design and structuring for vulnerability in these systems to failures, extreme environmental events, and security attacks. This will require both fundamental and empirical research to establish, test, validate, and improve secure networked and software-enabled system construction principles.

Mobile computing raises many new issues such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. Coordinated checkpointing is an attractive approach for transparently adding fault tolerance to distributed applications since it avoids domino effects and minimizes the stable storage requirement. However, it suffers from high overhead associated with the checkpointing process in mobile computing systems. Two approaches have been used to reduce the overhead: First is to minimize the number of synchronization messages and the number of checkpoints; the other is to make the checkpointing process nonblocking. These two approaches were orthogonal previously until the Prakash-Singhal algorithm combined them. However, we found that this algorithm may result in an inconsistency in some situations and we proved that there does not exist a nonblocking algorithm which forces only a minimum number of processes to take their checkpoints. In this paper; we introduce the concept of "mutable checkpoint," which is neither a tentative checkpoint nor a permanent checkpoint, to design efficient checkpointing algorithms for mobile computing systems. Mutable checkpoints can be saved anywhere, e.g., the main memory or local disk of MHs. In this way, taking a mutable checkpoint avoids the overhead of transferring large amounts of data to the stable storage at MSSs over the wireless network. We present techniques to minimize the number of mutable checkpoints. Simulation results show that the overhead of taking mutable checkpoints is negligible. Based on mutable checkpoints, our nonblocking algorithm avoids the avalanche effect and forces only a minimum number of processes to take their checkpoints on the stable storage.

The performance of a mutual exclusion algorithm is measured by the number of messages exchanged per critical section execution and the delay between successive executions of the critical section. There is a message complexity and synchronization delay trade-off in mutual exclusion algorithms. The Lamport algorithm (1978) and the Ricart-Agrawal algorithm (1981) both have a synchronization delay of T (T is the average message delay), but their message complexity is O(N). Maekawa's algorithm reduces the message complexity to O(/spl radic/N); however, it increases the synchronization delay to 2T. After Maekawa's algorithm (1985), many quorum-based mutual exclusion algorithms have been proposed to reduce the message complexity or the increase the resiliency to site and communication link failures. Since these algorithms are Maekawa-type algorithms, they also suffer from the long synchronization delay. We propose a delay-optimal quorum-based mutual exclusion algorithm which reduces the synchronization delay to T and still has a low message complexity of O(K) (K is the size of the quorum which can be as low as log N). A correctness proof and a detailed performance analysis are provided.

Summary form only given. High-speed networks are becoming popular for accessing remote data and information sharing and more and more organizations are connecting through networks to obtain financial and strategic advantages. However, this high-bandwidth connectivity also exposes them to a higher degree of security attacks and intrusions. A router-based packet-filtering firewall is an effective way to protect an enterprise network from unauthorized accesses. However, traditional firewalls will not work efficiently in ATM networks because they require termination of end-to-end connections at the packet-filtering router for packet inspection. This is likely to incur a high overhead due to packet segmentation and reassembly making it a serious bottleneck. This talk presents the design of a high-speed ATM firewall that does not require the termination of an end-to-end connection in the middle. This firewall switch nicely integrates the IP level security mechanisms into the hardware components of an ATM switch so that most of the filtering operations are performed in parallel with the normal cell processing and most of its cost is absorbed into the base cost of the switch. The firewall switch employs "last cell hostage" (LCH) to avoid or reduce the latency caused by filtering. We analyze in detail the performance of the firewall switch in terms of the throughput and latency.

Existing and emerging layer-4 switching technologies require packet classification to be performed on more than one header field, known as layer-4 lookup. Currently, the fastest general layer-8 lookup scheme delivers a throughput of 1 million lookups per second (MLPS), far off from 25/75 MLPS needed to support 50/150 Gbps layer-4 router. We propose the use of route caching to speed up layer-4 lookup, and design and implement a cache architecture for this purpose. We investigated the locality behavior of the Interent traffic (at layer-4) and propose a near-LRU algorithm that can best harness this behavior. In implementation, to best approximate fully-associative near-LRU using relatively inexpensive set-associative hardware, we invented a dynamic set-associative scheme that exploits the nice properties of N-universal hash functions. The cache architecture achieves a high and stable hit ratio above 90 percent and a fast throughput up to 75 MLPS at a reasonable cost.

In a data warehouse, data cubes are accessed through their dimensions. If dimensions are numerical, because numerical data can be clustered or sorted, fast access methods such as binary search or B+ trees can be applied. However, complex attributes such as keyword sets of document contents are not easily sorted or clustered. Although it is highly desirable that documents can be searched through their sets of keywords.

The efficient transmission of constant quality compressed video streams is complicated by the burstiness (both short term and long term) that video compression standards such as MPEG introduce. Most of the techniques in the literature are concentrated on stored video traffic smoothing or real-time video traffic smoothing. However there is a growing number of live video applications, such as videocasts of courses or television news, where many clients may be willing to tolerate a playback delay of several seconds or minutes in exchange for a smaller throughput requirement. Bandwidth smoothing for these live video applications is referred to as online smoothing. In order to measure the effectiveness of online video smoothing methods, in this paper, we first propose a benchmark algorithm which provides the upper bound on some of the smoothness parameters in the smoothing results. Based on this algorithm, we found that significant discrepancy exists between the results produced by the existing online smoothing methods and the upper bound. With this observation, we then focus on devising algorithms which improve the smoothing results.

Complex queries with multiple conjunctive (AND) predicates have attracted increasing attention for their importance in OLAP systems. The signature index is ideal for the fast execution of queries involving multiple conjunctive predicates. However, previous signature-based methods did not separate the signatures from different attributes. We have developed a signature-augmented access index, called an MG-tree. Its main features are: (1) it is a lightweight search tree for indexing multiple attributes of text data, and (2) it eliminates the mix of signatures from different attributes, so the construction and maintenance of the index is easy and searching is efficient. Our analyses and experiments show that the MG-tree achieved a significant improvement in terms of access speed and storage space overhead over both tree-like indexes and previous multi-dimensional signature indexes, and is easier to build and maintain. The MG-tree can be employed in practical DBMS implementations.

Distributed channel allocation algorithms have received considerable attention due to their high reliability, and scalability. However, in these algorithms, a borrower needs to consult with its interference neighbors in order to borrow a channel. Thus, a borrower fails to borrow channels when it cannot communicate with anyone of its interference neighbors. In real-life networks, under heavy traffic load, a cell has a large probability to experience an intermittent network congestion or even a communication link failure. In these algorithms, since a cell has to consult with a large number of interference neighbors to borrow a channel. The failure rate will be much higher under heavy traffic load. In this paper, we first propose a fault-tolerant channel acquisition algorithm which tolerates communication link failures and node (MH or MSS) failures. Then, we present a channel selection algorithm and integrate it into the distributed acquisition algorithm. Simulation results show that our algorithm significantly reduces the failure rate under network congestion, communication link failures, and node failures compared to non-fault-tolerant channel allocation algorithms.

There are two approaches to design a distributed channel allocation algorithm: Search and Update. The update approach has shorter acquisition delay and lower call blocking rate, but higher message complexity. On the other hand, the search approach has lower message complexity, but longer acquisition delay and higher call blocking rate. In this paper, we propose a novel distributed acquisition algorithm, which has similar message complexity as the search approach and similar acquisition delay as the update approach. Also, we propose a channel selection algorithm, which has low call blocking rate and low intra-handoff overhead. By integrating the channel selection algorithm into our channel acquisition algorithm, we get a complete distributed channel allocation algorithm. By keeping the borrowed channels, our channel allocation algorithm adapts to the network traffic; i.e., free channels are transferred to hot cells to achieve load balance. Simulation results show that our algorithm significantly outperforms the search approach and the update approach in terms of call blocking rate, message complexity, and acquisition delay.

No abstract available.

No abstract available.

No abstract available.

A well-known security problem with MPOA is that cut-through connections generally bypasses firewall routers if there are any. None of the previously proposed approaches solved the problem properly. In this paper, we propose a novel firewalling scheme for MPOA that nicely fixes the security hole. Our firewalling scheme has three outstanding advantages that make it ideal for securing MPOA-based enterprise networks. First, based on our novel concept of "logical chokepoints", our firewalling scheme does not require the existence of physical chokepoints inside the network. Second, the scheme is nicely embedded into the MPOA protocol so that its cost, performance overhead, and protocol complexity are reduced to a minimum. Third, the scheme is centrally administered so that it scales well to very large networks.

We present the design of a value-added ATM switch that is capable of performing packet-level (IP) filtering at the maximum throughput of 2.88 Gbit/s per port. This firewall switch nicely integrates the IP level security mechanisms into the hardware components of an ATM switch so that most of the filtering operations are performed in parallel with the normal cell processing, and most of its cost is absorbed into the base cost of the switch. The firewall switch employs the concept of "last cell hostage" (LCH) to avoid or reduce the latency caused by filtering. We analyze in detail the performance of the firewall switch in terms of the throughput and the latency and address related design issues. Applications of our firewall switch as Internet and intranet security solutions are also discussed.

A router-based packet-filtering firewall is an effective way of protecting an enterprise network from unauthorized access. However, it will not work efficiently in an ATM network because it requires the termination of end-to-end ATM connections at a packet-filtering router, which incurs huge overhead of SAR (Segmentation and Reassembly). Very few approaches to this problem have been proposed in the literature, and none is completely satisfactory. In this paper we present the hardware design of a high-speed ATM firewall that does not require the termination of an end-to-end connection in the middle. We propose a novel firewall design philosophy, called Quality of Firewalling (QoF), that applies security measures of different strength to traffic with different risk levels and show how it can be implemented in our firewall. Compared with the traditional firewalls, this ATM firewall performs exactly the same packet-level filtering without compromising the performance and has the same "look and feel" by sitting at the chokepoint between the trusted ATM LAN and untrusted ATM WAN. It is also easy to manage and flexible to use.

Replicated databases that use quorum-consensus algorithms to perform majority voting are prone to deadlocks. Due to the P-out-of-Q nature of quorum requests, deadlocks that arise are generalized deadlocks and are hard to detect. We present an efficient distributed algorithm to detect generalized deadlocks in replicated databases. The algorithm performs reduction of a distributed wait-for-graph (WFG) to determine the existence of a deadlock. If sufficient information to decide the reducibility of a node is not available at that node, the algorithm attempts reduction later in a lazy manner. We prove the correctness of the algorithm. The algorithm has a message complexity of 2e messages and a worst-case time complexity of 2d+2 hops, where e is the number of edges and d is the diameter of the WFG. The algorithm is shown to perform significantly better in both time and message complexity than the best known existing algorithms. We conjecture that this is an optimal algorithm, in time and message complexity, to detect generalized deadlocks if no transaction has complete knowledge of the topology of the WFG or the system and the deadlock detection is to be carried out in a distributed manner.

Checkpointing algorithms are classified as synchronous and asynchronous in the literature. In synchronous checkpointing, processes synchronize their checkpointing activities so that a globally consistent set of checkpoints is always maintained in the system. Synchronizing checkpointing activity involves message overhead and process execution may have to be suspended during the checkpointing coordination, resulting in performance degradation. In asynchronous checkpointing, processes take checkpoints without any coordination with others. Asynchronous checkpointing provides maximum autonomy for processes to take checkpoints; however, some of the checkpoints taken may not lie on any consistent global checkpoint, thus making the checkpointing efforts useless. Asynchronous checkpointing algorithms in the literature can reduce the number of useless checkpoints by making processes take communication induced checkpoints besides asynchronous checkpoints. We call such algorithms quasi-synchronous. In this paper, we present a theoretical framework for characterizing and classifying such algorithms. The theory not only helps to classify and characterize the quasi-synchronous checkpointing algorithms, but also helps to analyze the properties and limitations of the algorithms belonging to each class. It also provides guidelines for designing and evaluating such algorithms.

this paper we present the hardware design of a high-speed ATM firewall that does not require the termination of an end-to-end connection in the middle. We propose a novel firewall design philosophy, called Quality of Firewalling (QoF), that applies security measures of different strength to traffic with different risk levels and show how it can be implemented in our firewall. Compared with the traditional firewalls, this ATM firewall performs exactly the same packet-level filtering without compromising the performance and has the same "look and feel" by sitting at the chokepoint between the trusted ATM LAN and untrusted ATM WAN. It is also easy to manage and flexible to use.

There are two approaches to design a distributed channel allocation algorithms: search and update. The update approach has shorter acquisition delay and lower call blocking rate, but higher message complexity. On the other hand, the search approach has lower message complexity, but longer acquisition delay and higher call blocking rate. In this paper we first propose a novel distributed acquisition algorithm, which has similar message complexity as the search approach and similar acquisition delay as the update approach. Then, we present a channel selection algorithm and integrate it into our distributed acquisition algorithm. By a rigorous analysis in terms of delay and message complexity, we show that our channel acquisition algorithm performs significantly better than the update approach (Dong and Lai 1997) and the search approach (Prakash et al. 1995). Detailed simulation experiments are carried out in order to evaluate our proposed methodology. The performance of our algorithm is compared with those of the geometric strategy (Baiocchi et al. 1995), the search approach, and the update approach. Simulation results show that our algorithm outperforms all other approaches in terms of call blocking probability under uniform as well as non-uniform traffic.

Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. We introduce the concept of mutable checkpoint, which is neither a tentative checkpoint nor a permanent checkpoint. Mutable checkpoints can be saved anywhere; e.g., the memory or local disk of MHs. In this way, taking a mutable checkpoint avoids the overhead of transferring a large amount of data to the stable storage in MSS over the wireless network. Based on mutable checkpoints, our non-blocking algorithm avoids the avalanche effect, minimizes the number of synchronization messages and forces only a minimum number of processes to take their checkpoints on the stable storage.

The performance of a mutual exclusion algorithm is measured by the number of messages exchanged per critical section execution and the delay between successive executions of the critical section. There is a message complexity and synchronization delay trade-off in mutual exclusion algorithms. Lamport's (1978) algorithm and Ricart and Agrawal's (1981) algorithm both have a synchronization delay of T, but their message complexity is O(N). Maekawa's (1985) algorithm reduces message complexity to O(/spl radic/N); however, it increases the synchronization delay to 2T. After Maekawa's algorithm, many quorum-based mutual exclusion algorithms have been proposed to reduce message complexity or increase the resiliency to site and communication link failures. Since these algorithms are Maekawa-type algorithms, they also suffer from long synchronization delay 2T. We propose a delay-optimal quorum-based mutual exclusion algorithm which reduces the synchronization delay to T and still has the low message complexity O(K) (K is the size of the quorum, which can be as low as log N). A correctness proof and detailed performance analysis are provided.

Authenticated signaling is an important security service to be provided by ATM networks to guard against threats of spoofing and impersonation. The ATM Forum specifies public key cryptography to be the default ATM authentication mechanism and directory services like X.509 to be the infrastructure for public key distribution and certification. With public key cryptography, authenticated signaling requires the signaling message to be authenticated with a digital signature signed by the private key of the calling party. To verify the digital signature, the called party needs to obtain the public key of the calling party and a proof of the calling party's ownership to that public key. In X.509, the standard form of such a proof is a chain of public key certificates, called the certificate path between two parties. The certificate exchange protocol (CEP), proposed by the ATM Forum, requires that another bi-directional connection be established between two parties to change public keys and certificate paths before an authenticated connection can be established, which is not an ideal approach. We propose a certificate path generating protocol (CPGP), which is embedded into ATM signaling and routing protocols to generate a certificate path inside a signaling message on-the-fly as the signaling message travels through the ATM network. In CPGP all that a calling party needs to do for authenticated signaling is to put into the signaling message its own public key certificate and the digital signature of the signaling message signed using its private key. The CPGP builds the rest of the certificate path for it. The proposed protocol is embedded into the ATM signaling and routing protocol so that no performance overhead is incurred to establish the certificate path.

Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. R. Prakash and M. Singhal (1996) proposed the first coordinated checkpointing algorithm for mobile computing systems. However we showed that their algorithm may result in an inconsistency. In this paper, we prove a more general result about coordinated checkpointing: there does not exist a non-blocking algorithm that forces only a minimum number of processes to take their checkpoints. Based on the proof, we propose an efficient algorithm for mobile computing systems, which forces only a minimum number of processes to take checkpoints and dramatically reduces the blocking time during the checkpointing process. Correctness proofs and performance analysis of the algorithm are provided.

This paper presents an algorithm for optimizing the route of a connection that becomes suboptimal due to operations such as handoffs and location-based reroutes, and applies this algorithm to the handoff management problem in networks with hierarchical link state routing protocols such as PNNI (Private Network-to-Network Interface)-based ATM (Asynchronous Transfer Mode) networks. The route optimization algorithm uses hierarchical route information of the connection and summarized topology and loading information of the network to determine a "crossover node" such that adjusting the connection from that crossover node results in an optimally routed connection. Handoff management schemes that perform local rerouting of connections have been proposed in order to support fast handoffs. These methods result in suboptimally routed connections. In this paper, we demonstrate how this route optimization algorithm can be used to optimize the route of a connection after such a handoff is executed, as the second phase of two-phase handoff scheme. This route optimization procedure can also be executed as part of the handoff procedure resulting in a one-phase handoff scheme. Applying this route optimization algorithm, we propose two one-phase schemes, the one-phase optimal scheme and the one-phase minimal scheme. A comparative performance analysis of one- and two-phase handoff schemes is presented. Measures of comparison are handoff latency and the amount of network resources used by a connection. Handoff latency in the one-phase optimal scheme is greater than that in the two-phase schemes, and handoff latency in the one-phase minimal scheme is smaller than that in the two-phase schemes. The one-phase methods show a significant increase in efficiency of the connection compared to the two-phase methods.

In this paper, we propose an algorithm for optimizing the route of a connection that becomes suboptimal due to operations such as handoffs and location-based reroutes, for mobile ATM (asynchronous transfer mode) networks based on the PNNI (private network-to-network interface) standard. This algorithm uses hierarchical route information of the connection and summarized topology and loading information of the network to determine a "crossover node" such that adjusting the connection from that crossover node results in an optimally routed connection. We then apply this algorithm to the mobile location management problem. Location management schemes have been proposed in which an incoming call to a mobile is first routed to its home switch (based on summarized reachability data) and then rerouted to the mobile's current location. If we consider such rerouting a "first phase" of mobile connection setup, a "second phase" is required to optimize the paths of such rerouted connections. Such an approach is considered a two-phase mobile location/connection setup scheme. Alternatively, an incoming call to a mobile can be first routed to its home switch based on summarized reachability data, and then "cranked back" to an optimal crossover node before rerouting the connection to the mobile's current location. Such a scheme is a one-phase mobile location/connection setup scheme since it directly results in an optimal path. A comparative performance analysis of the one- and two-phase connection setup schemes is presented. Measures of comparison are call setup delay and the amount of network resources allocated to a connection. The maximum call setup delay (worst case call setup delay) is lower in the two-phase scheme, but the average call setup delay is lower in the one-phase scheme. The amount of resources required for a connection in the two-phase scheme (prior to route optimization) is significantly greater than that in the one-phase scheme.

Coordinated checkpointing simplifies failure recovery and eliminates domino effects in case of failures by preserving a consistent global checkpoint on stable storage. However, the approach suffers from high overhead associated with the checkpointing process. Two approaches are used to reduce the overhead: first is to minimize the number of synchronization messages and the number of checkpoints, the other is to make the checkpointing process nonblocking. These two approaches were orthogonal in previous years until the Prakash-Singhal algorithm combined them. In other words, the Prakash-Singhal algorithm forces only a minimum number of processes to take checkpoints and it does not block the underlying computation. However, we found two problems in this algorithm. In this paper, we identify these problems and prove a more general result: there does not exist a nonblocking algorithm that forces only a minimum number of processes to take their checkpoints. Based on this general result, we propose an efficient algorithm that neither forces all processes to take checkpoints nor blocks the underlying computation during checkpointing. Also, we point out future research directions in designing coordinated checkpointing algorithms for distributed computing systems.

Global predicate detection is a fundamental problem in distributed systems and finds applications in many domains such as testing and debugging distributed programs. This paper presents an efficient distributed algorithm to detect conjunctive-form global predicates in distributed systems. The algorithm detects the first consistent global state that satisfies the predicate even if the predicate is unstable. Unlike previously proposed run-time predicate detection algorithms, our algorithm does not require the exchange of control messages during the normal computation. All the necessary information to detect predicates is piggybacked on computation messages of application programs. The algorithm is distributed because the predicate detection efforts as well as the necessary information are equally distributed among the processes. We prove the correctness of the algorithm and compare its performance with respect to message, storage and computational complexities with that of the previously proposed run-time predicate detection algorithms.

Multimedia applications require support from the underlying broadband network at the end-to-end communication level. Multicasting is an important paradigm of end-to-end communication. The root node of a multicasting session is responsible for controlling the session including monitoring, maintenance, and the implementation of the multicasting protocol. The job that controls the multicasting session executes as a group of tasks at the root node of a multicasting tree. The scheduling scheme at the root node should give support to a multicasting session by improving the completion time of the jobs controlling the multicasting session, hence increasing throughput and the probability of admitting new multicast sessions. We model the tasks that carry out the multicasting session monitoring and maintenance as a fork-join job executing on a multiprocessor system. We assume that an executing task blocks for device I/O as a part of the activities associated with sending and receiving data packets. We develop two analytic models for scheduling a session control job on a multiprocessor system. The first allows incoming job tasks to multiplex processors with existing tasks of another multicasting session; the other model schedules a task of the incoming job to an idle processor. We assume that the overhead of rescheduling a task to another processor is large. We compare the performance of both models and show the range of conditions under which a model outperforms the other. The results can be used in the design of an adaptive scheduler that uses both models to improve throughput and the probability of admitting new multicast sessions.

Fast and efficient detection of deadlocks remains an important problem in distributed operating systems. We present a distributed algorithm to detect generalized deadlocks in distributed systems. The algorithm performs reduction of a distributed wait-for-graph (WFG) to determine a deadlock. If sufficient information to decide the reducibility of a node is not available at that node, the algorithm attempts reduction later in a lazy manner. We prove the correctness of the algorithm. The algorithm has a message complexity of 2e messages and a worst case time complexity of 2d hops, where e is the number of edges and d is the diameter of the WFG. The algorithm is shown to perform better in both time and message complexity than the best known distributed algorithms to detect distributed generalized deadlocks. We conjecture that the algorithm is optimal in the number of messages and time delay, among distributed algorithms to detect generalized deadlocks.

This paper presents a distributed multimedia synchronization algorithm that supports both intramedia and intermedia synchronizations. The intramedia synchronization is achieved by media scaling techniques, and the intermedia synchronization is achieved by variable service rates. We compute the check period of media buffer and the scaling duration for intramedia synchronization, and compute the comparison period between master media's and slave media's relative time stamps for intermedia synchronization. We also evaluate our algorithm through simulations. Simulation results show that our algorithm performs well in both intramedia and intermedia synchronizations.

This paper presents an analytic model of a reliable multicast session protocol for collaborative continuous-feed applications. The protocol supports N/spl times/N group multicast communications at the session layer and runs on the top of existing reliable transport protocols (e.g., TCP). The protocol is portable as a network-layer-independent library that is suitable for both LAN and WAN environments. It multiplexes messages from different group members into transport packets to reduce the transport overhead per message. It requires only two transport-level connections per node, irrespective of the multicast group size, to reduce the overhead of acknowledgements and retransmissions per node. We compare the throughput of this protocol with the throughput of general sender-initiated and receiver-initiated reliable multicast transport protocols.

To support mobile endpoints in ATM (Asynchronous Transfer Mode) networks, location management schemes have been proposed in which an incoming call to a mobile is first routed to its home switch and then rerouted to the mobile's current location.In this paper, we propose an algorithm for optimizing the route of a connection that becomes suboptimal due to such location-based reroutes in mobile ATM networks based on the PNNI (Private Network-to-Network Interface) standard.This algorithm uses the hierarchical route information of the connection and the summarized topology and loading information of the network to determine a "crossover r&e" such that adjusting the connection from that crossover node results in an optimally routed connection.This route optimization procedure can be executed during mobile connection setup resulting in a one-phase mobile location and connection setup scheme.We also demonstrate how this route optimization procedure can be executed after a connection is set up to a mobile as a secondphase of a two-phase mobile location and connection setup scheme.A comparative performance analysis of the one-and two-phase connection setup schemes is presented.Measures of comparison are call setup delay and the amount of network resources allocated to a connection.The one-phase scheme incurs higher call setup delays, but results in an optimal route during connection setup.On the other hand, the two-phase scheme incurs lower call setup delays, but results in connections with suboptimal routes, prior to the execution of the route optimization phase. -.

No abstract available.

Causal message ordering is required for several distributed applications. In order to preserve causal ordering, only direct dependency information between messages, with respect to the destination process(es), need be sent with each message. By eliminating other kinds of control information from the messages, the communication overheads can be significantly reduced. In this paper we present an algorithm that uses this knowledge to efficiently enforce causal ordering of messages. The proposed algorithm does not require any prior knowledge of the network topology or communication pattern. As computation proceeds, it acquires knowledge of the communication pattern and is capable of handling dynamically changing multicast communication groups, and minimizing the communication overheads. With regard to communication overheads, the algorithm is optimal for the broadcast communication case. Extensive simulation experiments demonstrate that the algorithm imposes lower communication overheads than previous causal ordering algorithms. The algorithm can be employed in a variety of distributed computing environments. Its energy efficiency and low bandwidth requirement make it especially suitable for mobile computing systems. We show how to employ the algorithm for causally ordered multicasting of messages in mobile computing environments.

Consistent global checkpoints have many uses in distributed computations. A central question in applications that use consistent global checkpoints is to determine whether a consistent global checkpoint that includes a given set of local checkpoints can exist. Netzer and Xu (1995) presented the necessary and sufficient conditions under which such a consistent global checkpoint can exist, but they did not explore what checkpoints could be constructed. In this paper, we prove exactly which local checkpoints can be used for constructing such consistent global checkpoints. We illustrate the use of our results with a simple and elegant algorithm to enumerate all such consistent global checkpoints.

In this paper, we propose a quasi-synchronous checkpointing algorithm and a low-overhead recovery algorithm based on it. The checkpointing algorithm preserves process autonomy by allowing them to take checkpoints asynchronously and uses communication-induced checkpoint coordination for the progression of the recovery line which helps bound rollback propagation during a recovery. Thus, it has the easeness and low overhead of asynchronous checkpointing and the recovery time advantages of synchronous checkpointing. There is no extra message overhead involved during checkpointing and the additional checkpointing overhead is nominal. The algorithm ensures the existence of a recovery line consistent with the latest checkpoint of any process all the time. The recovery algorithm exploits this feature to restore the system to a state consistent with the latest checkpoint of a failed process. The recovery algorithm has no domino effect and a failed process needs only to rollback to its latest ch...

Causal message ordering is required for several distributed applications. In order to preserve causal ordering, only direct dependency information between messages with respect to the destination process(es) should be sent with each message. By eliminating other kinds of control information from the messages, the communication overheads can be significantly reduced. In this paper we present an algorithm that uses this knowledge to efficiently enforce causal ordering of messages. The proposed algorithm does not require any prior knowledge of the network or communication topology. As computation proceeds, it acquires knowledge of the logical communication topology and is capable of handling dynamically changing multicast communication groups. With regard to communication overheads, the algorithm is optimal for the broadcast communication case. Its energy efficiency and four bandwidth requirement make it suitable for mobile computing systems. We present a strategy that employs the algorithm for causally ordered multicasting of messages in mobile computing environments.

Mobile computers use wireless channels to communicate with other computers. The finite number of channels should be efficiently allocated to maximize throughput and to avoid co-channel interference. Temporal variations in, channel demand (load) require channel allocation to adapt dynamically to the changing demand. The presence of load imbalance does not automatically imply the usefulness of channel transfer. In this paper we present a probabilistic analysis of the temporal imbalance in channel demand. The effectiveness of channel transfer decisions depends on the probability distribution of the duration for which the imbalance persists. The results of our analysis provide guidelines for the design of dynamic distributed channel allocation strategies.

No abstract available.

No abstract available.

A mobile computing system consists of mobile and stationary nodes, connected to each other by a communication network. The presence of mobile nodes in the system places constraints on the permissible energy consumption and available communication bandwidth. To minimize the lost computation during recovery from node failures, periodic collection of a consistent snapshot of the system (checkpoint) is required. Locating mobile nodes contributes to the checkpointing and recovery costs. Synchronous snapshot collection algorithms, designed for static networks, either force every node in the system to take a new local snapshot, or block the underlying computation during snapshot collection. Hence, they are not suitable for mobile computing systems. If nodes take their local checkpoints independently in an uncoordinated manner, each node may have to store multiple local checkpoints in stable storage. This is not suitable for mobile nodes as they have small memory. This paper presents a synchronous snapshot collection algorithm for mobile systems that neither forces every node to take a local snapshot, nor blocks the underlying computation during snapshot collection. If a node initiates snapshot collection, local snapshots of only those nodes that have directly or transitively affected the initiator since their last snapshots need to be taken. We prove that the global snapshot collection terminates within a finite time of its invocation and the collected global snapshot is consistent. We also propose a minimal rollback/recovery algorithm in which the computation at a node is rolled back only if it depends on operations that have been undone due to the failure of node(s). Both the algorithms have low communication and storage overheads and meet the low energy consumption and low bandwidth constraints of mobile computing systems.

Today's demanding applications, such as multimedia, require higher network transfer rates. Traditional local area networks (LANs) will not be able to provide the throughput required by these applications. The use of switches in LANs is an effective technique to increase the throughput of the network. These switches have finite buffers at their input and output ports. The size of these buffers affect the packet loss rate. It also affect the delay at the switch as packets may have to wait for the output buffer to become available. We study the effect of buffer sizes within these switches. We show how the buffer size is related to the performance of the switch as well as overall performance of the LAN.

In multimedia systems, not only do messages that are sent to and received by multiple sites need to have a consistent order imposed by all sites, but cause and effect relations must be maintained. Causal ordering allows the cause and effect relations of messages to be maintained. This paper presents an algorithm that insures that multimedia data with real-time deadlines are delivered to the application layer in causal order. The algorithm is designed to insure that any message that arrives at a destination site before its deadline will be delivered to the application before the message expires. In addition, by focusing on a form of causal ordering violations caused by "the triangle inequality," this algorithm has a low overhead with respect to the amount of information that must be appended to each message.

We study different local area networks (LAN) configurations and their suitability to multimedia traffic. The transfer rates required by multimedia traffic are beyond the typical bandwidth of traditional LANs. The use of switching hubs in LAN configurations overcomes the bandwidth limitation and supports multiple concurrent communications. We present hub-network configurations that provide high performance and reliability in addition to increasing the effective network bandwidth. We study the performance of these configurations using simulation techniques.

Efficient allocation of communication channels is critical for the performance of wireless mobile computing systems.The centralized channel allocation algorithms proposed in literature are neither robust, nor scalable.Distributed channel allocation schemes proposed in the past are complicated and require active participation of the mobile nodes.These algorithms are unable to dynamically adjust to spatial and temporal fluctuations in channel demand.We present a dynamic distributed channel allocation algorithm that can quickly adapt to changes in load distribution.The algorithm described in this paper requires minimal involvement of the mobile nodes, thus conserving their limited energy supply.The algorithm is proved to be deadlock free, starvation free and fair.It prevents co-channel interference and is scalable.

Abstract Two important components of a global scheduling algorithm are its transfer policy and its location policy. While the transfer policy determines whether a task should be transferred, the location policy determines where it should be transferred. Many global scheduling algorithms have been proposed to schedule tasks with deadline constraints. These algorithms try to transfer tasks only when task's deadlines cannot be met locally or local load is high (i.e. they take only corrective measures). However, a scheduling algorithm that takes preventive measures in addition to corrective measures can reduce potential deadline misses substantially. In this paper we present: (a) a load index which characterizes the system state and is more conducive to preventive and corrective measures; (b) a new transfer policy which takes preventive measures by doing anticipatory task transfers in addition to corrective measures. The proposed transfer policy adapts better to the workload by availing of the accurate system state made available by the proposed load index. An algorithm making use of the new transfer policy and the new load index is shown to reduce the number of deadline misses significantly when compared to algorithms taking only corrective measures.

We are concerned with the problem of determining the potential for load balancing in a distributed computing system. We define a precise measure, called the number of sharable jobs, of this potential in terms of the number of jobs that can usefully be transferred across sites in the system. Properties of this measure are derived, including a general formula for its probability distribution, independent of any particular queuing discipline. A normalized version of the number of sharable jobs, called the job sharing coefficient, is defined. From the general formula, the probability distribution of the number of sharable jobs is computed for three important queuing models and exact expressions are derived in two cases. For queuing models in which an exact expression for the probability distribution of the number of sharable jobs is difficult to obtain, two methods are presented for numerical computation of this distribution. The job sharing coefficient is plotted against traffic intensity for various values of system parameters. Both of these measures are shown to be useful analytic tools for understanding the characteristics of load sharing in distributed systems and can aid in the design of such systems.>

We address the issues related to the delivery of multimedia streams on local area networks. Multimedia integrates voice and video along with text and images into existing systems. Traditionally, local area networks were designed to handle regular data traffic which are bursty in nature and for which variable delay is acceptable. Multimedia traffic, on the other hand, requires constant delay in addition to fast (or real time) delivery. Multimedia traffic also requires large bandwidth compared to regular traffic. Since local area networks are widely in use, their modification to integrate multimedia streams is very important. We propose priority-based communication schemes for the timely delivery of multimedia traffic on local area networks. We compare the performance of these schemes using simulation techniques.>

The results of modeling the performance of searching large text databases (>10 gigabytes) via various parallel hardware architectures and search algorithms are discussed. The performance under load and the cost of each configuration are compared. Strengths, weaknesses, performance sensitivities, and search features supported for each configuration are also addressed. In addition, a common search workload used in the modeling is described. The search workload is derived from a set of searches run against the Chemical Abstracts (CA) file of bibliographic and abstract text available on STN International®. This common workload is applied to all configurations modeled to provide a common basis of comparison. © 1994 John Wiley & Sons, Inc.

Abstract We present a set of library routines that allow easily parallelized graphics rendering routines that require no communication between each parallel task, such as ray‐tracing, to be run efficiently in an environment of distributed workstations. The presentation of the paper focuses on the problems encountered in implementing a distributed system under Unix and proposes solutions to each problem. Specifically, we discuss the challenges involved in overcoming the limits of communicating with a large number of processes in Unix and in providing fault tolerance when using sockets. Technical aspects of the implementation and some additional problems that were encountered are discussed. Finally, we compare the rendering times for a complex image with a renderer using the library and show that the library routines are able to exploit much of the existing parallelism. The library is presented using a graphics application, though the concepts are generic enough to be of use in designing any distributed system under Unix.

We present an efficient one-phase algorithm that consists of two concurrent sweeps of messages to detect generalized distributed deadlocks. In the outward sweep, the algorithm records a snapshot of a distributed wait-for-graph (WFG). In the inward sweep, the algorithm performs reduction of the recorded distributed WFG to check for a deadlock. The two sweeps can overlap in time at a process. We prove the correctness of the algorithm. The algorithm has a worst-case message complexity of 4e/spl minus/2n+2l and a time complexity of 2d hops, where e is the number of edges, n is the number of nodes, l is the number of leaf nodes, and d is the diameter of the WFG. This is a notable improvement over the existing algorithms to detect generalized deadlocks.>

Distributed shared memory provides a useful paradigm for developing distributed applications. As the number of processors in the system and running time of distributed applications increase, the likelihood of processor failure increases. A method of recovering processes running in a distributed shared memory environment which minimizes lost work and the cost of recovery is desirable so that long-running applications are not adversely affected by processor failure. A technique for achieving recoverable distributed shared memory which utilizes asynchronous process checkpoints and logging of pages accessed via read operations on the shared address space is presented. The scheme supports independent process recovery without forcing rollback of operational processes during recovery. The method is particularly useful in environments where taking process checkpoints is expensive.>

Processing rules in a distributed active database involves three design issues: how to decompose rules, how to distribute rules to sites, and how to evaluate distributed rules correctly. The authors study these three issues for complicated rules, which are complex and time-consuming to evaluate. They propose a relational operator, AND, and the associated algebraic manipulations of this operator to find independent parts of a rule query, which can be distributed among sites. Due to geographical dispersion in a distributed system, correct evaluation of distributed rules is not trivial. A distributed evaluation algorithm is preferred, which guarantees the correctness of the evaluation result of the distributed rule by collecting consistent local results from sites to form a global view.>

The performance of the interprocessor communication architecture of the CM-2 is analyzed. A discrete-time Markov chain model of its network architecture is developed to compute the message delay introduced by the network architecture. Due to the synchronous time-division multiplexing nature of the network operation, it is amenable to a discrete-time Markov chain modeling. The analysis yields formulas for response time and several other related performance measures, showing how the performance of the network degrades with the message arrival rate and other parameters. Since the communication delays affect interprocess communication, knowledge of the sensitivity of the delays to the parameters can be a useful aid in designing a high performance parallel system. To keep the analysis tractable, an approximate Markov model is used that requires the use of fixed-point iteration for its solution. Validation of the results against a simulation study reveals that the analysis predicts the performance of the network with high accuracy.>

A dynamic information-structure mutual exclusion algorithm is presented for distributed systems whose information-structure evolves with time as sites learn about the state of the system through messages. An interesting feature of the algorithm is that it adapts itself to heterogeneous or fluctuating traffic conditions to optimize the performance (the number of messages exchanged). The performance of the algorithm is studied by simulation technique and compared to the performance of a well-known mutual exclusion algorithm. The impact message loss and site failures on the algorithm is discussed and methods to tolerate these failures are proposed.>

The authors present a load index to characterize the system state that is more conducive to apply preventive and corrective measures, and a transfer policy which takes preventive measures by doing anticipatory task transfers in addition to corrective measures. Key features of this transfer policy are: (1) it is general and can be used in conjunction with a broad range of existing location policies, (2) it does not require the capability to transfer partially executed tasks, and (3) it adapts better to the system state by looking-ahead. A simulation study shows that an algorithm making use of the transfer policy and the load index reduces the number of deadline misses significantly when compared to algorithms taking only corrective measures.>

The author analyzes and compares the performance of two timestamp ordering concurrency control algorithms, namely, the basic and multiversion, for database systems. The multiversion algorithm improves the performance of the basic timestamp ordering algorithm by keeping multiple versions of data objects. The author discusses the performance enhancement in the multiversion algorithm over the basic algorithm. The author also discusses the storage overhead due to multiple versions of data objects in the multiversion algorithm. The exact performance model of these algorithms is so complex that it is impossible to find a closed-form solution. The author reduces the complexity of the analysis by analyzing a single transaction in isolation and reflects the presence of other transactions on the isolated transaction by the probability of conflict/abort. The analysis provides useful insight into the performance of these algorithms.>

It is argued that most previous proposals for distributed deadlock detection are incorrect because they have used informal/intuitive arguments to prove the correctness of their algorithms. Informal and intuitive arguments are prone to errors because of the highly complex nature of distributed deadlock detection/resolution algorithms. The priority-based probe algorithm for distributed deadlock detection and resolution of A.L. Choudhary et al. (1989) is corrected, and it is formally proven that the modified algorithm is correct (i.e., that it does detect all deadlocks and does not report phantom deadlocks). The proof technique is novel in that the authors first abstract the properties of the deadlock detection and resolution algorithm by invariants, and then show that the invariants imply the desired correctness of the algorithm.>

A hybrid approach to mutual exclusion is proposed to minimize both message traffic and time delay at the same time. A hybrid mutual exclusion algorithm using the release local sites first mode, the requesting group semantics, and the requesting sequence 1324 (i.e., local competition followed by global competition) is found to be an efficient way to control the interaction. This hybrid algorithm uses M. Singhal's (1989) algorithm as the local algorithm and M. Maekawa's (1985) algorithm as the global algorithm. Compared to Maekawa's algorithm, which needs 3 square root N. . .5 square root N messages but two time units delay between successive executions of the critical section (where N is the number of sites in the system), the proposed hybrid algorithm can reduce message traffic by 55% and time delay by 32% at the same time. Furthermore, when a distributed system exhibits locality of requests, the proposed hybrid algorithm can achieve even better performance.>

A fault-tolerant mutual exclusion algorithm for distributed systems is presented. The algorithm uses a distributed queue strategy and maintains alternative paths at each site to provide a high degree of fault tolerance. However, owing to these alternative paths, the algorithm must use reverse messages to avoid the occurrence of directed cycles, which may form when the direction of edges is reversed after the token passes through. If there is no alternative path, the total number of the messages exchanged is O (2*log N) in light traffic and two messages in heavy traffic; however, in this case the system cannot tolerate even a single communication link or site failure. If there are alternative paths between sites, the system can achieve a higher degree of fault tolerance at the expense of increased message traffic (owing to reverse messages). Thus, there is a tradeoff between efficiency and reliability, and a system can be designed to balance these two criteria properly. A recovery procedure for restoring a recovering site consistently into the system is also presented.>

A fully distributed approach to update synchronization is presented where each site completely executes every update. This approach has several features-higher resiliency to different kinds of failures, higher parallelism, improved response to user requests, and low communication overhead. A fully distributed algorithm for concurrency control obtained by rehashing a previously published semidistributed algorithm into the fully distributed model of update execution is presented. A performance model of replicated database systems is presented and used to study the performance of the proposed algorithm and its semidistributed version. The results of the performance study reveal that the proposed approach can substantially improve the performance at the cost of moderate input/output overhead.>

A framework is presented for distributed problem solving. As an illustration of this system, the implementation of a job scheduler to do load balancing in distributed systems is developed and discussed. The framework is developed around a distributed blackboard system with multiple planes in a hierarchy. Sites in a distributed system have an incorrect and inconsistent picture of the states of other sites in the system. In this framework of cooperating specialists communicating by means of distributed blackboards, it is shown how to handle uncertain and unreliable knowledge. Some of the specialists used in the system, results obtained, and directions for future research are described.>

A dynamic information-structure mutual-exclusion algorithm is presented for distributed systems whose information structure evolves with time as sites learn about the state of the system through messages. It is shown that the algorithm achieves mutual exclusion and is free from starvation. Unlike Maekawa-type algorithms, the proposed algorithm is not prone to deadlocks. This is because its information structure forms a staircaselike structure which in conjunction with timestamp ordering eliminates the possibility of deadlock. Besides having the flavor of dynamic information structure, the algorithm adapts itself to heterogeneous or fluctuating traffic conditions to optimize the performance. An asymptotic analysis of the performance of the algorithm for low and heavy traffics of requests for critical section execution is carried out.>

A heuristically-aided algorithm to achieve mutual exclusion in distributed systems is presented which has better performance characteristics than previously proposed algorithms. The algorithm makes use of state information, which is defined as the set of states of mutual exclusion processes in the system. Each site maintains information about the state of other sites and uses it to deduce a subset of sites likely to have the token. Consequently, the number of messages exchanged for a critical section invocation is a random variable between 0 and n (n is the number of sites in the system). It is shown that the algorithm achieves mutual exclusion and is free from deadlock and starvation. The effects of a site crash are discussed, as are those of a communication-medium failure on the proposed algorithm. Methods of recovery from these failures are suggested. The performance of the algorithm is studied using a simulation technique (and an analytic technique for low and heavy traffics of requests for critical section execution).>

Existing algorithms for concurrency control in replicated database systems are semi-distributed because, in these algorithms, only one site completely executes an update and the other sites just commit its writes. The author presents a fully distributed algorithm for concurrency control where each site completely executes every update. This approach has improved resiliency to different kinds of failures, higher parallelism, fast response to user requests, and low communication overhead. The author also presents a performance model of a replicated database system and uses it to study the performance of the proposed algorithm and the algorithm of M. Singhal et al. (1986). The results of the performance study reveal that the proposed approach improves the performance at the cost of nominal I/O overhead.>

In this paper, we analyze the performance of a concurrency control algorithm for replicated database systems. We present a model of a distributed database system which provides a framework to study the performance of different concurrency control algorithms. We discuss performance criteria to evaluate different algorithms. We use the model to analyze the performance of an algorithm for concurrency control in replicated database systems. The technique used in analysis is iterative and approximate. We plot a set of performance measures for several values of the model parameters. The results of analysis are compared against a simulation study.