Relaxed consistency models have been reported to significantly improve the performance of training machine learning (ML) models compared to strong consistency models. However, the existing relaxed consistency models for distributed ML either force fast workers to wait for stragglers (e.g., stale-synchronous models) or have no upper bound on data staleness (e.g., asynchronous models), thus negatively affecting the quality and performance of training ML models. We propose a new asynchronous non-blocking consistency model with bounded staleness for distributed ML that overcomes the drawbacks of blocking and unbounded staleness in previous relaxed consistency models. The new model, named Chained Asynchronous Consistency (CAC), guarantees an upper bound on data staleness in asynchronous computation without forcing fast workers to wait for slow workers. We theoretically prove that the Stochastic Gradient Descent (SGD) algorithm under CAC converges and the upper bound on the convergence expectation is independent of the number of workers. Based on the CAC model, we develop a new staleness-aware cacheable distributed object (CAC-object) for distributed ML where shared parameters are distributed among workers in a peer-to-peer manner. This approach avoids intermediate centralized storage, such as parameter servers, while maintaining simple one-sided communication (e.g., get and put ). The CAC-object allows remote parameters to be cached and reused locally following a consistency model (e.g., CAC, stale-synchronous or asynchronous model). To demonstrate the applicability of the CAC-object in asynchronous distributed ML, we introduce a new asynchronous distributed matrix completion algorithm (CAC-MF) using the CAC-object. We develop the CAC-object and CAC-MF using UPC++, a Partitioned Global Address Space (PGAS) library for high-performance computing (HPC), and evaluate them in different execution scenarios (e.g., with and without stragglers and crash failures, different minibatch sizes) on HPC clusters. Our experimental results show that the CAC model scales with increasing workers, tolerates stragglers and crash failures, and achieves better convergence than stale-synchronous and asynchronous models. Particularly, in the case of halted stragglers, CAC’s Root Mean Square Error (RMSE) is up to 25 times less than the baseline models’ RMSE for the Netflix dataset, and 170 times less for the MovieLens dataset.

Thanks to their high maneuverability, high flexibility, and low cost, unmanned aerial vehicles (UAVs) have been widely used for data collection in the Internet of Things (IoT). To deal with UAV's onboard battery limitation, UAV-to-UAV (U2U) wireless charging mechanism emerges as a promising solution for extending flight distance and reducing mission completion time. However, U2U charging mechanisms encounter key challenges of limited wireless charging distance and energy loss. In this paper, we propose eU2U, a novel energy-efficient wireless charging and trajectory design approach for IoT data collection. We develop eU2U based on the distributed laser charging (DLC) system for its compact size and meter-level wireless power transmission. To minimize the total energy consumption, we build holistic power and energy consumption models for U2U-enabled data collection. With joint considerations on the wireless charging energy loss and delay constraint, we propose a heuristic algorithm to derive the most energy-efficient locations of the U2U charging points and the UAV trajectories, where the charging points are determined from the Fermat point and the battery drain point. Extensive evaluations show that eU2U can reduce the total energy consumption by 44.52% as compared to state-of-the-art schemes.

Shared Electric Vehicle (EV) charging emerges as a mutually beneficial paradigm where EV charging hosts can earn income by renting out their home EV chargers with autonomous pricing, and EV users gain access to a broader range of charging options. However, existing works on EV charging scheduling either propose global optimal solutions that may conflict with users' individual interests, or fail to fully consider the diverse demands of EV users and the varying characteristics of EV hosts. In this paper, we propose iCharging, an efficient decentralized Nash equilibrium approach for shared EV charging using weighted congestion game. In particular, each EV user only follows the strategy to minimize its user-specific cost while accounting for the congestion incurred by other users. By proving that the formulated game possesses at least one pure Nash equilibrium (PNE), we devise an optimized parallel batch-based best response dynamics algorithm to steer users' strategy profiles towards a PNE in linear time complexity for each individual variable. Through extensive evaluations using real-world datasets from OpenStreetMap and ACN-Data, we demonstrate that iCharging can converge to a PNE time-efficiently in EV host-user matching while integrating users' specific preferences and dynamic congestion levels, with only a 3.34 % increase in the average total cost compared to the global optimal solution.

