20 April 2018

Séminaire DALGO : « The Synchronization Power of Atomic Bitwise Operations », Damien Imbs

Bitwise AND, OR and XOR operations are very widely used, but have received little attention in the distributed setting. Because bitwise operations are available in most modern processors, they can constitute a valuable tool for synchronization in distributed systems. It is then natural to consider the level of synchronization that these operations can achieve. A shared AND/OR register consists of an array of x bits and offers three atomic operations: AND and OR operations, which take an array of x bits as parameter and change the state of the register by applying the corresponding bitwise operation, and a read operation which returns the content of the array. A shared AND/OR/XOR register additionally offers a XOR operation. After introducing shared AND/OR and AND/OR/XOR registers, this talk will exhibit their synchronization power by determining their consensus number, that is, the maximum number of processes that can solve wait-free consensus using these objects.
20 April 2018, 10h3011h30
salle de réunion du LIS, Luminy (Préfabriqué)

Prochains évènements

Retour à l'agenda
03 May 2018

Séminaire MOVE : "Costs and Rewards in Priced Timed Automata", Mahsa Shirmohammadi (LIS)

We consider Pareto analysis of reachable states of multi-priced timed automata (MPTA): timed automata equipped with multiple observers that keep track of costs (to be minimised) and rewards (to be maximised) along a computation. Each observer has a constant non-negative derivative which may depend on the location of the MPTA. We study the Pareto Domination Problem, which asks whether it is possible to reach a target location via a run in which the accumulated costs and rewards Pareto dominate a given objective vector. We show that this problem is undecidable in general, but decidable for MPTA with at most three observers. For MPTA whose observers are all costs or all rewards, we show that the Pareto Domination Problem is PSPACE-complete. We also consider an ε-approximate Pareto Domination Problem that is decidable without restricting the number and types of observers. We develop connections between MPTA and Diophantine equations. Undecidability of the Pareto Domination Problem is shown by reduction from Hilbert’s 10th Problem, while decidability for three observers is shown by a translation to a fragment of arithmetic involving quadratic forms.