37th International Conference on Current Trends in Theory and Practice of Computer Science

Invited speakers of SOFSEM 2011

Christian Cachin (IBM Research)

Title: Integrity and Consistency for Untrusted Services

Abstract: A group of mutually trusting clients outsources an arbitrary computation service to a remote provider, which they do not fully trust and that may be subject to attacks. The clients do not communicate with each other and would like to verify the integrity of the stored data, the correctness of the remote computation process, and the consistency of the provider’s responses. We present a novel protocol that guarantees atomic operations to all clients when the provider is correct and fork-linearizable semantics when it is faulty; this means that all clients which observe each other’s operations are consistent, in the sense that their own operations, plus those operations whose effects they see, have occurred atomically in same sequence. This protocol generalizes previous approaches that provided such guarantees only for outsourced storage services.


Markus Gross (ETH Zurich)

Title: Visualization based on physical and geometric modeling.


Juerg Gutknecht (ETH Zurich)

Title: Hardware/ software codesign at work

Abstract: Embedded systems are by far the most important class of computerized devices. 8.8 billions out of 9 billions of processors fabricated in 2005 went into embedded devices. New technologies like manycore and programmable hardware and their combination will decisively influence both the architecture of future embedded systems and the way how they are built. As an exemplary case study, we shall discuss our work within a Microsoft Innovation Cluster in Embedded Software Development. In particular, we shall present our approach based on an ingenious combination of hardware/ software compilation.


Tony Hey (Microsoft)

Title: The Fourth Paradigm: Data-Intensive Science

Abstract: We live in an era in which scientific discovery is increasingly driven by data exploration and often occurs within a data explosion. Scientists today are envisioning diverse data analyses and computations that scale from the desktop to supercomputers, yet often have difficulty designing and constructing software architectures to accommodate the heterogeneous and often inconsistent data at scale. Moreover, scientific data and computational resource needs can vary widely over time. The needs grow as the science collaboration broadens or as additional data is accumulated; the computational demand can have large transients in response to seasonal field campaigns or new instrumentation breakthroughs. Cloud computing can offer a scalable, economic, on-demand model well-matched to some of these evolving science needs. This talk presents two of our experiences over the last year – the TeraPixel Project, using workflow, HPC and non-SQL data processing to render the largest astronomical image for WorldWide Telescope, and MODISAzure, a science pipeline for image processing, deployed using the Azure Cloud infrastructure.


Rainer Koschke (University of Breman)

Title: Begun the Software Clone War has

Abstract: Software clones are duplicated code fragments resulting from copy-and-paste reuse of source code. Clones lead to redundancy in programs with the problem of potential update anomalies. Despite of their potentially negative impact, software clones are a frequent phenomenon in practice as several studies show. For these reasons, research has investigated ways to detect and remove or otherwise treat clones. Moreover, researchers have investigated their reasons and their true effects on maintainability.

This talk summarizes the state of the art in software clones research. It summarizes the existing body of knowledge and highlights open issues directing at future research.


Ulrich Rührmair (TU Munich)

Title: Physical Cryptography, Or: How to Realize Cryptography and Security by Random, Disordered, and Unclonable Physical Structures

Abstract: The use of disordered micro- or nanoscale physical structures for cryptographic and security purposes has recently gained some interest in the community. Wherever applicable, the employment of such structures has some potential advantages: First, it can avoid permanent digital secret keys in vulnerable hardware, promising to make the resulting systems more resilient against malware and invasive attacks. Second, it can allow cryptographic protocols whose security does not rest on the usual unproven number theoretic assumptions like factoring and discrete log, creating and independent fundament for cryptography. Physical Unclonable Functions or PUFs are certainly the best known representative of this new class of “disordered” cryptoprimitives, but there are also others. In this talk, we will try to survey and categorize the existing work in the area, but will also include a discussion of some new ideas (such as Virtual Proofs of Reality) and of the main future challenges in the field.

Vitaly Shmatikov (University of Texas at Austin)

Title: Anonymity and Data Privacy: Yesterday, Today, and Tomorrow

Abstract: The Internet economy relies on the collection and aggregation of personal data on an ever-increasing scale. Information about our tastes, purchases, searches, browsing history, social relationships, health history, genetics, and so forth is shared with advertisers, marketers, and researchers, who use it to predict individual behavior and provide personalized product offerings, recommendations, and even clinical treatments. I will survey privacy issues caused by massive aggregation of personal information. After demonstrating that the existing methods for "anonymizing" the data fail to provide meaningful privacy protection, I will describe new approaches to privacy-preserving computation. This includes Airavat, a new system for large-scale data analysis which integrates mandatory access control and differential privacy.

Jiri Srba (Aalborg University)

Title: Verification of Timed-Arc Petri Nets

Abstract: Timed-Arc Petri Nets (TAPN) are an extension of the classical P/T nets with continuous time. Tokens in TAPN carry an age and arcs between places and transitions are labelled with time intervals restricting the age of tokens available for transition firing. The TAPN model posses a number of interesting theoretical properties distinguishing them from other time extensions of Petri nets. In this talk, I will give an overview of the recent theory developed in the verification of TAPN extended with features like read/transport arcs, timed inhibitor arcs and age invariants. I will focus on the boundaries of automatic verification and the connections between TAPN and the model of timed automata. Finally, I will give a demonstration of the tool TAPAAL that supports modelling, simulation and verification of TAPN.


Tomáš Vojnar (Brno Universtiy of Technology)

Title: Efficient Algorithms for Checking Inclusion on Nondeterministic Automata

Abstract: Finite (word, tree, or omega) automata play an important role in different areas of computer science, including, for instance, formal verification. In many of the applications, a crucial step is to check inclusion between the languages of some automata. A traditional way to do so is to complement one of the input automata and check emptiness of the intersection of the languages of the complemented automaton and the other input automaton. However, complementation of automata usually includes some form of determinisation which is a very expensive step. That is why various approaches for checking inclusion directly on nondeterministic automata, using techniques such as antichains and simulations, which greatly speed up inclusion checking in many practical scenarios, have recently attracted a lot of attention. In the talk, we review several of such techniques, covering inclusion checking for finite word and tree automata as well as for Büchi automata. The talk is based on several common works with Parosh Aziz Abdulla, Yu-Fang Chen, Lorenzo Clemente, Lukas Holik, Chih-Duo Hong, and Richard Mayr.



Created using Fluid 960 Grid, and Sofsems' webs. © Faculty of Mathematics, Physics, and Computer Science, Comenius University, 2010