Talk Titles and Abstracts

Please click on each title to see the related slides

 

Invited Speaker: Yehuda Afek, Tel-Aviv University, Israel

Title: Programming with Hardware Lock Elision

Abstract: We present a simple yet effective technique for improving performance of lock-based code using the hardware lock elision (HLE) feature in Intel’s upcoming Haswell processor. We also describe how to extend Haswell’s HLE mechanism to achieve a similar effect to our lock elision scheme entirely in hardware.

 

Invited Speaker: Carole Delporte and Hugues Fauconnier, Université Paris Diderot - Paris 7 (France)

Title: Some results with MWMR registers

Abstract: What is the number of registers required to solve a task? Many years ago, Ellen and al. have proved a lower bound of square root of n registers to (obstruction free) solve the consensus, but today there is no known consensus algorithm using less than n registers. In a system of n processes, if each process has its own SWMR register, it is possible to emulate any number of registers, but what  of tasks can be solved with less than n registers?

Before considering this question, what’s happens when we only have MWMR registers? A trivial way may be to assign each process one MWMR: given an array C of MWMR registers, C[i] will be assigned to process i. But if the n processes have ids drawn from a very large set of N identifiers, the size of C depends on N not on n. Renaming algorithms may help but they use a non linear (on n) number of MWMR registers.

We give a solution without renaming that implements for each process a SWMR register using only n MWMR registers. This implementation is only non-blocking, but we get with 2(n-1) MWMR a wait-free implementation.  Moreover we prove that n is a lower bound to such implementation. We also prove that n MWMR registers are sufficient to solve any wait-free task solvable with any number of (MWMR or SWMR) registers.

If the number of MWMR is less than n, we prove that some tasks may nevertheless been (obstruction-free) solved. For example, we prove  that 2 registers are necessary and sufficient to (Obstruction-Free) solve the set-agreement problem.

This a joint work with C. Delporte, H. Fauconnier, E. Gafni and S. Rajbaum. A recent extension to the adaptive case has been made jointly with L. Lamport.

 

Invited Speaker: Shlomi Dolev, Ben Gurion University (Israel)

Title: Online Secure Multiparty Computations Over Public Clouds

Abstract: The talk summarizes several recent works in which a dealer wants to delegate a computation to processes in the cloud by sending them stream of inputs. The dealer is able to harvest the result by collecting the states of the processes at any given time, while processes have limited or no information concerning the current state of the computation. In particular the following solutions will be described:

- Reactive secret sharing, that changes the secret according to unbounded sequence of common inputs, where no communication among the (dynamic set of) participants is allowed, a fully secure solution for simple functions but somewhat non perfectly secure solution for any function.

- Dynamic online multiparty computation, in which a dynamic group of participants that should not know the sequence of inputs they process nor the program computed. The solution is based on a secret share based implementation of oblivious Turing machine.

- Infinite execution with no communication among the participants where the input is revealed to all participants. We prove that any automaton can be executed without revealing any information concerning the current state of the automaton. The construction is based on Krohn-Rhodes decomposition technique. Using pseudo random sequence, we present a simpler efficient technique for securing the current state of the automaton.

- Sring matching in which both the inputs and the state are information theoretically secure.

(Joint works with Limor Lahiani, Moti Yung, Juan Garay, Niv Gilboa and Vladimir Kolesnikov, Yelena Yuditski)

 

Invited Speaker: Faith Ellen, University of Toronto (Canada)

Title: An Optimal Implementation of Fetch-and-Increment

Abstract: We present a new wait-free implementation of a fetch-and increment object shared by n processes from read-write registers and load-linked/store-conditional objects. The step complexity of each operation is O(log n), which is optimal. Our implementation uses O(n) objects, each of which stores O(log max{m,n}) bits, where m is the number of fetch-and-increment operations that are performed. This also gives a new algorithm for strong renaming of processes whose original names are from a universe of size n. Our implementation uses a new object, called a buffer. It supports an operation which, if successful, puts a value into its input area that can depend on the value that is currently there, an operation that copies the value in its input area to its output area, provided its output area is empty, and an operation that empties its output area. We show a buffer can be implemented from a small constant number of load-linked/store-conditional objects so that all three operations have constant step complexity. This is joint work with Philipp Woelfel.

 

Invited Speaker: Pascal Felber, Université de Neuchâtel (Switzerland)

Title: Optimistic Synchronization and the Natural Degree of Parallelism of Concurrent Applications