Vehicular Edge Computing (VEC) emerges as a rem-edy to achieve flexible and fine-grained air pollution monitoring, where vehicles equipped with onboard sensors can sense, process, calibrate and store air pollutants on the drive, and roadside units (RSUs) can be deployed for vehicles to offload data via low-cost vehicle-to-RSU (V2R) communication. However, existing VEC-based air pollution monitoring solution either suffers from high deployment cost, limited V2R communication distance, or degraded data collection latency. To address these challenges, we propose a novel cost-efficient VEC deployment solution for mobile air pollution monitoring, where a set of buses are used to monitor the air pollutants, and selected bus stations are equipped with RSU s for offloading the collected data, considering the effective communication distance and power consumption of V2R. To jointly minimize the VEC deployment cost and data collection latency, we build a multi-objective problem formulation under the constraints of resource, latency, etc. Then we propose a Two-stage Cost-efficient VEC Deployment (TCVD) algorithm based on two heuristic strategies, i.e., the near-equivalence point deployment strategy and the conditioned RSU deployment strategy, with a theoretically-proved worst-case bound. Through extensive evaluations on an open data set of Dublin bus, we verify that TCVD not only reduces the data collection latency by 25.04%, but also reduces the total VEC deployment cost by 30.81 % as compared with existing schemes.

IoT nodes need to be updated after deployment. However, doing so for nodes deployed to resource-challenged environments, like the arctic tundra, is a challenge. Because humans as the common case cannot physically visit the nodes, updating must be done from a remote update service over a back-haul data network. However, most nodes are not in range of a back-haul data network. Even when nodes are in range, they probably sleep to conserve energy and the remote cloud back-end therefore cannot communicate with them.We report on an approach and a prototype system for distributing updates from a cloud update distribution service to nodes. We assume that nodes carry one or several local area network technologies supporting short-lived point-to-point ad-hoc communication between two nodes at a time in range of each other. We assume that a single node in each neighborhood has a back-haul network, and delegate to this node to further distribute updates inside the neighborhood.A series of performance measuring experiments were conducted on the update distribution system when it executes on nodes with behaviors from always-on to mostly-off. We document how the distribution system behaves through a set of performance metrics. The results are very sensitive to the behavior of the nodes.

A wireless sensor network (WSN) depends on energy to operate and considerable efforts have been devoted to extend its operational lifetime. Energy harvesting (EH) has emerged as one promising approach to prolong the lifetime of a WSN without interrupting its operations. In an EH-WSN, sensor nodes typically have batteries being charged with energy harvested from ambient environments such as wind, solar, water mills etc. However, uncertainties remain about when and how much energy can be harvested over time from the environments and about traffic fluctuation at each node. Unfortunately, existing works on EH-WSN are limited in evaluating the impacts of these factors and the number of the nodes in an EH-WSN on its key performance metrics. This paper, therefore, presents a general method and a practical implementation of a node capable of harvesting solar energy in an EH-WSN. The paper then evaluates the performance of the EH-WSN. Explicit mathematical expressions define models for network operational time, throughput and reliability of the EH-WSN and simulations are used to validate the models. Influential factors are energy arrival rate, traffic rate at each node and the number of nodes in an EH-WSN. The results document that the analytical models and simulations correspond.

Beacon-enabled IEEE 802.15.4 standard has been widely applied for industrial applications because it can provide contention-free access by using guaranteed time slots (GTSs) in contention-free period (CFP) of a super frame. In IEEE 802.15.4 networks, sensors can also request GTSs for purpose of reliable communication. In existing GTS scheduling studies, however, a sensor wishing to use GTSs has to send a GTS request to a network coordinator. The sending of the GTS request by using carrier sense multiple access with collision avoidance (CSMA/CA) algorithm in fact creates more traffic in the networks. This results in more collisions and packets blocking probability. In addition, if the transmission of GTS request is failed, bandwidth utilization can be low because all GTSs are not allocated. This paper therefore proposes an advanced GTS scheduling (AGS) algorithm, applied in homogeneous networks, to solve those problems. The proposed algorithm eliminates the sending GTS request and allocates GTSs to sensors based on their time order of discovery and the observation of actual allocated GTS usage. Simulation results show that AGS algorithm improves the performance of IEEE 802.15.4 networks in term of bandwidth utilization, packet blocking probability and number of collision per transmission request. In some scenarios, packet blocking probability is reduced about 30 %.

