The emergence of persistent shared memory in recent years has created new opportunities to rethink classic algorithmic problems in the presence of crash-restart failures, and also new challenges as algorithm designers must account for both failures and concurrency. Recent research has explored algorithm design techniques based on powerful base objects that provide special features to simplify recovery from failures as an alternative to the traditional approach of programming more directly using processor instructions. Notably, Friedman, Herlihy, Marathe, and Petrank introduced detectable objects, which allow an application to resolve the outcome of operations that may have been interrupted by a crash. We propose a transformation that replaces low-level memory operations in a conventional algorithm with operations on detectable base objects that leverage persistent memory to enable recovery from crash-restart failures. The transformation is almost universal, and can be used to obtain efficient solutions to complex and previously unsolved problems.

Mutual exclusion is one of the most commonly used techniques to handle contention in concurrent systems. Traditionally, mutual exclusion algorithms have been designed under the assumption that a process does not fail while acquiring/releasing a lock or while executing its critical section. However, failures do occur in real life, potentially leaving the lock in an inconsistent state. This gives rise to the problem of recoverable mutual exclusion (RME) , which involves designing a mutual exclusion (ME) algorithm that can tolerate failures while maintaining required safety and liveness properties. In this work, we present a framework that transforms any algorithm that solves the RME problem into an algorithm that can also simultaneously adapt to (i) the number of processes concurrently competing for the lock, as well as (ii) the number of unresolved failures in the system, while maintaining the correctness properties and performance characteristics of the underlying RME algorithm. Additionally, the algorithm constructed as a result of this transformation adds certain desirable properties such as bounded recovery and fairness. One of the important performance measures of any ME algorithm, including an RME algorithm, is the number of remote memory references (RMRs) made by a process—to acquire and release a lock, as well as to recover the lock structure after a failure. Let R(n) denote the RMR complexity of a critical section request in the underlying RME algorithm, where n denotes the number of processes in the system. Then, our framework yields an RME algorithm for which the RMR complexity of a critical section request is given by \(\mathcal {O}(\min \lbrace \ddot{c},\sqrt {F+1},\ R(n) \rbrace)\) , where \(\ddot{c}\) denotes the point contention of the request and F denotes the failure-density of the request. We further extend our framework by presenting a novel memory reclamation algorithm to bound the space complexity of the RME algorithm. Our memory reclamation algorithm maintains the correctness, performance, and fairness properties of our transformation. Our approach is general enough that it may also be used to bound the space complexity of other RME algorithms. In addition to read and write instructions, our algorithm uses compare-and-swap ( CAS ) and fetch-and-store ( FAS ) hardware instructions, both of which are commonly available in most modern processors.

Recoverable mutual exclusion (RME) is a fault-tolerant variation of Dijkstra's classic mutual exclusion (ME) problem that allows processes to fail by crashing as long as they recover eventually. A growing body of literature on this topic, starting with the problem formulation by Golab and Ramaraju (PODC'16), examines the cost of solving the RME problem, which is quantified by counting expensive shared memory operations called remote memory references (RMRs), under a variety of conditions. Published results show that the RMR complexity of RME algorithms, among other factors, depends crucially on the failure model used: individual process versus system-wide. Recent work by Golab and Hendler (PODC'18) also suggests that explicit failure detection can be helpful in attaining constant RMR solutions to the RME problem in the system-wide failure model. Follow-up work by Jayanti et al. (SPAA'23) shows that such a solution exists even without employing a failure detector, albeit this solution uses a more complex algorithmic approach.