Abstract: Transactional memory (TM) provides a scalable and easy-to-use alternative to locks. One of the key results highlighted by previous research is that, independently of the nature of the synchronization scheme adopted by a TM platform, its actual performance is strongly workload-dependant and affected by a number of complex, often intertwined factors (e.g., duration of transactions, level of data contention, ratio of update vs. read-only transactions). In this talk, we will explore the assumption that most workloads have a natural degree of parallelism, i.e., there is a workload-specific threshold below which adding more threads will improve transaction throughput, and over which new threads will not help and might even degrade performance because of higher contention and aborts rates, even if sufficiently many cores are available. We discuss techniques to dynamically identify the "best" degree of parallelism that should be used for a given application.

 

Invited Speaker: Rachid Guerraoui, EPFL (Switzerland)

Title: Generalized Universality

Abstract: Replicated state machine is a fundamental computing construct for it essentially makes a distributed system emulate a, highly available, centralized one using a consensus abstraction through which processes agree on common decisions. The idea is at the heart of the fault-tolerance of most data centers today. Any sequential object is modeled by a state machine that can be replicated over all processes of the system and accessed in a wait-free manner: we talk about the universality of the construct and of its underlying consensus abstraction. Yet, consensus is just a special case of a more general abstraction, k-set consensus, where processes agree on at most k different decisions. It is natural to ask whether there exists a generalization of state machine replication with k-set agreement, for otherwise distributed computing would not deserve the aura of having an underpinning Theory as 1 (k-set consensus with k=1) would be special. The talk will recall the classical state machine replication construct and show how, using k-set consensus as an underlying abstraction, the construct can be generalized to implement k state machines of which at least one makes progress, generalizing in a precise sense the very notion of consensus universality. Joint work with Eli Gafni.

 

Invited Speaker: Maurice Herlihy, Brown University (USA)

Title: Type-Specific Synchronization for Software Transactional Memory

Abstract: Software transactional memory (STM) is intended to make concurrent programs easier to design, implement, and reason about. STM is supported, either directly or through libraries, by an increasing number of languages and compilers, such as GNU C++, Clojure, Haskell, Java, Scala, and others. Perhaps inspired by databases, most STM synchronization and recovery mechanisms work by classifying operations as reads or writes. We argue that such an approach is unlikely to scale, especially for highly-contended "hot-spot" objects. As an alternative, we describe "transactional boosting", a technique for making highly-concurrent thread-safe data structures transactional. As long as the thread-safe implementation satisfies certain regularity properties (informally, that every method has an inverse), we define a simple wrapper transformation that that concurrent transactions without inherent conflicts can synchronize at the same granularity as the original thread-safe implementation.

 

Invited Speaker: Anne-Marie Kermarrec, INRIA - Rennes Campus (France)

Title: Systems support for news recommendation: from P2P to hybrid architectures

Abstract: The ever-growing amount of information available on the Internet can only be handled with appropriate personalization.  One of the most appealing ways to filter content matching users' interests and achieve efficient personalized recommendation is collaborative filtering (CF). Yet, CF systems are notoriously resource greedy. 

In this talk, we will first present a collaborative filtering system for disseminating news items in a large-scale dynamic setting with no central authority. WhatsUp constructs an implicit social network based on user profiles that express the opinions of users about the news items they receive (\textit{like-dislike}). Users with similar tastes are clustered using a similarity metric reflecting long-standing and emerging (dis)interests.  News items are disseminated through a novel heterogeneous gossip protocol that (1) biases the orientation of its targets towards those with similar interests, and (2) amplifies dissemination based on the level of interest in every news item. We will then explore a novel scheme and present DREC an online cost-effective scalable architecture for CF personalization. combining the manageability of centralized solutions with the scalability of decentralization.

 

Invited Speaker: Euripides Markou, University of Central Greece (Greece)

Title: Exploration of Networks Containing Malicious Hosts

Abstract: In distributed mobile computing environments one of the most pressing concerns is security. Two are the most important security threats: a malicious mobile process which can move along the network and a stationary harmful process which resides at a host. One of the most studied models for stationary harmful processes is the black hole which has been introduced by S. Dobrev, P. Flocchini, G. Prencipe and N. Santoro in 2001. A black hole is a harmful node in the network that destroys any mobile agent visiting that node without leaving any trace. The objective of the Black Hole Search problem is to identify the black hole without destroying too many agents and the main effort is to discover the minimal hypotheses under which it can be solved. The problem had been initially investigated in asynchronous networks and introduced later in synchronous networks. Recently it has been investigated in synchronous networks under very weak models (e.g., using agents with only constant m emory) in which it is unsolvable in asynchronous networks. We will present some main results and algorithmic techniques and we will discuss the case when the malicious host has byzantine behavior and can also alter the memory of a visiting agent.

 