Observing an environment is essential to its understanding. This is certainly true for the arctic tundra as it is extremely sensitive to climate change. Satellites are used to observe large areas of the arctic tundra. However, the measurements are not at sufficient spatial resolution to be used to determine the species of animals, and to measure humidity, temperature, and CO2 levels for small areas. Ground-based measurements, which represent less that one percent of the experiments carried on the arctic tundra, must be done. Deploying and maintaining ground-based instruments is hard to do because visiting the arctic tundra is expensive, time consuming, and dangerous. Instead, automation is needed, where instruments can operate independently for long periods of time, and allow interaction with remote users for reporting of data and control of the instruments. However, the arctic tundra also has, as a common case, limited data network and energy coverage. We present the Distributed Arctic Observatory, where instruments called Observation Units (OUs) are distributed across the arctic tundra to measure a range of environmental state variables, and report them to where they are needed for further analysis. The DAO project uses Unmanned Aerial Vehicles (UAVs) to provide backhaul network access and energy to OUs. The modifications applied to the UAV and to OUs are presented. We describe the experiences gathered from practical use of the UAV to provide network access and energy to OUs located on the ground at 70°N. We show that it is feasible to apply UAVs to provide network access and energy to OUs on the arctic tundra, albeit practical restrictions.

Concurrent search trees are crucial data abstractions widely used in many important systems such as databases, file systems and data storage. Like other fundamental abstractions for energy-efficient computing, concurrent search trees should support both high concurrency and fine-grained data locality in a platform-independent manner. However, existing portable fine-grained locality-aware search trees such as ones based on the van Emde Boas layout (vEB-based trees) poorly support concurrent update operations while existing highly-concurrent search trees such as non-blocking search trees do not consider fine-grained data locality. In this paper, we first present a novel methodology to achieve both portable fine-grained data locality and high concurrency for search trees. Based on the methodology, we devise a novel locality-aware concurrent search tree called GreenBST. To the best of our knowledge, GreenBST is the first practical search tree that achieves both portable fine-grained data locality and high concurrency. We analyze and compare GreenBST energy efficiency (in operations/Joule) and performance (in operations/second) with seven prominent concurrent search trees on a high performance computing (HPC) platform (Intel Xeon), an embedded platform (ARM), and an accelerator platform (Intel Xeon Phi) using parallel micro- benchmarks (Synchrobench). Our experimental results show that GreenBST achieves the best energy efficiency and performance on all the different platforms. GreenBST achieves up to 50 percent more energy efficiency and 60 percent higher throughput than the best competitor in the parallel benchmarks. These results confirm the viability of our new methodology to achieve both portable fine-grained data locality and high concurrency for search trees.

With the rise of Internet of Things, end-users expect to obtain data from well-connected smart devices and stations through data services being provisioned in distributed architectures. Such services could be aggregated in a number of smart ways to provide the end-users and third-party applications with sophisticated data (e.g., weather data coupled with soil pollution), resulting in a growing number of service offerings to be requested. Service offerings that have been shortlisted for a certain data request (e.g., rainfall in a particular farming site) need to be ranked according to the end-users' preference. Service level agreements, i.e., the mutual responsibilities between the service provider and its consumers, address this sort of preference. Unfortunately, provisioning quality-aware services under this term still stays on the sidelines. In this paper, we propose a novel service architecture where the service level agreements shall be: (i) accumulated overtime on IoT service transactions; (ii) compiled when aggregating IoT services; (iii) used as a ranking criterion for suggesting IoT service offerings. We demonstrate our new approach in the service provisioning of agricultural datasets taken from a farming site of the Mekong Delta in Vietnam.

Recently, renewed interest has been given to improving energy efficiency of automated home systems for which Zigbee (over IEEE 802.15.4) is a potential technology. The IEEE 802.15.4 standard supports both contention-free and contention-based services. Contention-free services can be provided via guaranteed time slots (GTS) in beacon mode. However, directly applying GTS scheduling in IEEE 802.15.4 for resource management is not efficient in improving network performance. First, the improvement of GTS scheduling requires adding more bits and fields to IEEE 802.15.4 frames or more layers to Zigbee network stacks, this results in incompatibility problems with deployed products. Second, the network coordinator fails to assess the exact bandwidth demand from sensors for optimal resource management; resulting in the waste of network resources. This paper therefore proposes a resource management approach for improving the performance of IEEE 802.15.4-based automated home systems. The solution includes four extensions of the IEEE 802.15.4 standard. First, sensors specify data size they have to transmit instead of number of GTSs in their GTS command frames. Second, the coordinator handles two separate queues: a GTS allocation queue and a GTS deallocation one. Third, the coordinator runs the optimal GTS scheduling algorithm and fourth, the sensor operates according to the optimal power- saving algorithm. Extensive simulations show that the proposed approach significantly improves network performance in terms of power efficiency, bandwidth utilization and throughput while guaranteeing delay requirements for home automation applications.