Recoverable mutual exclusion (RME) is a fault-tolerant variation of Dijkstra’s classic mutual exclusion (ME) problem that allows processes to fail by crashing as long as they recover eventually. A growing body of literature on this topic, starting with the problem formulation by Golab and Ramaraju (PODC'16), examines the cost of solving the RME problem, which is quantified by counting the expensive shared memory operations called remote memory references (RMRs), under a variety of conditions. Published results show that the RMR complexity of RME algorithms, among other factors, depends crucially on the failure model used: individual process versus system-wide. Recent work by Golab and Hendler (PODC'18) also suggests that explicit failure detection can be helpful in attaining constant RMR solutions to the RME problem in the system-wide failure model. Follow-up work by Jayanti, Jayanti, and Joshi (SPAA'23) shows that such a solution exists even without employing a failure detector, albeit this solution uses a more complex algorithmic approach. In this work, we dive deeper into the study of RMR-optimal RME algorithms for the system-wide failure model, and present contributions along multiple directions. First, we introduce the notion of withdrawing from a lock acquisition rather than resetting the lock. We use this notion to design a withdrawable RME algorithm with optimal O(1) RMR complexity for both cache-coherent (CC) and distributed shared memory (DSM) models in a modular way without using an explicit failure detector. In some sense, our technique marries the simplicity of Golab and Hendler’s algorithm with Jayanti, Jayanti and Joshi’s weaker system model. Second, we present a variation of our algorithm that supports fully dynamic process participation (i.e., both joining and leaving) in the CC model, while maintaining its constant RMR complexity. We show experimentally that our algorithm is substantially faster than Jayanti, Jayanti, and Joshi’s algorithm despite having stronger correctness properties. Finally, we establish an impossibility result for fully dynamic RME algorithms with bounded RMR complexity in the DSM model that are adaptive with respect to space, and provide a wait-free withdraw section.

Abstract We present Locksynth, a tool that automatically derives synchronization needed for destructive updates to concurrent data structures that involve a constant number of shared heap memory write operations. Locksynth serves as the implementation of our prior work on deriving abstract synchronization code. Designing concurrent data structures involves inferring correct synchronization code starting with a prior understanding of the sequential data structure’s operations. Further, an understanding of shared memory model and the synchronization primitives is also required. The reasoning involved transforming a sequential data structure into its concurrent version can be performed using Answer Set Programming, and we mechanized our approach in previous work. The reasoning involves deduction and abduction that can be succinctly modeled in ASP. We assume that the abstract sequential code of the data structure’s operations is provided, alongside axioms that describe concurrent behavior. This information is used to automatically derive concurrent code for that data structure, such as dictionary operations for linked lists and binary search trees that involve a constant number of destructive update operations. We also are able to infer the correct set of locks (but not code synthesis) for external height-balanced binary search trees that involve left/right tree rotations. Locksynth performs the analyses required to infer correct sets of locks and as a final step, also derives the C++ synchronization code for the synthesized data structures. We also provide a performance analysis of the C++ code synthesized by Locksynth with the hand-crafted versions available from the Synchrobench microbenchmark suite. To the best of our knowledge, our tool is the first to employ ASP as a backend reasoner to perform concurrent data structure synthesis.

The group mutual exclusion (GME) problem is a generalization of the classical mutual exclusion problem in which every critical section is associated with a type or session. Critical sections belonging to the same session can execute concurrently, whereas critical sections belonging to different sessions must be executed serially. The well-known read-write mutual exclusion problem is a special case of the group mutual exclusion problem.

Mutual exclusion (ME) is one of the most commonly used techniques to handle conflicts in concurrent systems. Traditionally, mutual exclusion algorithms have been designed under the assumption that a process does not fail while acquiring/releasing a lock or while executing its critical section. However, failures do occur in real life, potentially leaving the lock in an inconsistent state. This gives rise to the problem of recoverable mutual exclusion (RME) that involves designing a mutual exclusion algorithm that can tolerate failures, while maintaining safety and liveness properties.

Skiplist is an important data structure used for storing and managing ordered data. It provides logarithmic time complexity (in list size) for lookup, insert and remove operations with high probability without the need for complex balancing actions. Several algorithms have been proposed for concurrent maintenance of a skiplist using both blocking and non-blocking synchronization techniques. In this work, we propose a new algorithm for maintaining a concurrent skiplist that uses two techniques to boost performance. The first technique, referred to as "unrolling", involves storing multiple key-value pairs in the same node. The second technique involves using an advanced locking primitive, based on "group mutual exclusion", to allow certain operations to work on the same node concurrently. In our experiments, our concurrent skiplist consistently outperformed existing concurrent skiplists by as much as 90% in some cases.

The group mutual exclusion (GME) problem is a generalization of the classical mutual exclusion problem in which every critical section is associated with a type or session. Critical sections belonging to the same session can execute concurrently, whereas critical sections belonging to different sessions must be executed serially. The well-known read-write mutual exclusion problem is a special case of the group mutual exclusion problem. In a shared memory system, locks based on traditional mutual exclusion or its variants are commonly used to manage contention among processes. In concurrent algorithms based on fine-grained synchronization, a single lock is used to protect access to a small number of shared objects (e.g., a lock for every tree node) so as to minimize contention window. Evidently, a large number of shared objects in the system would translate into a large number of locks. Also, when fine-grained synchronization is used, most lock accesses are expected to be uncontended in practice. Most existing algorithms for the solving the GME problem have high space-complexity per lock. Further, all algorithms except for one have high step-complexity in the uncontented case. This makes them unsuitable for use in concurrent algorithms based on fine-grained synchronization. In this work, we present a novel GME algorithm for an asynchronous shared-memory system that has O(1) space-complexity per GME lock when the system contains a large number of GME locks as well as O(1) step-complexity when the system contains no conflicting requests.

Binary Search Tree (BST) is an important data structure for managing ordered data. Many algorithms---blocking as well as non-blocking---have been proposed for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations based on both external and internal representations of a search tree.

We present a new lock-based algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. Some of the desirable characteristics of our algorithm are: (i) a search operation uses only read and write instructions, (ii) an insert operation does not acquire any locks, and (iii) a delete operation only needs to lock up to four edges in the absence of contention. Our algorithm is based on an internal representation of a search tree and it operates at edge-level (locks edges) rather than at node-level (locks nodes); this minimizes the contention window of a write operation and improves the system throughput. Our experiments indicate that our lock-based algorithm outperforms existing algorithms for a concurrent binary search tree for medium-sized and larger trees, achieving up to 59% higher throughput than the next best algorithm.

We present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. In addition to read and write instructions, our algorithm uses (single-word) compare-and-swap (CAS) and bit-test-and-set (SETB) atomic instructions, both of which are commonly supported by many modern processors including Intel~64 and AMD64.

Analyzing a distributed computation is a hard problem in general due to the combinatorial explosion in the size of the state-space with the number of processes in the system. By abstracting the computation, unnecessary state explorations can be avoided. Computation slicing is an approach for abstracting distributed computations with respect to a given predicate. We focus on regular predicates, a family of predicates that covers many commonly used predicates for runtime verification. The existing algorithms for computation slicing are centralized - a single process is responsible for computing the slice in either offline or online manner. In this paper, we present first distributed online algorithm for computing the slice of a distributed computation with respect to a regular predicate. Our algorithm distributes the work and storage requirements across the system, thus reducing the space and computation complexity per process.

MapReduce scheme has became the state of the art in parallel processing of vast amount of data in distributed systems. Hadoop, as a popular open-source implementation of this technique, makes use of data block replication mechanism to provide a reliable and fault-tolerant design. To maintain data availability, Hadoop takes into account the possibilities of node and rack failures. Hence, it stores multiple copies of each data block to ensure availability and reliability. The current data block placement policy is to randomly distribute the replicas on all servers, satisfying some constraints such as preventing storage of two replicas of a data block on a single node. Our study proposes an efficient placement policy for data block replicas, which can reduce the consumed energy in data centers. The proposed policy is built upon the covering subset (CovSet) method. The effectiveness of the proposed approach is confirmed through simulations. Also, our experiments show that the proposed method becomes more effective whenever the average number of data blocks per server increases, which corresponds to the actual conditions in practice.

An important first step when deploying a wireless ad hoc network is neighbor discovery in which every node attempts to determine the set of nodes it can communicate within one wireless hop. In the recent years, cognitive radio (CR) technology has gained attention as an attractive approach to alleviate spectrum congestion. A CR transceiver can operate over a wide range of frequencies possibly spanning multiple frequency bands. A CR node can opportunistically utilize unused wireless spectrum without interference from other wireless devices in its vicinity. Due to spatial variations in frequency usage and hardware variations in radio transceivers, different nodes in the network may perceive different subsets of frequencies available to them for communication. This heterogeneity in the available channel sets across the network increases the complexity of solving the neighbor discovery problem in a CR network. In this paper, we design and analyze several randomized algorithms for neighbor discovery in such a (heterogeneous) network under a variety of assumptions.

We investigate the problem of maintaining a topology with small degree as well as small diameter in a dynamic distributed system such that the system always stays connected and processes that wish to leave the system can do so quickly. Perpetual system connectivity is necessary to solve many important problems in dynamic distributed systems, including atomic broadcast and stable property detection, that need strict (deterministic) guarantees about system connectivity to be solvable. To our knowledge, in all existing topology maintenance algorithms for asynchronous distributed systems that provide perpetual system connectivity, either: (i) the topology has large worst-case degree and/or diameter (ii) a process may experience high worst-case delay when leaving the system, or (iii) processes cannot join and/or leave concurrently. In this paper, we present a spanning tree maintenance algorithm that satisfies the following desirable properties. First, the spanning tree has small maximum degree of O(1) and small maximum diameter of O(log N), where N denotes the maximum size of the system. Second, any process can leave the system within O(log N) time even in the presence of concurrent arrivals and departures. Third, the system always stays connected. We show using a simple knowledge-based argument that, in any algorithm that maintains perpetual connectivity such that the topology has either worst-case diameter of ¿(log N) or worst-case degree of O(1), the departure of a process may be delayed by ¿(log log N) time in the worst-case.

In this paper, we propose SKAIT, a parameterized symmetric key pre-distribution scheme that guarantees a secure and confidential channel between every pair of nodes in a wireless network. Parameterization enables control over the number of keys assigned to a node, and allows users to trade increased key space complexity for improved collusion resistance. We provide an analysis of the space complexity, time complexity, and collusion resistance, and we show that message exchange is secure against internal and external eavesdroppers. We also show via analysis and simulation that SKAIT possesses the ability to make efficient use of key storage capacities of at least 3 sqrt (n), and collusion resistance superior to that of two recently proposed schemes when the number of colluding nodes is small.

An important step in the initialization of a wireless ad hoc network is neighbor discovery in which every node attempts to determine the set of nodes it can communicate with in one wireless hop. In recent years, cognitive radio technology has gained attention as an attractive approach to alleviate the congestion within the frequency spectrum. A cognitive radio transceiver can operate over a wide range of frequencies possibly spanning multiple frequency bands. A cognitive radio node can scan the frequency spectrum and dynamically identify frequencies that it can use for communication without interference from other wireless devices in its vicinity. When multiple cognitive radio nodes come together to form an ad hoc network, due to spatial variations in frequency usage and hardware variations in radio transceivers, different nodes in the network may perceive different subsets of frequencies available to them for communication. This heterogeneity in the available channel sets across the network increases the complexity of conducting neighbor discovery in a cognitive radio network. In this paper, we propose a new deterministic neighbor discovery algorithm for heterogeneous multi-hop cognitive radio networks with termination detection capability. Our algorithm allows nodes to detect termination of the neighbor discovery process. Our simulation results indicate that our algorithm is much faster compared to a recently proposed deterministic neighbor discovery algorithm (a reduction of 97-98% in time complexity ) and termination detection is lightweight (at most 3% of the total time complexity).

We present a novel key predistribution scheme that uses deployment knowledge to divide deployment regions into overlapping clusters, each of which has its own distinct key space. Through careful construction of these clusters, network resilience is improved, without compromising connectivity or communications overhead. Experimental results show significant improvement in performance over existing schemes based on deployment knowledge.

Termination detection in distributed systems has been a popular problem of study. It involves determining whether a computation running on multiple nodes has ceased all its activities. A large number of termination detection algorithms have been proposed for static distributed systems in which the number of nodes present in the system is fixed and never changes during runtime. Recently, the termination detection problem has been investigated in the context of dynamic distributed systems in which individual nodes may join and/or leave the system at any time. In this paper, we propose an efficient algorithm for detecting termination of a computation in a dynamic, asynchronous, distributed system that allows nodes to join as well as leave the system while the computation is in progress. Our simulation results indicate that our algorithm has lower message complexity as well as lower detection latency than other comparable algorithms for solving the same problem.

Software simulation has often been used to evaluate proposed protocols for wireless devices. Simulation allows for rapid development and testing, but does not provide a realistic RF environment. To compensate for this, field experiments are performed. However, problems encountered during field experiments can be difficult to locate and correcting problems on-site can be time-consuming. Emulations attempt to provide the advantages of simulation and field experiments without the suffering the disadvantages of both. This demo provides an overview of the hardware, software, and emulation capabilities of ASSERT, an emulation testbed.

Predistribution of cryptographic keys is a widely used approach for establishing secure communication between network nodes which are severely resource-constrained. Many proposed key predistribution schemes make the implicit assumption that message contents need not be kept private from nodes other than the intended recipient. Messages in such schemes are not guaranteed to be confidential--they may be read by nodes within the network other than the intended recipient. In this paper, we present TASK--a symmetric key predistribution scheme that enables secure and confidential communication within wireless networks. TASK distributes keys by generating and reinforcing a series of template key assignment instances. We show, through analysis and simulation, that TASK achieves a level of security superior to that of two recently proposed schemes that also provide confidentiality, while maintaining the same space complexity. TASK is also parameterized, which allows it to make use of key storage capacities that other recently proposed schemes cannot.

Evaluating queries in distributed sensor networks while preserving privacy of data is a challenging problem. In this paper, we propose a new scheme for evaluating almost all types of queries, including sum, min/max, mean, median and histogram, accurately while, at the same time, preserving privacy of individual data. Our scheme does not require sensor nodes to share secret keys with each other. Further, it does not use encryption and secure hashing, both of which can be expensive operations.

In this paper we investigate a special type of denial of service (DoS) attack on 802.11-based networks, namely deauthentication/disassociation attack. In the current IEEE 802.11 standards, whenever a wireless station wants to leave the network, it sends a deauthentication or disassociation frame to the access point. These two frames, however, are sent unencrypted and are not authenticated by the access point. Therefore, an attacker can launch a DoS attack by spoofing these messages and thus disabling the communication between a wireless device and its access point. We propose an efficient solution based on a one way hard function to verify that a deauthentication/disassociation frame is from a legitimate station. We implement our solution on some 802.11 devices and the experimental results show that our protocol is highly effective against this DoS attack.

The group mutual exclusion problem extends the traditional mutual exclusion problem by associating a type (or a group) with each critical section. In this problem, processes requesting critical sections of the same type can execute their critical sections concurrently. However, processes requesting critical sections of different types must execute their critical sections in a mutually exclusive manner. We present a distributed algorithm for solving the group mutual exclusion problem based on the notion of surrogate-quorum. Intuitively, our algorithm uses the quorum that has been successfully locked by a request as a surrogate to service other compatible requests for the same type of critical section. Unlike the existing quorum-based algorithms for group mutual exclusion, our algorithm achieves a low message complexity of O(q) and a low (amortized) bit-message complexity of O(bqr), where q is the maximum size of a quorum, b is the maximum number of processes from which a node can receive critical section requests, and r is the maximum size of a request while maintaining both synchronization delay and waiting time at two message hops. As opposed to some existing quorum-based algorithms, our algorithm can adapt without performance penalties to dynamic changes in the set of groups. Our simulation results indicate that our algorithm outperforms the existing quorum-based algorithms for group mutual exclusion by as much as 45 percent in some cases. We also discuss how our algorithm can be extended to satisfy certain desirable properties such as concurrent entry and unnecessary blocking freedom.

Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies the predicate. On the other hand, computation slicing is concerned with computing the smallest subcomputation (with the least number of consistent cuts) that contains all consistent cuts of the computation satisfying the predicate. In this paper, we investigate the relationship between predicate detection and computation slicing and show that the two problems are actually equivalent. Specifically, given an algorithm to detect a predicate b in a computation C, we derive an algorithm to compute the slice of C with respect to b. The time complexity of the (derived) slicing algorithm is O(n|E|T), where n is the number of processes, E is the set of events, and O(T) is the time complexity of the detection algorithm. We discuss how the "equivalence" result of this paper can be utilized to derive a faster algorithm for solving the general predicate detection problem in many cases. Slicing algorithms described in our earlier papers are all offline in nature. In this paper, we also present two online algorithms for computing the slice. The first algorithm can be used to compute the slice for a general predicate. Its amortized time complexity is O(n(c + n)T) per event, where c is the average concurrency in the computation and O(T) is the time complexity of the detection algorithm. The second algorithm can be used to compute the slice for a regular predicate. Its amortized time complexity is only O(n2) per event.

The group mutual exclusion problem extends the traditional mutual exclusion problem by associating a type with each critical section. In this problem, processes requesting critical sections of the same type can execute their critical sections concurrently. However, processes requesting critical sections of different types must execute their critical sections in a mutually exclusive manner. In this paper, we provide a distributed algorithm for solving the group mutual exclusion problem based on the notion of surrogate-quorum. Intuitively, the algorithm uses the quorum that has been successfully locked by a request as a surrogate to service other compatible requests for the same type of critical section. Unlike the existing quorum-based algorithms for group mutual exclusion, the algorithm achieves a low message complexity of O(q), where q is the maximum size of a quorum, while maintaining both synchronization delay and waiting time at two message hops. Moreover, like the existing quorum-based algorithms, the algorithm has high maximum concurrency of n, where n is the number of processes in the system. The existing quorum-based algorithms assume that the number of groups is static and does not change during runtime. However, the algorithm can adapt without performance penalties to dynamic changes in the number of groups. Simulation results indicate that our algorithm outperforms the existing quorum-based algorithms for group mutual exclusion by as much as 50% in some cases

Path restoration is an important approach for building survivable telecommunication backbone networks. Path restoration is known for high restoration efficiency and its ability to protect against single link, multiple link and node failures. Path restoration can be formulated as the well-known multi-commodity network flow (MCNF) problem. While many centralized algorithms have been proposed for solving the MCNF problem, distributed algorithms have received very little attention. This paper presents an online distributed multi-commodity flow approximation algorithm specifically tailored for path restoration. Our algorithm uses O(|E|diam/sup 2/) messages and O(diam/sup 2/) time in the worst case, and substantially fewer messages and less time in practical networks. When simulated on a sample real-life backbone network similar to those used by the telecommunication service providers, our algorithm finds a solution significantly faster than many published algorithms.

Summary form only given. Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies the predicate. On the other hand, computation slicing is concerned with computing the smallest sub-computation - with the least number of consistent cuts - that contains all consistent cuts of the computation satisfying the predicate. We investigate the relationship between predicate detection and computation slicing and show that the two problems are equivalent. Specifically, given an algorithm to detect a predicate b in a computation C, we derive an algorithm to compute the slice of C with respect to b. The time-complexity of the (derived) slicing algorithm is O(n|E|) times the time-complexity of the detection algorithm, where n is the number of processes and E is the set of events. We discuss how the "equivalence " result can be utilized to derive a faster algorithm for solving the general predicate detection problem. Slicing algorithms described in our earlier papers are all off-line in nature. We also give an online algorithm for computing the slice for a predicate that can be detected efficiently. The amortized time-complexity of the algorithm is O(n(c + n)) times the time-complexity of the detection algorithm, where c is the average concurrency in the computation.

Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems, especially those employed in safety-critical environments, should be able to operate properly even in the presence of software faults. Monitoring the execution of a distributed system, and, on detecting a fault, initiating the appropriate corrective action is an important way to tolerate such faults. This gives rise to the predicate detection problem which involves finding a consistent cut of a distributed computation, if it exists, that satisfies the given global predicate. Detecting a predicate in a computation is, however, an NP-complete problem. To ameliorate the associated combinatorial explosion problem, we introduce the notion of computation slice in our earlier papers [5, 10]. Intuitively, slice is a concise representation of those consistent cuts that satisfy a certain condition. To detect a predicate, rather than searching the state-space of the computation, it is much more efficient to search the state-space of the slice. In this paper we provide efficient algorithms to compute the slice for several classes of predicates. Our experimental results demonstrate that slicing can lead to an exponential improvement over existing techniques in terms of lime and space.

We introduce the notion of a slice of a distributed computation. A slice of a distributed computation with respect to a global predicate is a computation which captures those and only those consistent cuts of the original computation which satisfy the global predicate. We show that a slice exists for a global predicate iff the predicate is a regular predicate. We then give an efficient algorithm for computing the slice and show applications of slicing to testing and debugging of distributed programs.

Monitoring of global predicates is a fundamental problem in asynchronous distributed systems. This problem arises in various contexts, such as design, testing and debugging, and fault tolerance of distributed programs. In this paper, we establish that the problem of determining whether there exists a consistent cut of a computation that satisfies a predicate in k-CNF (k/spl ges/2), in which no two clauses contain variables from the same process, is NP-complete in general. A polynomial-time algorithm to find the consistent cut, if it exists, that satisfies the predicate for special cases is provided. We also give algorithms (albeit exponential) that can be used to achieve an exponential reduction in time over existing techniques for solving the general version. Furthermore, we present an algorithm to determine whether there exists a consistent cut of a computation for which the sum x/sub 1/+x/sub 2/+/spl middot//spl middot//spl middot/+x/sub n/ exactly equals some constant k, where each x/sub i/ is an integer variable on a process p/sub i/ such that it is incremented or decremented by at most one at each step. As a corollary, any symmetric global predicate on Boolean variables, such as absence of simple majority and exclusive-OR of local predicates, can now be detected. Additionally, the problem is proved to be NP-complete if each x/sub i/ can be changed by an arbitrary amount at each step. Our results solve the previously open problems in predicate detection proposed by V.K. Garg (1997) and bridge the wide gap between the known tractability and intractability results that have existed until now.

Relational DBMSs (RDBMSs) have evolved to an extent that they are used to manage almost all traditional business data in a robust fashion. Nevertheless, a large fraction of unstructured and semi-structured data continues to be managed by file systems. As companies increasingly depend on non-traditional data for their daily business operations, it becomes more and more important to provide higher degree of integrity, security and reliability to the data stored in file systems. DataLinks technology, developed at IBM Almaden Research Center, achieves this by providing a vital integration between a RDBMS and a file system. It enables the DBMS to manage files residing in file systems as though they are logically within the database. Current DataLinks technology supports only read access to external files that are being managed by the DBMS. This severely restricts the applicability of DataLinks technology in transaction-oriented and/or e-business applications. Traditional database systems enforce ACID properties for database updates. Extending these properties to cover both external files stored outside of a DBMS and metadata stored in the DBMS is a hard problem. This is because files are updated through a standard file-system API while metadata, which references the files, is updated through a database API. This paper describes our experiences in the design and prototyping of an advanced DataLinks technology that supports database-managed external file updates. This enhanced capability makes DataLinks technology an even more attractive solution for managing the world's data.

Distributed programs are hard to write. A distributed debugger equipped with the mechanism to re-execute the traced computation in a controlled fashion can greatly facilitate the detection and localization of bugs. This approach gives rise to a general problem, called predicate control problem, which takes a computation and a safety property specified on the computation, and outputs a controlled computation that maintains the property. We define a class of global predicates, called region predicates, that can be controlled efficiently in a distributed computation. We prove that the synchronization generated by our algorithm is optimal. Further, we introduce the notion of an admissible sequence of events and prove that it is equivalent to the notion of predicate control. We then give an efficient algorithm for the class of disjunctive predicates based on the notion of an admissible sequence. 1.

The traditional distributed shared memory (DSM) model provides atomicity at levels of read and write on single objects. Therefore, multi-object operations such as double compare and swap, and atomic m-register assignment cannot be efficiently expressed in this model. We extend the traditional DSM model to allow operations to span multiple objects. We show that memory consistency conditions such as sequential consistency and linearizability can be extended to this general model. We also provide algorithms to implement these consistency conditions in a distributed system.