Invited Speaker: Maged Michael, IBM Thomas J. Watson Research Centre (USA)

Title: Practical Trade-offs in Non-Blocking Design

Abstract: Practical uses of non-blocking operations--such as signal safety, kill safety, and soft real-time response--typically involve the careful balancing and compromise among often contradictory features of a heterogeneous collection of operations. Some of the issues and features are the mix of operations, expected data sizes, expected lifetimes of data structures, interaction with blocking operations, expected update frequencies, interaction between reading and writing operations, memory management, hardware support, memory ordering, and programming language support. This talk explores the various characteristics of non-blocking operations, their intertwining implications, and the process for disentangling contradictory characteristics and recognizing when compromise in necessary to ultimately achieve practical designs.

 

Invited Speaker: Eliot Moss, University of Massachusetts (USA)

Title: Semantically Correct Concurrency Control for Transactions

Abstract: Techniques such as open nesting and blocking aim to increase concurrency among transactions to the maximum possible that is consistent with transaction atomicity and isolation.  I will describe correct concurrency control using abstract locks, which capture the fundamental commutativity of operations on an abstraction, and can be used for both pessimistic and optimistic concurrency control.  I will include a number of examples, including cases such as data types with iterators.

 

Invited Speaker: Michel Raynal, University of Rennes I (France)

Title: Shared memory synchronization despite failures: a few exercices

Abstract: In the recent past, lots of papers have addressed synchronization in asynchronous shared memory systems prone to process crashes. This aim of this talk is to give a flavor of a few of these fundamental results. To that end, it considers three problems and presents solutions proposed to solve them, emphasizing the basic concepts and techniques these solutions rely on. These problems have been selected because they address distinct facets of synchronization in presence of failures. So, the spirit of this introductory talk is mainly pedagogical (with an algorithmic taste).

 

Invited Speaker: Eric Ruppert, York University (Canada)

Title: A General Technique for Non-blocking Trees

Abstract: We describe a general method for obtaining non-blocking implementations of a large class of tree structures where pointers are directed from parents to children. Our construction uses LLX and SCX operations, which are multi-word generalizations of the standard LL (load-link) and SC (store-conditional) operations. These operations are, in turn, implemented from single-word CAS instructions. A non-blocking implementation of a balanced search tree will be described as an example. Its height is guaranteed to be O(log n + c), where n is the number of keys stored in the tree and c is the number of incomplete update operations. (joint work with Trevor Brown and Faith Ellen)

 

Invited Speaker: Assaf Schuster, Technion (Israel)

Title: On-the-Fly Monitoring of Big, Distributed, Streaming Data

Abstract: More and more tasks require efficient processing of continuous queries over scalable, distributed data streams. Examples include optimizing systems using their operational log history, mining sentiments using sets of crawlers, and data fusion over heterogeneous sensor networks. However, distributed mining and/or monitoring of global behaviors can be prohibitively difficult. The naïve solution which sends all data to a central location mandates extremely high communication volume, thus incurring unbearable overheads in terms of resources and energy. Furthermore, such solutions require expensive powerful central platform, while data transmission may violate privacy rules. An attempt to enhance the naïve solution by periodically polling aggregates is bound to fail, exposing a vicious tradeoff between communication and latency. Given a continuous global query, the solution proposed in the talk is to generate filters, called safe zones, to be applied locally at each data stream. Essentially, the safe zones represent geometric constraints which, until violated by at least one of the sources, guarantee that a global property holds. In other words, the safe zones allow for constructive quiescence: There is no need for any of the data sources to transmit anything as long as all constraints are held with the local data confined to the local safe zone. The typically-rare violations are handled immediately, thus the latency for discovering global conditions is negligible. The safe zones approach makes the overall system implementation, as well as its operation, much simpler and cheaper. The saving, in terms of communication volume, can reach many orders of magnitude. The talk will describe a general approach for compiling efficient safe zones for many tasks and system configurations.

 

Invited Speaker: Nir Shavit, MIT Computer Science and Artificial Intelligence Laboratory (USA)

Title: The Future of HyTM

Abstract: With the advent of hardware transactional memory (HTM) in upcoming Intel and IBM processors, there is a need for novel hybrid transactional memory (HyTM) approaches to allow a best effort attempt to execute transactions in hardware, yet always fall back to slower software transactions in order to provide better progress guarantees and the ability to execute various protected instructions. In my talk I will survey the state of the art in HyTM design, from the first HyTM algorithms to today's mixed hardware-software slow paths. 

 

