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é)