The Harmoniser project aims to provide a practical tool to aid music composers in creating complete musical works. In this paper, we present a formal model of its second layer, tonal chord progressions and modulations to neighbouring tonalities, and a practical implementation using the Gecode constraint solver. Since music composition is too complex to formalize in its entirety, the Harmoniser project makes two assumptions for tractability: first, it focuses on tonal music (the basis of Western classical and popular music); second, it defines a simplified four-layer composition process that is relevant for a significant number of composers. Previous work on using constraint programming for music composition was limited to exploring the formalisation of different musical aspects and did not address the overall problem of building a practical composer tool. Harmoniser's four layers are global structure (tonal development of the whole piece), chord progressions (diatonic and chromatic) and modulations, voicing (four-voice chord layout), and ornaments (e.g., passing notes, appoggiaturas), all allowing iterative refinement by the composer. This paper builds on prior work for voicing layer 3, Diatony, and presents a model for layer 2, chord progressions and modulations. The results of the present paper can be used as input to Diatony to generate voicing. Future work will define models for the remaining layers, and combine all layers together with a graphical user interface as a plug-in for a DAW.

This retrospective reflects on a decade of influence stemming from Lasp, a coordination-free programming model built atop Conflict-Free Replicated Data Types (CRDTs). Designed to simplify distributed programming by prioritizing availability and convergence, Lasp has had a lasting impact across academia and industry.

Summary Sharing of computing resources and workload across different big data frameworks is challenging due to their lack of interoperable interfaces. In contrast, web services natively support an interoperable execution. Therefore, an increasing number of big data workflows are composed of data services and web service implementations that access and process big data. On the other hand, big data execution in the wide area networks needs to minimize latency and communication overheads to be able to scale seamlessly. Lack of network‐awareness of classic web service execution beyond data centers significantly challenges the scope of data services. Software‐Defined Networking (SDN) offers better control and management to the network, by unifying the control plane centrally, away from the distributed data plane devices. In this paper, we propose Software‐Defined Data Services (SDDS), an SDN‐based distributed service composition and workflow placement approach for data services in wide area networks. We first present the design of an SDDS framework that models the big data executions as composable data service workflows in multi‐domain network environments. We then evaluate the performance of a prototype SDDS framework through microbenchmarks. The benchmarks highlight the efficiency of SDDS in data service execution inside and beyond data centers.

Oz is a programming language designed to support multiple programming paradigms in a clean factored way that is easy to program despite its broad coverage. It started in 1991 as a collaborative effort by the DFKI (Germany) and SICS (Sweden) and led to an influential system, Mozart, that was released in 1999 and widely used in the 2000s for practical applications and education. We give the history of Oz as it developed from its origins in logic programming, starting with Prolog, followed by concurrent logic programming and constraint logic programming, and leading to its two direct precursors, the concurrent constraint model and the Andorra Kernel Language (AKL). We give the lessons learned from the Oz effort including successes and failures and we explain the principles underlying the Oz design. Oz is defined through a kernel language, which is a formal model similar to a foundational calculus, but that is designed to be directly useful to the programmer. The kernel language is organized in a layered structure, which makes it straightforward to write programs that use different paradigms in different parts. Oz is a key enabler for the bookConcepts, Techniques, and Models of Computer Programming(MIT Press, 2004). Based on the book and the implementation, Oz has been used successfully in university-level programming courses starting from 2001 to the present day.

Modern transactional platforms strive to jointly ensure ACID consistency and high scalability. In order to pursue these antagonistic goals, several recent systems have revisited the classical State Machine Replication (SMR) approach in order to support sharding of application state across multiple data partitions and partial replication. By promoting and exploiting locality principles, these systems, which we call Partially Replicated State Machines (PRSMs), can achieve scalability levels unparalleled by classic SMR. Yet, existing PRSM systems suffer from two major limitations: 1) they rely on a single thread to execute or serialize transactions within a partition, thus failing to fully untap the parallelism of multi-core architectures, and/or 2) they rely on the ability to accurately predict the data items to be accessed by transactions, which is non-trivial for complex applications. This paper proposes Sparkle, an innovative deterministic concurrency control that enhances the throughput of state of the art PRSM systems by more than one order of magnitude under high contention, through the joint use of speculative transaction processing and scheduling techniques. On the one hand, speculation allows Sparkle to take full advantage of modern multi-core micro-processors, while avoiding any assumption on the a-priori knowledge of the transactions' access patterns, which increases its generality and widens the scope of its scalability. Transaction scheduling techniques, on the other hand, are aimed to maximize the efficiency of speculative processing.