Significant efforts have been devoted to choosing the best configuration of a computing system to run an application energy efficiently. However, available tuning approaches mainly focus on homogeneous systems and are inextensible for heterogeneous systems which include several components (e.g., CPU s, G PU s) with different architectures. This study proposes a holistic tuning approach called REOH using probabilistic network to predict the most energy-efficient configuration (i.e., which platform and its setting) of a heterogeneous system for running a given application. Based on the computation and communication patterns from Berkeley dwarfs, we conduct experiments to devise the training set including 7074 data samples covering varying application patterns and characteristics. Validating the REOH approach on heterogeneous systems including CPUs and GPUs shows that the energy consumption by the REOH approach is close to the optimal energy consumption by the Brute Force approach while saving 17 % of sampling runs compared to the previous (homogeneous) approach using probabilistic network. Based on the REOH approach, we develop an open-source energy-optimizing runtime framework for selecting an energy efficient configuration of a heterogeneous system for a given application at runtime.

The fact that graphics processors (GPUs) are today’s most powerful computational hardware for the dollar has motivated researchers to utilize the ubiquitous and powerful GPUs for general-purpose computing. However, unlike CPUs, GPUs are optimized for processing 3D graphics (e.g., graphics rendering), a kind of data-parallel applications, and consequently, several GPUs do not support strong synchronization primitives to coordinate their cores. This prevents the GPUs from being deployed more widely for general-purpose computing. This paper aims at bridging the gap between the lack of strong synchronization primitives in the GPUs and the need for strong synchronization mechanisms in parallel applications. Based on the intrinsic features of typical GPU architectures, we construct strong synchronization objects such as wait-free and$t$-resilientread-modify-writeobjects for a general model of GPU architectures without hardware synchronization primitives such astest-and-setandcompare-and-swap. Accesses to the wait-free objects have time complexity$O(N)$, where$N$is the number of processes. The wait-free objects have the optimal space complexity$O(N^2)$. Our result demonstrates that it is possible to construct wait-free synchronization mechanisms for GPUs without strong synchronization primitives in hardware and that wait-free programming is possible for such GPUs.

The smart home is an environment, where heterogeneous electronic devices and appliances are networked together to provide smart services in a ubiquitous manner to the individuals. As the homes become smarter, more complex, and technology dependent, the need for an adequate security mechanism with minimum individual's intervention is growing. The recent serious security attacks have shown how the Internet-enabled smart homes can be turned into very dangerous spots for various ill intentions, and thus lead the privacy concerns for the individuals. For instance, an eavesdropper is able to derive the identity of a particular device/appliance via public channels that can be used to infer in the life pattern of an individual within the home area network. This paper proposes an anonymous secure framework (ASF) in connected smart home environments, using solely lightweight operations. The proposed framework in this paper provides efficient authentication and key agreement, and enables devices (identity and data) anonymity and unlinkability. One-time session key progression regularly renews the session key for the smart devices and dilutes the risk of using a compromised session key in the ASF. It is demonstrated that computation complexity of the proposed framework is low as compared with the existing schemes, while security has been significantly improved.

Like time complexity models that have significantly contributed to the analysis and development of fast algorithms, energy complexity models for parallel algorithms are desired as crucial means to develop energy efficient algorithms for ubiquitous multicore platforms. Ideal energy complexity models should be validated on real multicore platforms and applicable to a wide range of parallel algorithms. However, existing energy complexity models for parallel algorithms are either theoretical without model validation or algorithm-specific without ability to analyze energy complexity for a wide-range of parallel algorithms. This paper presents a new general validated energy complexity model for parallel (multithreaded) algorithms. The new model abstracts away possible multicore platforms by their static and dynamic energy of computational operations and data access, and derives the energy complexity of a given algorithm from its work, span and I/O complexity. The new model is validated by different sparse matrix vector multiplication (SpMV) algorithms and dense matrix multiplication (matmul) algorithms running on high performance computing (HPC) platforms (e.g., Intel Xeon and Xeon Phi). The new energy complexity model is able to characterize and compare the energy consumption of SpMV and matmul kernels according to three aspects: different algorithms, different input matrix types and different platforms. The prediction of the new model regarding which algorithm consumes more energy with different inputs on different platforms, is confirmed by the experimental results. In order to improve the usability and accuracy of the new model for a wide range of platforms, the platform parameters of ICE model are provided for eleven platforms including HPC, accelerator and embedded platforms.

