CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Algorithms for synchronization and consistency in concurrent system services

Anders Gidenstam (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers))
Göteborg : Chalmers University of Technology, 2006. ISBN: 91-7291-832-2.- 238 s.
[Doktorsavhandling]

Synchronization, consistency and scalability are important issues in the design of concurrent computer system services. In this thesis we study the application of optimistic and scalable methods in concurrent system services. In a distributed setting we study scalable tracking of the causal relations between events, lightweight information dissemination in optimistic causal order in distributed systems and fault-tolerant and dynamic resource sharing. Further, we study scalable memory allocation, memory reclamation, threading, thread synchronization and data structures in shared memory systems. For each of the services we study we give the design of algorithms using optimistic methods, assess the correctness and analyze the behaviour of the algorithm, and in most cases describe implementations and perform experimental studies comparing the proposed algorithms to “traditional” approaches. We present a study of the accuracy of plausible timestamps for scalable event tracking in large systems. We analyze how these clocks may relate causally independent event pairs and based on the analysis we propose two new clock algorithms to satisfy the analysis criteria. We propose an information dissemination service providing optimistic causal order called lightweight causal cluster consistency. It offers scalable behaviour, low message size overhead and highprobability reliability guarantees for e.g. multi-peer collaborative applications. A key component in the dissemination service is a dynamic and fault-tolerant cluster management algorithm, which manages a set of tickets/resources such that each ticket has at most one owner at a time. In the dissemination service this algorithm manages senders and enables the use of small fixed size vector clocks. We present a lock-free concurrent memory allocator, NBmalloc, designed to enhance performance and scalability on multiprocessors which also shows in our experimental evaluation. We present a lock-free memory reclamation algorithm for use in the implementation of lock-free data structures. Our algorithm is the first practical one that has all the following features: (i) guarantees the safety of local as well as global references, (ii) provides an upper bound of deleted but not yet reclaimed nodes, (iii) is compatible with standard memory allocation schemes. We also present LFthreads, a user-level thread library that is implemented entirely using lock-free methods aiming for increased scalability and efficiency over traditional thread libraries.

Nyckelord: synchronization, logical clocks, plausible clocks, time stamping system, event ordering, group communication, optimistic causal order, nonblocking, lock-free, memory management, memory reclamation, threading, atomic registers.



Denna post skapades 2006-09-05. Senast ändrad 2013-09-25.
CPL Pubid: 22272

 

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers) (2005-2007)

Ämnesområden

Datalogi

Chalmers infrastruktur

Relaterade publikationer

Inkluderade delarbeten:


Adaptive Plausible Clocks


Multi-word Atomic Read/Write Registers on Multiprocessor Systems


Allocating memory in a lock-free manner


Dynamic and fault-tolerant cluster management


LFthreads: A lock-free thread library or "Blocking without locking"


Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting


Lightweight Causal Cluster Consistency


Examination

Datum: 2006-09-25
Tid: 10.15
Lokal: 10.15 EC, EDIT-huset, Rännvägen 6B, Chalmers.
Opponent: Professor, Evangelos Kranakis, School of Computer Science, Carleton University, Ottawa, Canada

Ingår i serie

Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie 2514


Technical report D - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University 20D