This work presents Speculative Transaction Replication (STR), a protocol that exploits transparent speculation techniques to enhance performance of geo-distributed, partially replicated transactional data stores. In addition, we define a new consistency model, Speculative Snapshot Isolation (SPSI), that extends the semantics of Snapshot Isolation (SI) to shelter applications from the subtle anomalies that can arise from using speculative transaction processing. SPSI extends SI in an intuitive and rigorous fashion by specifying desirable atomicity and isolation guarantees that must hold when using speculative execution.

Online services are often deployed over geographically-scattered data centers (geo-replication), which allows services to be highly available and reduces access latency. On the down side, to provide ACID transactions, global certification (i.e., across data centers) is needed to detect conflicts between concurrent transactions executing at different data centers. The global certification phase reduces throughput because transactions need to hold pre-commit locks, and it increases client-perceived latency because global certification lies in the critical path of transaction execution.

This paper presents the design, implementation, and evaluation of Saturn, a metadata service for geo-replicated systems. Saturn can be used in combination with several distributed and replicated data services to ensure that remote operations are made visible in an order that respects causality, a requirement central to many consistency criteria.

State-machine replication (SMR) is a fundamental technique to implement fault-tolerant services. Recently, various works have aimed at enhancing the scalability of SMR by exploiting partial replication techniques. By sharding the state machine across disjoint partitions, and replicating each partition over independent groups of processes, a Partially Replicated State Machine (PRSM) can process operations that involve a single partition by only requiring synchronization among the replicas of that partition - achieving higher scalability than SMR. Unfortunately, though, existing PRSM rely on inefficient mechanisms to coordinate the execution of multi-partition operations, which either impose global coordination across all nodes in the system or require inter-partition synchronization on the critical path of execution of operations. As such, performance and scalability of existing PRSM systems is severely hindered in the presence of even a small fraction of multi-partition operations. This paper tackles this issue by presenting Genepi, a PRSM protocol that introduces a novel, highly efficient mechanism for regulating the execution of multi-partition operations. We show via an experimental evaluation based on both synthetic benchmarks and TPC-C that Genepi can achieve up to 5.5× of throughput gain over existing PRSM systems, with only negligible latency overhead at low load.

Programming models for building large-scale distributed applications assist the developer in reasoning about consistency and distribution. However, many of the programming models for weak consistency, which promise the largest scalability gains, have little in the way of evaluation to demonstrate the promised scalability. We present an experience report on the implementation and large-scale evaluation of one of these models, Lasp, originally presented at PPDP '15, which provides a declarative, functional programming style for distributed applications. We demonstrate the scalability of Lasp's prototype runtime implementation up to 1024 nodes in the Amazon cloud computing environment. It achieves high scalability by uniquely combining hybrid gossip with a programming model based on convergent computation. We report on the engineering challenges of this implementation and its evaluation, specifically related to operating research prototypes in a production cloud environment.

We present a work in progress report on a new programming model that supports declarative, functional style aggregation operations over devices at the edge. This programming model bridges the gap between the two competing approaches for large-scale aggregations, streaming all data back to a central coordinator versus designing an optimized, distributed algorithm, by leveraging convergent data structures, dynamic scoping, and a declarative functional semantics implemented by a distributed runtime. We motivate our design with an industrial application susceptible to message reordering and arbitrary message delays on an unreliable network.

Designers of large user-oriented distributed applications, such as social networks and mobile applications, have adopted measures to improve the responsiveness of their applications. Latency is a major concern as people are very sensitive to it. Geo-replication is a commonly used mechanism to bring the data closer to clients. Nevertheless, reaching the closest datacenter can still be considerably slow. Thus, in order to further reduce the access latency, mobile and web applications may be forced to replicate data at the client-side. Unfortunately, fully replicating large data structures may still be a waste of resources, specially for thin-clients. We propose a replication mechanism built upon conflict-free replicated data types (CRDT) to seamlessly replicate parts of large data structures. The mechanism is transparent to developers and gives improvements without increasing application complexity. We define partial replication and give an approach to keep the strong eventual consistency properties of CRDTs with partial replicas. We integrate our mechanism into SwiftCloud, a transactional system that brings geo-replication to clients. We evaluate the solution with a content-sharing application. Our results show improvements in bandwidth, memory, and latency over both classical geo-replication and the existing SwiftCloud solution.