A smart grid is envisioned as a promising platform for the next-generation power supply network, where the electricity is generated based on the demand from the consumers energy-use information. However, the security and privacy issues over insecure wireless communications are still big obstacles in the success of smart grid networks. In this paper, we present an efficient authentication model in smart grid networks. The proposed model justifies its feasibility with an early test-bed using off-the-shelf 802.15.4 low- cost sensors. Moreover, this poster reports preliminary performance evaluation results, and shows that the proposed scheme is effective and efficient than the prior works.

Ultra-low power (ULP) embedded systems have become popular in the scientific community and industry, especially in media and wearable computing. In order to model ULP systems where energy per instruction can be as low as few pJ, more accurate fine-grained approaches are needed. However, there are no application-general, fine-grained and validated models yet that provide insights into how an application running on an ULP embedded system consumes energy and, particularly, whether the race-to-halt (RTH) strategy that are widely used in high-performance computing (HPC) systems is still applicable to ULP embedded systems. In this study, we propose new RTHpower models which provide insights into how an application consumes energy when running on an ULP embedded system. The models are trained and validated with data from 22 microbenchmarks. The experimental results show that RTH is not always applicable to ULP embedded systems, due to their low static power. RTHpower models support predicting when and when not to use RTH for a given application.

Recent research has suggested that improving fine-grained data-locality is one of the main approaches to improving energy efficiency and performance. However, no previous research has investigated the effect of the approach on these metrices in the case of concurrent data structures.

Like other fundamental abstractions for high-performance computing, search trees need to support both high concurrency and data locality. However, existing locality-aware search trees based on the van Emde Boas layout (vEB-based trees), poorly support concurrent (update) operations.

Humans can interact remotely with each other through computers.Systems supporting this include teleconferencing, games and virtual environments.There are delays from when a human does an action until it is reflected remotely.When delays are too large, they will result in inconsistencies in what the state of the interaction is as seen by each participant.The delays can be reduced, but they cannot be removed.When delays become too large the effects they create on the humanto-human remote interaction can be partially masked to achieve an illusion of insignificant delays.The MultiStage system is a human-to-human interaction system meant to be used by actors at remote stages creating a common virtual stage.Each actor is remotely represented by a remote presence created based on a stream of data continuously recorded about the actor and being sent to all stages.We in particular report on the subsystem of MultiStage masking the effects of delays.The most advanced masking approach is done by having each stage continuously look for late data, and when masking is determined to be needed, the system switches from using a live stream to a pre-recorded video of an actor.The system can also use a computable model of an actor creating a remote presence substituting for the live stream.The present prototype uses a simple human skeleton model.

To interact with a computer, a user can walk up to it and interact with it through its local interaction space defined by its input devices. With multiple computers in a room, the user can walk up to each computer and interact with it. However, this can be logistically impractical and forces the user to learn each computers local interaction space. Interaction involving multiple computers also becomes hard or even impossible to do. We propose to have a global interaction space, letting users, through in-room gestures, select and issue commands to one or multiple computers in the room. A global interaction space has functionality to sense and record the state of a room, including location of computers, users, and gestures, and use this to issue commands to each computer. A prototype has been implemented in a room with multiple computers and a wall-sized large display. The global interaction space is used to issue commands, moving display output from on-demand selected computers to the large display and back again. It is also used to select multiple computers and concurrently execute commands on them.

A user has several personal computers, including mobile phones, tablets, and laptops, and needs to watch live camera feeds from and videos stored at any of these computers at one or more of the others. Industry solutions designed for many users, computers, and videos can be complicated and slow to apply. The user must typically rely on a third party service or at least log in. The Personal Video Distribution (pVD) system supports sending and viewing live and stored videos between any of a single user's computers, and allows for a smooth handover of play back between computers. The system avoids any third parties, and relies only on the user's personal computers. We present the architecture, design and implementation of the pVD prototype. The architecture is comprised of functionality for sending videos, subscribing to videos, and maintaining the video play-back state. The design has a local side sending and viewing videos, and a global side coordinating the switching and distribution of videos, and maintaining subscriptions and video state. The prototype is primarily done in Python. A set of experiments was conducted to document the performance of the prototype. The results show that pVD global side has low CPU usage, and supports a handful of simultaneous exchanges of videos on a wireless network.

