Vincent Gramoli

• 2^nd Workshop on the Theory of Transactional Memory in conjunction with DISC 2010 will be advertised soon.
• Workshop on New Topics in Distributed Algorithms.
• Combining elastic transactions with normal ones: ε-STM.
• The summary of the 1^st Workshop on the Theory of Transactional Memory in conjunction with DISC 2009 is here!

Transactional Memory. During 30 years, sequential processors have kept speeding up almost twice a year. New trend is to multiply the number of processors (cores) on the same chip and no longer their speed. Transactional memory (TM) has been recently proposed as a parallel programming paradigm well-suited for multicore architecture and simple to reason with. Transactions in the context of database differ from these new transactions due to the constraints imposed by upcoming multicore architecture. While the former transactions were bufferized on server-side in traditional database systems, the latter ones are now executed as fast as possible by cores. Nevertheless, this programming paradigm suffers severe limitations. Among these problems we formalize and test the workload of TMs to evaluate their Input Acceptance and we aim at enhancing concurrency whitout precluding programming simplicity (cf. Elastic transactions).

Distributed Slicing. The distributed slicing is a refinement of the notion of super-peers election, where each peer must determine how super it is. In a system where each node has an attribute value (representing some resource or capacity), the distributed slicing problem is for each node to determine the slice/portion of the system its attribute value belongs to. For example, given k equally sized slices, the problem is solved if and only if every node knows precisely to which slice Si (0 < i <= k) of the system it belongs to, where slice Si represents the portion of nodes with the i^th highest attribute values. From a theoretical point of view if k=n, the problem is similar to the quantile finding problem where each node must find the quantile its attribute value corresponds to. More information.

Dynamic Storage. I investigated solutions for atomic memory in wide-scale and unstructured systems, typically like Peer-to-Peer (P2P) systems. In such systems, where the total number of participants is unknown, each participant acts on its own and can leave the system at will. The first approach was to define a replaceable quorum system, called RAMBO, then we integrated the reconfiguration process to make it more fault tolerant and we obtain RDS. Moreover, we investigated overlays that cope with high dynamism to define scalable quorum systems, as in SAM (Self-* Atomic Memory) and SQUARE. Finally, we defined Timed Quorum System that relaxes invariants with timely requirements to cope with dynamism efficiently. The result is available here: TQS.