We investigate the interaction between Network Partitioning and Churn (node turnover) in Structured Overlay Networks. This work is relevant both to systems with peaks of high stress (e.g., partitions, churn) or continuous high stress. It prepares the way for new application venues in mobile and ad hoc networks, which have high node mobility and intermittent connectivity, and undergo frequent changes in network topology. We evaluate existing overlay maintenance strategies, namely Correction-on-Change, Correction-on-Use, Periodic Stabilization, and Ring Merge. We define the reversibility property of a system as its ability to repair itself to provide its original functionality when the external stress is withdrawn. We propose a new strategy, Knowledge Base, to improve conditions for reversibility in the case of combined network partitioning and churn. By means of simulations, we demonstrate reversibility for overlay networks with high levels of partition and churn and we make general conclusions about the ability of the maintenance strategies to achieve reversibility. We propose a model, namely Stranger Model, to generalize the impact of simultaneous network partitioning and churn. We show that this interaction causes partitions to eventually become strangers to each other, which makes full reversibility impossible when this happens. Using this model, we can predict when irreversibility arrives, which we verify via simulation. However, high levels of one only, network partitioning or churn, do not hinder reversibility. In future work we will extend these results to real systems and experiment with applications that take advantage of reversibility.

We propose Lasp, a new programming model designed to simplify large-scale distributed programming. Lasp combines ideas from deterministic dataflow programming together with conflict-free replicated data types (CRDTs). This provides support for computations where not all participants are online together at a given moment. The initial design presented here provides powerful primitives for composing CRDTs, which lets us write long-lived fault-tolerant distributed applications with nonmonotonic behavior in a monotonic framework. Given reasonable models of node-to-node communications and node failures, we prove formally that a Lasp program can be considered as a functional program that supports functional reasoning and programming techniques. We have implemented Lasp as an Erlang library built on top of the Riak Core distributed systems framework. We have developed one nontrivial large-scale application, the advertisement counter scenario from the SyncFree research project. We plan to extend our current prototype into a general-purpose language in which synchronization is used as little as possible.

Distributed applications built on top of Structured Overlay Networks (SONs) operate based on certain assurances from the underlying Peer-to-Peer network. Such applications continue to increase in scale, becoming more complex and difficult to manage. The situation becomes worse if the behavior of underlying SON is non-deterministic or even unknown for a given scenario. This implies non-trivial questions: what behavior should the application layer expect from the underlying SON in a given scenario? Under what conditions should a SON exhibit resiliency against an extremely hostile environment? Ideally, the behavior of a complex system such as a SON needs to be defined for every possible operating condition. Existing literature lacks a systematic and in-depth study of the global behavior of a SON. This work is a step towards answering those questions, which starts by proposing an organization of the global operating space of a SON, also defines the term “behavior”, with respect to a SON. In order to conduct the experimental study, an existing ring-based SON, namely Beernet, is chosen as a representative. As the entire operating space of a SON is extremely large, due to space limitation, this paper presents the first results of our investigation, the behavior of Beernet along the dimension of Churn. The study assesses behaviors like key availability, updates, replica management, and failed transactions, as a function of churn up to 100% node turnover per time unit. The result shows that, continuous injection of extremely high churn causes the ring to be dissolved, creating isolation of peers. However, at such a high node turnover of 100% per 5s, there are instances, where the % of failed transactions didn't reach 100%, especially in cases, when the join events dominate failures during initial period.

This paper introduces, motivates, defines, and exemplifies the concept of distribution graph as a way for modelling and developing Distributed User Interfaces of interactive systems. A distribution graph consists of a state chart model enriched as follows: states represent individual states of entities involved in the distribution as well as a collective representation of their synchronization; transitions are represented by event-condition-actions where the action part consists of a distribution script. A distribution script expresses the distribution behaviour based on distribution primitives. These primitives are basic operations that manipulate parts or wholes of user interface for distribution at run-time. These primitives are themselves implemented on top of an environment for distributed computing that is implemented for four major computing platforms (i.e., Microsoft Windows, Mac OS X, Linux, and Mobile Linux). Thanks to the capabilities provided by this environment, the user interfaces belonging to these distributed systems can be run indifferently on any of these computing platforms. This paper defines the new concepts introduced for this purpose, i.e., distribution primitive, distribution script, and distribution graph, and demonstrates how they can effectively support distributed user interfaces.