Multicore architectures have established themselves as the new generation of computer architectures. As part of the one core to many cores evolution, memory access mechanisms have advanced rapidly. Several new memory access mechanisms have been implemented in many modern commodity multicore architectures. By specifying how processing cores access shared memory, memory access mechanisms directly influence the synchronization capabilities of multicore architectures. Therefore, it is crucial to investigate the synchronization power of these new memory access mechanisms. This paper investigates the synchronization power of coalesced memory accesses, a family of memory access mechanisms introduced in recent large multicore architectures such as the Compute Unified Device Architecture (CUDA). We first define three memory access models to capture the fundamental features of the new memory access mechanisms. Subsequently, we prove the exact synchronization power of these models in terms of their consensus numbers. These tight results show that the coalesced memory access mechanisms can facilitate strong synchronization between the threads of multicore architectures, without the need of synchronization primitives other than reads and writes. In the case of the contemporary CUDA processors, our results imply that the coalesced memory access mechanisms have consensus numbers up to 64.

We introduce a non-blocking full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on may-core architectures. We show that the NB-FEB primitive is universal, scalable and feasible. NB-FEB, together with registers, can solve the consensus problem for an arbitrary number of processes (universality). NB-FEB is combinable, namely its memory requests to the same memory location can be combined into only one memory request, which consequently mitigates performance degradation due to synchronization "hot spots" (scalability). Since NB-FEB is a variant of the original full/empty bit that always returns a value instead of waiting for a conditional flag, it is as feasible as the original full/empty bit, which has been implemented in many computer systems (feasibility).

The fact that graphics processors (GPUs) are today’s most powerful computational hardware for the dollar has motivated researchers to utilize the ubiquitous and powerful GPUs for general-purpose computing. Recent GPUs feature the single-program multiple-data (SPMD) multicore architecture instead of the single-instruction multiple-data (SIMD). However, unlike CPUs, GPUs devote their transistors mainly to data processing rather than data caching and flow control, and consequently most of the powerful GPUs with many cores do not support any synchronization mechanisms between their cores. This prevents GPUs from being deployed more widely for general-purpose computing. This paper aims at bridging the gap between the lack of synchronization mechanisms in recent GPU architectures and the need of synchronization mechanisms in parallel applications. Based on the intrinsic features of recent GPU architectures, we construct strong synchronization objects like wait-free and t-resilient read-modify-write objects for a general model of recent GPU architectures without strong hardware synchronization primitives like test-and-set and compare-and-swap. Accesses to the wait-free objects have time complexity O(N), whether N is the number of processes. Our result demonstrates that it is possible to construct wait-free synchronization mechanisms for GPUs without the need of strong synchronization primitives in hardware and that wait-free programming is possible for GPUs.

This paper aims at bridging the gap between the lack of synchronization mechanisms in recent graphics processor (GPU) architectures and the need of synchronization mechanisms in parallel applications. Based on the intrinsic features of recent GPU architectures, we construct strong synchronization objects like wait-free and t-resilient read-modify-write objects for a general model of recent GPU architectures without strong hardware synchronization primitives like test-and-set and compare-and-swap. Accesses to the new wait-free objects have time complexity O(N), where N is the number of concurrent processes. The wait-free objects have space complexity O(N2), which is optimal. Our result demonstrates that it is possible to construct wait-free synchronization mechanisms for GPUs without the need of strong synchronization primitives in hardware and that wait-free programming is possible for GPUs.

In this paper we examine the general multi-word lock problem, where processes are allowed to multilock arbitrary registers. Aiming for a highly efficient solution we propose a randomized algorithm which successfully breaks long dependency chains, the crucial factor for slowing down an execution. In the analysis we focus on the 2-word lock problem and show that in this special case an execution of our algorithm takes with high probability at most time O( ∆ 3 log n / log log n), where n is the number of registers and ∆ the maximal number of processes interested in the same register (the contention). Furthermore, we implemented our algorithm for the general multi-word lock problem on an SGI Origin2000 machine, demonstrating that our algorithm is not only of theoretical interest.