Lock-Free Algorithms

In distributed systems where many processes access shared data, locks are often used to ensure that processes cannot simultaneously perform updates on the same part of the data. This approach has disadvantages: lack of fault-tolerance, fast processes having to wait for slower ones, and reduced parallelism. Lock-free algorithms avoid these problems while maintaining data consistency. The groups work on this project is done in collaboration with researchers from EPFL, the Technion, the University of Crete and the University of Toronto.

Lock-free Data Structure Implementations

Graduate students Mikhail Fomitchev and Niloufar Shafiei have worked on the design of lock-free, distributed implementations of fundamental data structures, such as linked lists, skip lists and stacks for shared-memory systems. Many other data structures remain to be explored. Another interesting challenge is the automatic verification of these implementations of data structures.

Snapshots

A snapshot object allows processes to obtain a consistent view of a shared array, even when other processes are simultaneously updating components of the array. Snapshots are an abstraction of several important problems, including making backups to facilitate error-recovery and obtaining simultaneous readings from a collection of sensors. The group's work on this problem includes new algorithms and also complexity lower bounds.

Anonymous Distributed Systems

It is important to understand how the assumptions made in modelling distributed systems influence the results that can be proved using those models. One frequently made assumption is that each process has a unique name (or id). However, unique ids are not available, or processes may not want to divulge their ids (for reasons of privacy). How does the absence of ids affect the power of the model to solve problems?