Invited Speaker: Liuba Shrira, Brandeis University (USA)

Title: ACID transactions and modularity in distributed systems

Abstract: ACID transactions are a classical tool that makes it easier to develop applications that operate correctly in the presence of failures and concurrency. Implementing a high-performance ACID transaction system for a data store is challenging. A complex  internal data store component, the storage manager, consisting of interacting recovery and concurrency subsystems has to be carefully engineered and tuned to achieve good performance. A known limitation of high-performance transaction systems has been the lack of flexibility.  For example, there was no way to add a new concurrency control scheme to exploit the semantics of a new application, or to add useful functionality such as snapshots, without invasive, potentially destabilizing modifications of the data store internals. This talk will present techniques  for extending high-performance transactional systems in a modular way, without invasive modifications to data store internals. 

 

Invited Speaker: Gadi Taubenfeld, Interdisciplinary Center (Israel)

Title: A Closer Look at Fault Tolerance

Abstract: The traditional notion of fault tolerance requires that all the correct participating processes eventually terminate, and thus, is not sensitive to the number of correct processes that should  properly terminate as a result of failures. Intuitively, an algorithm that in the presence of any number of faults always guarantees that all the correct processes except maybe one properly terminate, is more resilient to faults than an algorithm that in the presence of a single fault does not even guarantee that a single correct process ever terminates. However, according to the standard notion of fault tolerance both algorithms are classified as algorithms that cannot tolerate a single fault. We generalize the traditional notion of fault tolerance in a way which enables to capture more sensitive information about the resiliency of an algorithm.

It is well known that, in asynchronous systems where processes communicate either by reading and writing atomic registers or by sending and receiving messages, important problems such as, consensus, set-consensus, election, perfect renaming, implementations of a test-and-set bit, a shared stack, a swap object and a fetch-and-add object have no deterministic solutions which can tolerate even a single fault. We show that while, some of these problems have solutions which guarantee that in the presence of any number of faults most of the correct processes will properly terminate; other problems do not even have solutions which guarantee that in the presence of just one fault at least one correct process properly terminates. If time permits, I will also discuss an idea of how to design algorithms that provide some level of resiliency against memory reordering.

 

Invited Speaker: Theo Ungerer, University of Augsburg, Germany

Title: Parallelisation of Industrial Software for Hard Real-time Systems

Abstract: Providing higher performance than state-of-the-art embedded processors can deliver today will increase safety, comfort, number and quality of services, while also lowering emissions as well as fuel demands for automotive, avionic and automation applications. Such a demand for increased computational performance is widespread among European key industries. Engineers who design hard real-time embedded systems in such embedded domains express a need for several times the performance available today while keeping safety as major criterion. A breakthrough in performance is expected by parallelising hard real-time applications and running them on an embedded multi-core processor, which enables combining the requirements for high-performance with time-predictable execution.
The talk will discuss the parallelisation of industrial hard real-time software to yield timing analysable parallel hard real-time applications running on a scalable many-core processor. We present preliminary results of the EC FP-7 project parMERASA (Multi-Core Execution of Parallelised Hard Real-Time Applications Supporting Analysability, 2011-2014) where application companies of avionics, automotive, and construction machinery domains cooperate with tool developers and multi-core architects. Timing predictable synchronization of parallel hard real-time tasks is one major challenge in this research. We propose an approach to apply transactional memory (TM) for mixed criticality systems that allows tasks of different criticality to share data while providing timing guarantees for the high critical tasks.

 

Invited Speaker: Pawel T. Wojciechowski, University of Poznan (Poland)

Title: Optimistic, Pessimistic, and Futures-based Transactions

Abstract: Transactional memory, an approach aiming to replace cumbersome locking mechanisms in concurrent systems, has become a popular research topic. But due to problems posed by irrevocable operations (e.g., system calls), the viability of pessimistic (or hybrid) concurrency control for transactional memory systems is being explored, in lieu of the more typical optimistic approach. In this talk, I will discuss the semantics of optimistic and pessimistic transactions, and propose future-based rollback-capable transactions---a novel concept that combines pessimistic transactions with futures (or promises) known from functional programming languages. Futures enable to parallelize operations executed by transactions, as in the optimistic approach, but without the need to worry about problems caused by forced aborts. In a distributed setting, future-based transactions can also tolerate network partitions.