This article aims to investigate user preferences for extra-user interfaces (extra-UI), formerly known as meta-user interfaces. These are special user interfaces that allow the user to control or personalize the application's user interface. They are named “extra-user interfaces” because the application does not need it to work. Their main goal is the support of systems with several contexts, displays, devices, or platforms. The purposes and features offered by all the Extra-UI vary from one application to another. To create coherence between them, we defined a catalogue of 14 distribution primitives that are typically provided and classified into 4 categories: simple primitives, basic primitives, advanced primitives, and management operations. Based on this catalogue, a comparative analysis of the state of the art was conducted to identify which interaction styles have been properly used and to discuss the rationale behind these usages. From this analysis, we set up and conducted a comparative evaluation of user preferences by 14 participants testing 6 selected distribution primitives in 4 different interaction styles. The research outcomes exemplified that there were significant differences on user preferences between interaction styles with regards to experience level and primitive type.

The focus of this demonstrator is on the study of algorithms for implementing transactions on peer-to-peer networks. Their visualization contributes to the analysis and test of the protocols, verifying their tolerance to failures. In particular, we show a DHT running two-phase commit and the Paxos consensus algorithm.

Social networks are usually navigable small worlds: individuals are able to find short chains of acquaintances connecting pairs of unrelated nodes. This property can be explained by the fact that nodes are characterized by a series of properties, such as geographical position, work or educational background; the navigation proceeds towards the node that is "most similar" to the destination. Since nodes are likely to be linked with similar individuals, this strategy permits to quickly reach the destination. We approach the problem of creating the information that makes a network navigable. Starting from a given network, and without any other information, we show how nodes can reconstruct, with a scalable and decentralized algorithm, a "network map": a d-dimensional layout that places nodes in a way that reflects the network structure, so that navigability is achieved. Euclidean distance on the layout is used as a measure for node similarity, and efficient routing can be simply achieved by iteratively jumping towards the neighbor that is closest to the destination. The network map provides a means for implementing routing on social networks that can be used in "darknets", that is, anonymous networks where nodes establish connections only if they are mutually trusted. Moreover, the distance between nodes on the network map can be used as a measure of node affinity, and may help in various types of network analysis, for instance to help evaluate reputation in webs of trust, or in order to perform "personalized" ranking.

The migration of a user interface (UI) is the action of transferring a UI from one device to another, for example from a desktop computer to a handheld device. A UI is said to be migratable if it has the ability to migrate. This paper describes how the QTk toolkit has been extended to provide a migratable UI and the application programming interface (API) provided to the developers. Basically, an indirection layer has been introduced between the application and the actual representation of the UI. The migration of a UI is achieved by firstly creating a clone of the state of the site displaying the UI, secondly by changing the indirection to point to this clone. The API provides a way to specify if (the entirety of) a window can be migrated or not at construction time. A migratable window returns a universal reference that can be given to any site with whom a network connection is possible. This reference can be used by a receiver widget to migrate the window there. Interestingly, a migratable window can itself contain a receiver widget configured to display the content of another migratable window: all windows are transparently migrated. Also a window (stationary or migratable) may contain one or more receiver widgets : it is possible to dynamically compose a Ul from several different UIs.

The purpose of this panel is to confront the wide variety of opinions on the role of language paradigms in teaching programming. We have selected four divergent opinions:Armstrong says that concurrent programming is considered difficult because it is taught in the wrong paradigm, namely imperative or object-oriented programming. Instead, concurrency should be taught using a paradigm that makes it simple.Flatt says that everyone should be taught how to program, not just computer science majors. Further, programming should be taught as an extension of what students already know, which is algebra. More important than a particular paradigm, however, is teaching students a design process.Magnusson says that object-oriented programming must be the first and principal paradigm, because it is best for teaching how to analyze problems and structure solutions. Other paradigms can be taught after students have a solid understanding of OO.Van Roy says that programming should be taught in terms of concepts, not paradigms. Common paradigms (functional, OO, etc.) then appear naturally, depending on the concepts used..The panel will confront these opinions to enrich our understanding of how to teach programming.

