5,898 Works

QoE Vadis? (Dagstuhl Perspectives Workshop 16472)

Makus Fiedler, Marcus Möller, Peter Reichl & Min Xie
The goal of the Dagstuhl Perspectives Workshop 16472 has been to discuss and outline the strategic evolution of Quality of Experience as a key topic for future Internet research. The resulting manifesto, which is presented here, reviews the state of the art in the Quality of Experience (QoE) domain, along with a SWOT analysis. Based on those, it discusses how the QoE research area might develop in the future, and how QoE research will lead...

Reliable Computation and Complexity on the Reals (Dagstuhl Seminar 17481)

Norbert T. Müller, Siegfried M. Rump, Klaus Weihrauch & Martin Ziegler
Naive computations with real numbers on computers may cause serious errors. In traditional numerical computation these errors are often neglected or, more seriously, not identified. Two approaches attack this problem and investigate its background, Reliable Computing and Computable Analysis. Methods in Reliable Computing are essentially mathematical theorems, the assumptions of which are verified on the computer. This verification is performed using the very efficient floating point arithmetic. If the verification succeeds, the assertions are true...

Dagstuhl Reports, Table of Contents, Volume 7, Issue 9, 2017

Marc Herbstritt
Table of Contents, Frontmatter

Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151)

Serge Abiteboul, Marcelo Arenas, Pablo Barceló, Meghyn Bienvenu, Diego Calvanese, Claire David, Richard Hull, Eyke Hüllermeier, Benny Kimelfeld, Leonid Libkin, Wim Martens, Tova Milo, Filip Murlak, Frank Neven, Magdalena Ortiz, Thomas Schwentick, Julia Stoyanovich, Jianwen Su, Dan Suciu, Victor Vianu & Ke Yi
The area of Principles of Data Management (PDM) has made crucial contributions to the development of formal frameworks for understanding and managing data and knowledge. This work has involved a rich cross-fertilization between PDM and other disciplines in mathematics and computer science, including logic, complexity theory, and knowledge representation. We anticipate on-going expansion of PDM research as the technology and applications involving data management continue to grow and evolve. In particular, the lifecycle of Big...

Testing and Verification of Compilers (Dagstuhl Seminar 17502)

Junjie Chen, Alastair F. Donaldson, Andreas Zeller & Hongyu Zhang
This report documents the Dagstuhl Seminar 17502 "Testing and Verification of Compilers" that took place during December 10 to 13, 2017, which we provide as a resource for researchers who are interested in understanding the state of the art and open problems in this field, and applying them to this and other areas.

Multi-Level Modelling (Dagstuhl Seminar 17492)

João Paulo A. Almeida, Ulrich Frank & Thomas Kühne
This report documents the program and the outcomes of Dagstuhl Seminar 17492 "Multi-Level Modelling". This seminar brought together researchers and industry practitioners from the fields of conceptual modeling, ontologies, and formal foundations to discuss and share the benefits of Multi-Level Modelling (MLM), to develop an agreement on MLM terminology and scope, and to drive future research directions in MLM. Some foundational presentations were given by the seminar organizers to ground the discussions and provide an...

Computational Metabolomics: Identification, Interpretation, Imaging (Dagstuhl Seminar 17491)

Theodore Alexandrov, Sebastian Böcker, Pieter Dorrestein & Emma Schymanski
Metabolites are key players in almost all biological processes, and play various functional roles providing energy, building blocks, signaling, communication, and defense. Metabolites serve as clinical biomarkers for detecting medical conditions such as cancer; small molecule drugs account for 90% of prescribed therapeutics. Complete understanding of biological systems requires detecting and interpreting the metabolome in time and space. Following in the steps of high-throughput sequencing, mass spectrometry (MS) has become established as a key analytical...

Artificial and Computational Intelligence in Games: AI-Driven Game Design (Dagstuhl Seminar 17471)

Pieter Spronck, Elisabeth André, Michael Cook & Mike Preuß
With the dramatic growth of the game industry over the past decade, its rapid inclusion in many sectors of today's society, and the increased complexity of games, game development has reached a point where it is no longer humanly possible to use only manual techniques to create games. Large parts of games need to be designed, built, and tested automatically. In recent years, researchers have delved into artificial intelligence techniques to support, assist, and even...

Addressing the Computational Challenges of Personalized Medicine (Dagstuhl Seminar 17472)

