NDLI: CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory

Please wait, while we are loading the content...

Distributed computation of the mode

Anti-Ω: the weakest failure detector for set agreement

Collaborative enforcement of firewall policies in virtual private networks

On the complexity of asynchronous gossip

On a capacitated multivehicle routing problem

Flooding time in edge-Markovian dynamic graphs

Distributed algorithms for ultrasparse spanners and linear size skeletons

New combinatorial topology upper and lower bounds for renaming

Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing

Asynchronous exclusive selection

Forget him and keep on moving

BMobi_Causal: a causal broadcast protocol in mobile dynamic groups

A fast distributed slicing algorithm

A tradeoff analysis on message complexity and lifetime optimality for a distributed multicast algorithm in WSNs

Greedy distributed optimization of unsplittable multicommodity flows

Quantum distributed consensus

Optimizing consistency checking for memory-intensive transactions

The lotus-eater attack

Evolution of distributed computing theory: from concurrency to networks and beyond

Beyond nash equilibrium: solution concepts for the 21st century

Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition

Failure detectors in loosely named systems

Secure communication over radio channels

Brahms: byzantine resilient random membership sampling

Improved compact routing schemes for dynamic trees

On the effect of the deployment setting on broadcasting in Euclidean radio networks

Efficient distributed approximation algorithms via probabilistic tree embeddings

Timeliness-based wait-freedom: a gracefully degrading progress condition

The impact of randomization in smoothing networks

Fast self-stabilizing byzantine tolerant digital clock synchronization

Online and dynamic embeddings of approximate ultrametrics

Correctness criteria for replicated database systems with snapshot isolation replicas

A dynamic exchange game

Nearest-neighbor graphs on random point sets and their applications to sensor networks

Stateless distributed algorithms for near optimal maximum multicommodity flows

Looking for the optimal conditions for solving set agreement

Wait-free programming for general purpose computations on graphics processors

Extracting models from design documents with mapster

A world of (Im) possibilities

The internet is flat: a brief history of networking in the next ten years

A log-star distributed maximal independent set algorithm for growth-bounded graphs

Every problem has a weakest failure detector

On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

Tight bounds for delay-sensitive aggregation

Virtual infrastructure for collision-prone wireless networks

On the locality of distributed sparse spanner construction

Lower bounds for randomized consensus under a weak adversary

Optimizing data popularity conscious bloom filters

OCD: obsessive consensus disorder (or repetitive consensus)

Dynamic routing and location services in metrics of low doubling dimension

The asynchronous bounded-cycle model

Anonymous and censorship resistant content sharing in unstructured overlays

From anarchy to geometric structuring: the power of virtual coordinates

Distributed averaging in the presence of a sparse cut

Tight RMR lower bounds for mutual exclusion and other problems

Transactional memory retry mechanisms

Efficient single phase unconditionally secure message transmission with optimum communication complexity

The power of simulation relations

Accountability for distributed systems

A jamming-resistant MAC protocol for single-hop wireless networks

Sharing is harder than agreeing

CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory

Bounded budget connection (BBC) games or how to make friends and influence people, on a budget

The forgiving tree: a self-healing distributed data structure

Sleeping on the job: energy-efficient and robust broadcast for radio networks

The stretched exponential distribution of internet media access patterns

Randomized consensus in expected O(n log n) individual work

Distributed order scheduling and its application to multi-core dram controllers

An almost-surely terminating polynomial protocol for asynchronous byzantine agreement with optimal resilience

On ad hoc routing with guaranteed delivery

Model checking transactional memory with spin

Our brothers' keepers

Balancing energy consumption for uniform data gathering wireless sensor networks

Gossip-based aggregate computation: computing faster with non address-oblivious schemes

Closing the complexity gap between mutual exclusion and FCFS mutual exclusion

Scheduling tasks with dependencies on asymmetric multiprocessors

Mobile proactive secret sharing

On fault tolerance and wireless networks

On the internet delay space dimensionality

On the robustness of (semi) fast quorum-based implementations of atomic shared memory

Distributed churn measurement in arbitrary networks

Scheduling sensors by tilinglattices

Snap-stabilization in message-passing systems

Fault-tolerant implementations of atomic registers by safe registers in networks

The future of distributed computing: renaissance or reformation?

Maximizing quorum availability in multi-clustered systems

Principles of untrusted storage: a new look at consistency conditions

Efficient pipeline configuration in distributed heterogeneous computing environments

Power management of devices: when should i switch off?

Dynamic service assignment in mobile networks: the magma approach

Optimal failure detection with low sporadic overhead and communication locality

CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory

Content Provider	ACM Digital Library
Author	Suissa, Adi Dolev, Shlomi Hendler, Danny
Abstract	Transactional memory (TM) is a key concurrent programming abstraction. Several software-based transactional memory (STM) implementations have been developed in recent years. All STM implementations must guarantee transaction atomicity but different STM implementations may provide different progress guarantees. In order to ensure progress, an STM implementation must resolve transaction conflicts. This is done either by the implementation itself or by delegating conflict resolution to a separate contention manager module that tries to resolve transaction collisions once they are detected. We present CAR-STM, a scheduling-based mechanism for STM Collision Avoidance and Resolution, that can be incorporated into existing STM implementations. CAR-STM maintains per-core transaction queues and schedules a thread while it is performing a transaction. CAR-STM employs the following two novel collision reduction techniques: (1) seriailizing contention managers resolve conflicts by aborting one transaction and moving it to the transactions queue of the other, effectively serializing the execution of these transactions and ensuring they will not collide again. (2) Proactive collision reduction allows applications to provide information about transactions' collision-probability. CAR-STM uses this information to pre-assign transactions that are more likely to collide to the same core. We have incorporated CAR-STM into the University of Rochester's STM (RSTM) and compared the performance of the new implementation with that of the original RSTM by using STMBench7. Our results show that the new implementation provides orders-of-magnitude reduction of execution times and improved throughput for almost all concurrency levels. Additionally, since CAR-STM greatly reduces the unpredictable influence of operating-system scheduling on STM performance, the new implementation provides a much more stable performance. In contrast, the performance of the original RSTM implementation on STMBench7 workloads exhibits extremely high variance. Though our paper focuses on software transactional memory, we believe the ideas introduced by CAR-STM may prove useful also for hybrid implementations of transactional memory.
Starting Page	125
Ending Page	134
Page Count	10
File Format	PDF
ISBN	9781595939890
DOI	10.1145/1400751.1400769
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-08-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Contention management Scheduling Synchronization Collision avoidance and reduction Transactional memory
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in