Oz is a multiparadigm language that supports logic programming as one of its major paradigms. A multiparadigm language is designed to support different programming paradigms (logic, functional, constraint, object-oriented, sequential, concurrent, etc.) with equal ease. This paper has two goals: to give a tutorial of logic programming in Oz; and to show how logic programming fits naturally into the wider context of multiparadigm programming. Our experience shows that there are two classes of problems, which we call algorithmic and search problems, for which logic programming can help formulate practical solutions. Algorithmic problems have known efficient algorithms. Search problems do not have known efficient algorithms but can be solved with search. The Oz support for logic programming targets these two problem classes specifically, using the concepts needed for each. This is in contrast to the Prolog approach, which targets both classes with one set of concepts, which results in less than optimal support for each class. We give examples that can be run interactively on the Mozart system, which implements Oz. To explain the essential difference between algorithmic and search programs, we define the Oz execution model. This model subsumes both concurrent logic programming (committed-choice-style) and search-based logic programming (Prolog-style). Furthermore, as consequences of its multiparadigm nature, the model supports new abilities such as first-class top levels, deep guards, active objects, and sophisticated control of the search process. Instead of Horn clause syntax, Oz has a simple, fully compositional, higher-order syntax that accommodates the abilities of the language. We give a brief history of Oz that traces the development of its main ideas and we summarize the lessons learned from this work. Finally, we give many entry points into the Oz literature.

The peer-to-peer (P2P) computing paradigm is an emerging paradigm that aims to overcome most of the main limitations of the traditional client/server architecture. In the P2P setting, individual computers communicate directly with each other in order to share information and resources without relying on any kind of centralized server. To achieve this full decentralization, an application-level (or overlay) network is constructed using, for example, TCP connections. In most of the existing P2P systems, the overlay network is built in a manner that does not guarantee that the overlay network is efficient with respect to a given metric (e.g. latency, hop count and bandwidth). Hence, an overlay node can be very far away, in terms of a given metric, from its overlay neighbors. This can result in both, an inefficient routing at the overlay network and an ineffective use of the underlying IP network. In this paper, we introduce a new measure, "goodness of overlay networks", to quantify the quality of an overlay network for a given metric. We then propose NetProber, a simple, distributed and scalable component that can be combined with any connected overlay network in order to allow the latter to adapt, and to become "good" within a finite amount of time.

We define a practical algorithm for distrubuted rational tree unification and prove its correctness in both the off-line and on-line cases. We derive the distributed algorithm from a centralized one, showing clearly the trade-offs between local and distributed execution. The algorithm is used to realize logic variables in the Mozart Programming System, which implements the Oz language (see http://www/mozart-oz.org). Oz appears to the programmer as a concurrent object-oriented language with dataflow synchronization. Logic variables implement the dataflow behavior. We show that lohgic variables can easily be added to the more restricted models of Java and ML, thus providing an alternative way to do concurent programming in these languages. We present common distributed programming idioms in a network-transparent way using logic variables. We show that in common cases the algorithm maintains the same message latency as explicit message passing. In addition, it is able to handle uncommon cases that arise from the properties of latency tolerance and third-party independence. This is evidence that using logic variables in distributed computing is beneficial at both the system and language levels. At the system level, they improve latency tolerance and third-party independence. At the language level, they help make network-transparent distribution practical.

Some of the most difficult questions to answer when designing a distributed application are related to mobility: what information to transfer between sites and when and how to transfer it. Network-transparent distribution, the property that a program's behavior is independent of how it is partitioned among sites, does not directly address these questions. Therefore we propose to extend all language entities with a network behavior that enables efficient distributed programming by giving the programmer a simple and predictable control over network communication patterns. In particular, we show how to give objects an arbitrary mobility behavior that is independent of the objects definition. In this way, the syntax and semantics of objects are the same regardless of whether they are used as stationary servers, mobile agents, or simply as caches. These ideas have been implemented in Distributed Oz, a concurrent object-oriented language that is state aware and has dataflow synchronization. We prove that the implementation of objects in Distributed Oz is network transparent. To satisfy the predictability condition, the implementation avoids forwarding chains through intermediate sites. The implementation is an extension to the publicly available DFKI Oz 2.0 system.

Most Prolog machines have been based on specialized architectures. Our goal is to start with a general purpose architecture and determine a minimal set of extensions for high performance Prolog execution. We have developed both the architecture and optimizing compiler simultaneously, drawing on results of previous implementations. We find that most Prolog specific operations can be done satisfactorily in software; however, there is a crucial set of features that the architecture must support to achieve the best Prolog performance. The emphasis of this paper is on our architecture and instruction set. The costs and benefits of the special architectural features and instructions are analyzed. Simulated performance results are presented and indicate a peak compiled Prolog performance of 3.68 million logical inferences per second.