Niko Beerenwinkel, Holger Fröhlich & Susan A. Murphy
This report provides an overview of the talks and the working group reports from the Dagstuhl Seminar 17472 "Addressing the Computational Challenges of Personalized Medicine". The seminar brought together leading computational scientists with different backgrounds and perspectives in order to allow for a cross-fertilizing and stimulating discussion. It thus joined expertise that is usually scattered in different research communities. In addition, selected medical researchers, pharmacogenomics researchers and behavioral scientists provided their input and established the...

Connecting Visualization and Data Management Research (Dagstuhl Seminar 17461)

Remco Chang, Jean-Daniel Fekete, Juliana Freire & Carlos E. Scheidegger
This report documents the program and the outcomes of Dagstuhl Seminar 17461 "Connecting Visualization and Data Management Research".

A Shared Challenge in Behavioural Specification (Dagstuhl Seminar 17462)

Klaus Havelund, Martin Leucker, Giles Reger & Volker Stolz
This report documents the program and the outcomes of Dagstuhl Seminar 17462 "A Shared Challenge in Behavioural Specification". The seminar considered the issue of behavioral specification with a focus on its usage in Runtime Verification. The seminar was motivated by the observations that, whilst the field of Runtime Verification is becoming more mature, there is a lack of common specification language, in the main part due to the rich setting allowing for highly expressive languages....

New Challenges in Parallelism (Dagstuhl Seminar 17451)

Annette Bieniusa, Hans-J. Boehm, Maurice Herlihy & Erez Petrank
A continuing goal of current multiprocessor software design is to improve the performance and reliability of parallel algorithms. Parallel programming has traditionally been attacked from widely different angles by different groups of people: Hardware designers designing instruction sets, programming language designers designing languages and library interfaces, and theoreticians developing models of parallel computation. Unsurprisingly, this has not always led to consistent results. Newly developing areas show every sign of leading to similar divergence. This Dagstuhl...

Algorithmic Cheminformatics (Dagstuhl Seminar 17452)

Jakob L. Andersen, Christoph Flamm, Daniel Markle & Peter F. Stadler
Dagstuhl Seminar 17452 "Algorithmic Cheminformatics" brought together leading researchers from both chemistry and computer science. The seminar was the second in a series of the Dagstuhl seminars and had a focus on concurrency theory as chemical systems are highly concurrent by nature. Within computer science we focused on formal approaches for chemistry and concurrency theory, including process calculi and Petri nets. The participants surveyed areas of overlapping interests and identified possible fields of joint future...

Quantum Cryptanalysis (Dagstuhl Seminar 17401)

Michele Mosca, Nicolas Sendrier, Rainer Steinwandt & Krysta Svore
This report documents the program and the outcomes of Dagstuhl Seminar 17401 "Quantum Cryptanalysis." We start out by outlining the motivation and organizational aspects of the seminar. Thereafter, abstracts of presentations given by seminar participants are provided.

Causality for the Masses: Offering Fresh Data, Low Latency, and High Throughput

Luís Rodrigues
The problem of ensuring consistency in applications that manage replicated data is one of the main challenges of distributed computing. Among the several invariants that may be enforced, ensuring that updates are applied and made visible respecting causality has emerged as a key ingredient among the many consistency criteria and client session guarantees that have been proposed and implemented in the last decade. Techniques to keep track of causal dependencies, and to subsequently ensure that...

Mutual Exclusion Algorithms with Constant RMR Complexity and Wait-Free Exit Code

Rotem Dvir & Gadi Taubenfeld
Two local-spinning queue-based mutual exclusion algorithms are presented that have several de- sired properties: (1) their exit codes are wait-free, (2) they satisfy FIFO fairness, (3) they have constant RMR complexity in both the CC and the DSM models, (4) it is not assumed that the number of processes, n, is a priori known, that is, processes may appear or disappear intermit- tently, (5) they use only O(n) shared memory locations, and (6) they make...

Remote Memory References at Block Granularity

Hagit Attiya & Gili Yavneh
The cost of accessing shared objects that are stored in remote memory, while neglecting accesses to shared objects that are cached in the local memory, can be evaluated by the number of remote memory references (RMRs) in an execution. Two flavours of this measure—cache-coherent (CC) and distributed shared memory (DSM)—model two popular shared-memory architectures. The number of RMRs, however, does not take into account the granularity of memory accesses, namely, the fact that accesses to...

