Search

Linked lists and other list-based sets are some of the most ubiquitous data structures in computer science. They are useful in their own right and are frequently used as building blocks in other data structures. A linked list can be "unrolled" to combine multiple keys in each node; this improves storage density and overall performance. This organization also allows an operation to skip over nodes which cannot contain a key of interest. This work introduces a new high-performance concurrent unrolled linked list with a lazy synchronization strategy. Most write operations under this strategy can complete by locking a single node. Experiments show up to 300% improvement over other concurrent list-based sets. [ABSTRACT FROM AUTHOR]

Abstract: A cognitive radio node is a radio device capable of operating over multiple channels. As a result, a network consisting of one or more cognitive radio nodes can adapt to varying channel availability in its geographical region by dynamically changing the channel (or channels) nodes are using for communication. We investigate the problem of designing a fast deterministic algorithm for neighbor discovery in an undirected network consisting of one or more cognitive radio nodes when different nodes may have different subsets of channels available for communication at their location. We say that a neighbor discovery algorithm is fast if its time-complexity is polynomial in actual network-size. We prove that it is impossible to devise a fast algorithm to solve the neighbor discovery problem if nodes are neither size-aware nor collision-aware. When nodes are collision-aware, we present a fast algorithm for neighbor discovery with time-complexity of , where denotes the actual number of nodes present in the network, denotes the size of space used for assigning labels to the nodes, and denotes the number of channels over which nodes can operate. Our algorithm has the desirable property that every node knows when the neighbor discovery has completed and, moreover, all nodes terminate at the same time. When nodes are size-aware, we use a gossiping algorithm for a single-channel network with large labels that was proposed recently to derive a fast adaptive algorithm for neighbor discovery. We also investigate the neighbor discovery problem when the network may be directed. Finally, we describe a way to speed up neighbor discovery when nodes are collision-aware and channel availability sets of neighboring nodes do not vary significantly. [Copyright &y& Elsevier]

Abstract: We investigate the problem of detecting termination of a distributed computation in systems where processes can fail by crashing. Specifically, when the communication topology is fully connected, we describe a way to transform any termination detection algorithm that has been designed for a failure-free environment into a termination detection algorithm that can tolerate process crashes. Our transformation assumes the existence of a perfect failure detector. We show that a perfect failure detector is in fact necessary to solve the termination detection problem in a crash-prone distributed system even if at most one process can crash. Let and denote the message complexity and detection latency, respectively, of when the system has processes and the underlying computation exchanges application messages. The message complexity of is messages per failure more than the message complexity of . Also, its detection latency is per failure more than that of . Furthermore, application message size increases by at most bits, where is the actual number of processes that fail during an execution. We show that, when the communication topology is fully connected, under certain realistic assumption, any fault-tolerant termination detection algorithm can be forced to exchange control messages in the worst-case even when at most one process may be active initially and the underlying computation does not exchange any application messages. This implies that our transformation is optimal in terms of message complexity when . The fault-tolerant termination detection algorithm resulting from the transformation satisfies three desirable properties. First, it can tolerate the failure of up to processes. Second, it does not impose any overhead on the fault-sensitive termination detection algorithm until one or more processes crash. Third, it does not block the application at any time. Further, using our transformation, we derive a fault-tolerant termination detection algorithm that is the most efficient fault-tolerant termination detection algorithm that has been proposed so far to our knowledge. Our transformation can be extended to arbitrary communication topologies provided process crashes do not partition the system. [Copyright &y& Elsevier]

Abstract: In the group mutual exclusion problem, each critical section has a type or a group associated with it. Processes requesting critical sections belonging to the same group (that is, of the same type) may execute their critical sections concurrently. However, processes requesting critical sections belonging to different groups (that is, of different types) must execute their critical sections in a mutually exclusive manner. Most algorithms for solving the group mutual exclusion problem that have been proposed so far in the literature treat all groups equally. This is quite acceptable if a process, at the time of making a request for critical section, selects a group for the critical section uniformly. However, if some groups are more likely to be selected than others, then better performance can be achieved by treating different groups in a different manner. In this paper, we propose an efficient algorithm for solving the group mutual exclusion problem when group selection probabilities are non-uniformly distributed. Our algorithm has a message complexity of per request for critical section, where is the number of processes in the system. It has low synchronization delay of one message hop and low waiting time of two message hops. The maximum concurrency of our algorithm is , which implies that if all processes have requested critical sections of the same type then all of them may execute their critical sections concurrently. Finally, the amortized message-size complexity of our algorithm is . Our experimental results indicate that our algorithm outperforms the existing algorithms, whose complexity measures are comparable to that of ours, by as much as 50% in some cases. [Copyright &y& Elsevier]

Abstract: We present an efficient approach to detect a locally stable predicate in a distributed computation. Examples of properties that can be formulated as locally stable predicates include termination and deadlock of a subset of processes. Our algorithm does not require application messages to be modified to carry control information (e.g., vector timestamps), nor does it inhibit events (or actions) of the underlying computation. The worst-case message complexity of our algorithm is , where is the number of processes in the system and is the number of events executed by the underlying computation. We show that, in practice, its message complexity should be much lower than its worst-case message complexity. The detection latency of our algorithm is time units, where is the diameter of communication topology. Our approach also unifies several known algorithms for detecting termination and deadlock. We also show that our algorithm for detecting a locally stable predicate can be used to efficiently detect a stable predicate that is a monotonic function of other locally stable predicates. [Copyright &y& Elsevier]

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 cognitive radio transceiver can operate over a wide range of frequencies possibly spanning multiple frequency bands. A cognitive radio 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 cognitive radio network. In this work, we design and analyze several randomized algorithms for neighbor discovery in such a (heterogeneous) network under a variety of assumptions ( e.g. , maximum node degree known or unknown) for both synchronous and asynchronous systems under minimal knowledge. We also show that our randomized algorithms are naturally suited to tolerate unreliable channels and adversarial attacks. [ABSTRACT FROM AUTHOR]