piChain: When a Blockchain meets Paxos

Conrad Burchert & Roger Wattenhofer
We present a new fault-tolerant distributed state machine to inherit the best features of its “parents in spirit”: Paxos, providing strong consistency, and a blockchain, providing simplicity and availability. Our proposal is simple as it does not include any heavy weight distributed failure handling protocols such as leader election. In addition, our proposal has a few other valuable features, e.g., it is responsive, it scales well, and it does not send any overhead messages.

Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms

Bogdan S. Chlebus, Gianluca De Marco & Muhammed Talo
We consider synchronous distributed systems in which processors communicate by shared read- write variables. Processors are anonymous and do not know their number n. The goal is to assign individual names by all the processors to themselves. We develop algorithms that accomplish this for each of the four cases determined by the following independent properties of the model: concurrently attempting to write distinct values into the same shared memory register either is allowed or not,...

Lower Bounds on the Amortized Time Complexity of Shared Objects

Hagit Attiya & Arie Fouren
The amortized step complexity of an implementation measures its performance as a whole, rather than the performance of individual operations. Specifically, the amortized step complexity of an implementation is the average number of steps performed by invoked operations, in the worst case, taken over all possible executions. The amortized step complexity of a wide range of known lock- free implementations for shared data structures, like stacks, queues, linked lists, doubly-linked lists and binary trees, includes...

Fast Detection of Stable and Count Predicates in Parallel Computations

Himanshu Chauhan & Vijay K. Garg
Enumerating all consistent states of a parallel computation that satisfy a given predicate is an important problem in debugging and verification of parallel programs. We give a fast algorithm to enumerate all consistent states of a parallel computation that satisfy a stable predicate. In addi- tion, we define a new category of global predicates called count predicates and give an algorithm to enumerate all consistent states (of the computation) that satisfy it. All existing predicate...

Fast Distributed Approximation for TAP and 2-Edge-Connectivity

Keren Censor-Hillel & Michal Dory
The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G, such that T ∪ Aug is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of...

Constant-Space Population Protocols for Uniform Bipartition

Hiroto Yasumi, Fukuhito Ooshita, Ken'Ichi Yamaguchi & Michiko Inoue
In this paper, we consider a uniform bipartition problem in a population protocol model. The goal of the uniform bipartition problem is to divide a population into two groups of the same size. We study the problem under various assumptions: 1) a population with or without a base station, 2) weak or global fairness, 3) symmetric or asymmetric protocols, and 4) designated or arbitrary initial states. As a result, we completely clarify constant-space solvability of...

Designing a Planetary-Scale IMAP Service with Conflict-free Replicated Data Types

Tim Jungnickel, Lennart Oldenburg & Matthias Loibl
Modern geo-replicated software serving millions of users across the globe faces the consequences of the CAP dilemma, i.e., the inevitable conflicts that arise when multiple nodes accept writes on shared state. The underlying problem is commonly known as fault-tolerant multi-leader replica- tion; actively researched in the distributed systems and database communities. As a more recent theoretical framework, Conflict-free Replicated Data Types (CRDTs) propose a solution to this problem by offering a set of always converging...

Schlegel Diagram and Optimizable Immediate Snapshot Protocol

Susumu Nishimura
In the topological study of distributed systems, the immediate snapshot is the fundamental computation block for the topological characterization of wait-free solvable tasks. However, in reality, the immediate snapshot is not available as a native built-in operation on shared memory distributed systems. Borowsky and Gafni have proposed a wait-free multi-round protocol that implements the immediate snapshot using more primitive operations, namely the atomic reads and writes. In this paper, up to an appropriate reformulation on...

Resource Types

  • Text
    5,844
  • Software
    54

Publication Year

  • 2018
    361
  • 2017
    1,327
  • 2016
    1,177
  • 2015
    732
  • 2014
    431
  • 2013
    463
  • 2012
    430
  • 2011
    371
  • 2010
    226
  • 2009
    169
  • 2008
    125
  • 2007
    44
  • 2006
    42

Registration Year

  • 2018
    362
  • 2017
    1,326
  • 2016
    1,178
  • 2015
    731
  • 2014
    432
  • 2013
    462
  • 2012
    447
  • 2011
    373
  • 2010
    453
  • 2009
    134