Distributed concurrent constraint execution in the CIAO system

This paper describes the current prototype of the distributed CIAO system. It introduces the concepts of "teams" and "active modules" (or active objects), which conveniently encapsulate different types of functionalities desirable from a distributed system, from parallelism for achieving speedup to client-server applications. It presents the user primitives available and describes their implementation. This implementation uses attributed variables and, as an example of a communication abstraction, a blackboard that follows the Linda model. The functionalities of the system are illustrated through examples, using the implemented primitives. The implementation of most of the primitives is also described in detail.

Some methodological issues in the design of CIAO, a generic, parallel concurrent constraint system

We informally discuss several issues related to the parallel execution of logic programming systems and concurrent logic programming systems, and their generalization to constraint programming. We propose a new view of these systems, based on a particular definition of parallelism. We argüe that, under this view, a large number of the actual systems and models can be explained through the application, at different levéis of granularity, of only a few basic principies: determinism, non-failure, independence (also referred to as stability), granularity, etc. Also, and based on the convergence of concepts that this view brings, we sketch a model for the implementation of several parallel constraint logic programming source languages and models based on a common, generic abstract machine and an intermedíate kernel language.

Towards CIAO-Prolog - A parallel concurrent constraint system

Abstract is not available.

Some considerations on the compile-time analysis of constraint logic programs

This paper discusses some issues which arise in the dataflow analysis of constraint logic programming (CLP) languages. The basic technique applied is that of abstract interpretation. First, some types of optimizations possible in a number of CLP systems (including efficient parallelization) are presented and the information that has to be obtained at compile-time in order to be able to implement such optimizations is considered. Two approaches are then proposed and discussed for obtaining this information for a CLP program: one based on an analysis of a CLP metainterpreter using standard Prolog analysis tools, and a second one based on direct analysis of the CLP program. For the second approach an abstract domain which approximates groundness (also referred to as "definiteness") information (i.e. constraint to a single valué) and the related abstraction functions are presented.

Analysis of concurrent constraint logic programs with a fixed scheduling rule

The analysis of concurrent constraint programs is a challenge due to the inherently concurrent behaviour of its computational model. However, most implementations of the concurrent paradigm can be viewed as a computation with a fixed scheduling rule which suspends some goals so that their execution is postponed until some condition awakens them. For a certain kind of properties, an analysis defined in these terms is correct. Furthermore, it is much more tractable, and in addition can make use of existing analysis technology for the underlying fixed computation rule. We show how this can be done when the starting point is a framework for the analysis of sequential programs. The resulting analysis, which incorporates suspensions, is adequate for concurrent models where concurrency is localized, e.g. the Andorra model. We refine the analysis for this particular case. Another model in which concurrency is preferably encapsulated, and thus suspensions are local to parts of the computation, is that of CIAO. Nonetheless, the analysis scheme can be generalized to models with global concurrency. We also sketch how this could be done, and we show how the resulting analysis framework could be used for analyzing typical properties, such as suspensión freeness.

An Introductory Course on Constraint Logic Programming

The purpose of this document is to serve as the printed material for the seminar "An Introductory Course on Constraint Logic Programming". The intended audience of this seminar are industrial programmers with a degree in Computer Science but little previous experience with constraint programming. The seminar itself has been field tested, prior to the writing of this document, with a group of the application programmers of Esprit project P23182, "VOCAL", aimed at developing an application in scheduling of field maintenance tasks in the context of an electric utility company. The contents of this paper follow essentially the flow of the seminar slides. However, there are some differences. These differences stem from our perception from the experience of teaching the seminar, that the technical aspects are the ones which need more attention and clearer explanations in the written version. Thus, this document includes more examples than those in the slides, more exercises (and the solutions to them), as well as four additional programming projects, with which we hope the reader will obtain a clearer view of the process of development and tuning of programs using CLP. On the other hand, several parts of the seminar have been taken out: those related with the account of fields and applications in which C(L)P is useful, and the enumerations of C(L)P tools available. We feel that the slides are clear enough, and that for more information on available tools, the interested reader will find more up-to-date information by browsing the Web or asking the vendors directly. More details in this direction will actually boil down to summarizing a user manual, which is not the aim of this document.

Constraint-based runtime prediction of SLA violations in service orchestrations

Service compositions put together loosely-coupled component services to perform more complex, higher level, or cross-organizational tasks in a platform-independent manner. Quality-of-Service (QoS) properties, such as execution time, availability, or cost, are critical for their usability, and permissible boundaries for their values are defined in Service Level Agreements (SLAs). We propose a method whereby constraints that model SLA conformance and violation are derived at any given point of the execution of a service composition. These constraints are generated using the structure of the composition and properties of the component services, which can be either known or empirically measured. Violation of these constraints means that the corresponding scenario is unfeasible, while satisfaction gives values for the constrained variables (start / end times for activities, or number of loop iterations) which make the scenario possible. These results can be used to perform optimized service matching or trigger preventive adaptation or healing.

Tools for constraint visualisation: The VIFID/TRIFID tool

Visualisation of program executions has been used in applications which include education and debugging. However, traditional visualisation techniques often fall short of expectations or are altogether inadequate for new programming paradigms, such as Constraint Logic Programming (CLP), whose declarative and operational semantics differ in some crucial ways from those of other paradigms. In particular, traditional ideas regarding the behaviour of data often cannot be lifted in a straightforward way to (C)LP from other families of programming languages. In this chapter we discuss techniques for visualising data evolution in CLP. We briefly review some previously proposed visualisation paradigms, and also propose a number of (to our knowledge) novel ones. The graphical representations have been chosen based on the perceived needs of a programmer trying to analyse the behaviour and characteristics of an execution. In particular, we concentrate on the representation of the run-time values of the variables, and the constraints among them. Given our interest in visualising large executions, we also pay attention to abstraction techniques, i.e., techniques which are intended to help in reducing the complexity of the visual information.

Implicaciones de la accesibilidad configuracional en la movilidad peatonal. El caso de Madrid = The implications of configurational accessibility in pedestrian mobility. The case of Madrid

- Resumen La hipótesis que anima esta tesis doctoral es que algunas de las características del entorno urbano, en particular las que describen la accesibilidad de su red de espacio público, podrían estar relacionadas con la proporción de viajes a pie o reparto modal, que tiene cada zona o barrio de Madrid. Uno de los puntos de partida de dicha hipótesis que el entorno urbano tiene una mayor influencia sobre los viaje a pie que en sobre otros modos de transporte, por ejemplo que en los viajes de bicicleta o en transporte público; y es que parece razonable suponer que estos últimos van a estar más condicionadas por ejemplo por la disponibilidad de vías ciclistas, en el primer caso, o por la existencia de un servicio fiable y de calidad, en el segundo. Otra de las motivaciones del trabajo es que la investigación en este campo de la accesibilidad del espacio público, en concreto la denominada “Space Syntax”, ha probado en repetidas ocasiones la influencia de la red de espacio público en cómo se distribuye la intensidad del tráfico peatonal por la trama urbana, pero no se han encontrado referencias de la influencia de dicho elemento sobre el reparto modal. De acuerdo con la hipótesis y con otros trabajos anteriores se propone una metodología basada en el análisis empírico y cuantitativo. Su objetivo es comprobar si la red de espacio público, independientemente de otras variables como los usos del suelo, incluso de las variables de ajenas entorno no construido, como las socioeconómicas, está o no relacionada estadísticamente con la proporción de peatones viajes en las zonas urbanas. Las técnicas estadísticas se utilizan para comprobar sistemáticamente la asociación de las variables del entorno urbano, denominadas variables independientes, con el porcentaje de viajes a pie, la variable dependiente. En términos generales, la metodología es similar a la usada en otros trabajos en este campo como los de CERVERÓ y KOCKLEMAN (1997), CERVERÓ y DUNCAN (2003), o para los que se utilizan principalmente en la revisión general de TRB (2005) o, más recientemente, en ZEGRAS (2006) o CHATMAN (2009). Otras opciones metodológicas, como los métodos de preferencias declaradas (ver LOUVIERE, HENSHER y SWAIT, 2000) o el análisis basado en agentes (PENN & TURNER, 2004) fueron descartados, debido a una serie de razones, demasiado extensas para ser descritas aquí. El caso de estudio utilizado es la zona metropolitana de Madrid, abarcándola hasta la M-50, es decir en su mayor parte, con un tamaño aproximado de 31x34 Km y una población de 4.132.820 habitantes (aproximadamente el 80% de la población de la región). Las principales fuentes de datos son la Encuesta Domiciliaria de Movilidad de 2004 (EDM04), del Consorcio Regional de Transportes de Madrid que es la última disponible (muestra: > 35.000 familias,> 95.000 personas), y un modelo espacial del área metropolitana, integrando el modelo para calcular los índices de Space Syntax y un Sistema de Información Geográfica (SIG). La unidad de análisis, en este caso las unidades espaciales, son las zonas de transporte (con una población media de 7.063 personas) y los barrios (con una población media de 26.466 personas). Las variables del entorno urbano son claramente el centro del estudio. Un total de 20 índices (de 21) se seleccionan de entre los más relevantes encontrados en la revisión de la producción científica en este campo siendo que, al mismo tiempo, fueran accesibles. Nueve de ellos se utilizan para describir las características de los usos del suelo, mientras que otros once se usan para describir la red de espacios públicos. Estos últimos incluyen las variables de accesibilidad configuracional, que son, como se desprende de su título, el centro del estudio propuesto. La accesibilidad configuracional es un tipo especial de accesibilidad que se basa en la configuración de la trama urbana, según esta fue definida por HILLIER (1996), el autor de referencia dentro de esta línea de investigación de Space Syntax. Además se incluyen otras variables de la red de espacio público más habituales en los estudios de movilidad, y que aquí se denominan características geométricas de los elementos de la red, tales como su longitud, tipo de intersección, conectividad, etc. Por último se incluye además una variable socioeconómica, es decir ajena al entorno urbano, para evaluar la influencia de los factores externos, pues son varios los que pueden tener un impacto en la decisión de caminar (edad, género, nivel de estudios, ingresos, tasa de motorización, etc.). La asociación entre las variables se han establecido usando análisis de correlación (bivariante) y modelos de análisis multivariante. Las primeras se calculan entre por pares entre cada una de las 21 variables independientes y la dependiente, el porcentaje de viajes a pie. En cuanto a los segundos, se han realizado tres tipos de estudios: modelo multivariante general lineal, modelo multivariante general curvilíneo y análisis discriminante. Todos ellos son capaces de generar modelos de asociación entre diversas variables, pudiéndose de esta manera evaluar con bastante precisión en qué medida cada modelo reproduce el comportamiento de la variable dependiente, y además, el peso o influencia de cada variable en el modelo respecto a las otras. Los resultados fundamentales del estudio se expresan en dos modelos finales alternativos, que demuestran tener una significativa asociación con el porcentaje de viajes a pie (R2 = 0,6789, p <0,0001), al explicar las dos terceras partes de su variabilidad. En ellos, y en general en todo el estudio realizado, se da una influencia constante de tres índices en particular, que quedan como los principales. Dos de ellos, de acuerdo con muchos de los estudios previos, corresponden a la densidad y la mezcla de usos del suelo. Pero lo más novedoso de los resultados obtenidos es que el tercero es una medida de la accesibilidad de la red de espacio público, algo de lo que no había referencias hasta ahora. Pero, ¿cuál es la definición precisa y el peso relativo de cada uno en el modelo, es decir, en la variable independiente? El de mayor peso en la mayor parte de los análisis realizados es el índice de densidad total (n º residentes + n º puestos de trabajo + n º alumnos / Ha). Es decir, una densidad no sólo de población, sino que incluye algunas de las actividades más importantes que pueden darse una zona para generar movilidad a pie. El segundo que mayor peso adquiere, llegando a ser el primero en alguno de los análisis estadísticos efecturados, es el índice de accesibuilidad configuracional denominado integración de radio 5. Se trata de una medida de la accesibilidad de la zona, de su centralidad, a la escala de, más un menor, un distrito o comarca. En cuanto al tercero, obtiene una importancia bastante menor que los anteriores, y es que representa la mezcla de usos. En concreto es una medida del equilibrio entre los comercios especializados de venta al por menor y el número de residentes (n º de tiendas especializadas en alimentación, bebidas y tabaco / n º de habitantes). Por lo tanto, estos resultados confirman buena parte de los de estudios anteriores, especialmente los relativas a los usos del suelo, pero al mismo tiempo, apuntan a que la red de espacio público podría tener una influir mayor de la comprobada hasta ahora en la proporción de peatones sobre el resto de modos de transportes. Las razones de por qué esto puede ser así, se discuten ampliamente en las conclusiones. Finalmente se puede precisar que dicha conclusión principal se refiere a viajes de una sola etapa (no multimodales) que se dan en los barrios y zonas del área metropolitana de Madrid. Por supuesto, esta conclusión tiene en la actualidad, una validez limitada, ya que es el resultado de un solo caso — Abstract The research hypothesis for this Ph.D. Thesis is that some characteristics of the built environment, particularly those describing the accessibility of the public space network, could be associated with the proportion of pedestrians in all trips (modal split), found in the different parts of a city. The underlying idea is that walking trips are more sensitive to built environment than those by other transport modes, such as for example those by bicycle or by public transport, which could be more conditioned by, e.g. infrastructure availability or service frequency and quality. On the other hand, it has to be noted that the previously research on this field, in particular within Space Syntax’s where this study can be referred, have tested similar hypothesis using pedestrian volumes as the dependent variable, but never against modal split. According to such hypothesis, research methodology is based primarily on empirical quantitative analysis, and it is meant to be able to assess whether public space network, no matter other built environment and non-built environment variables, could have a relationship with the proportion of pedestrian trips in urban areas. Statistical techniques are used to check the association of independent variables with the percentage of walking in all trips, the dependent one. Broadly speaking this methodology is similar to that of previous studies in the field such as CERVERO&KOCKLEMAN (1997), CERVERO & DUNCAN (2003), or to those used mainly in the general review of T.R.B. (2005) or, more recently in ZEGRAS (2006) or CHATMAN (2009). Other methodological options such as stated choice methods (see LOUVIERE, HENSHER & SWAIT, 2000) or agent based analysis (PENN & TURNER, 2004), were discarded, due to a number of reasons, too long to be described here. The case study is not the entire Madrid’s metropolitan area, but almost (4.132.820 inhabitants, about 80% of region´s population). Main data sources are the Regional Mobility Home Based Survey 2004 (EDM04), which is the last available (sample: >35.000 families, > 95.000 individuals), and a spatial model of the metropolitan area, developed using Space Syntax and G.I.S. techniques. The analysis unit, in this case spatial units, are both transport zones (mean population = 7.063) and neighborhoods (mean population = 26.466). The variables of the built environment are clearly the core of the study. A total of 20 (out of 21) are selected from among those found in the literature while, at the same time, being accessible. Nine out of them are used to describe land use characteristics while another eleven describe the network of public spaces. Latter ones include configurational accessibility or Space Syntax variables. This is a particular sort of accessibility related with the concept of configuration, by HILLIER (1996), one of the main authors of Space Syntax, But it also include more customary variables used in mobility research to describe the urban design or spatial structure (here public space network), which here are called geometric characteristics of the such as its length, type of intersection, conectivity, density, etc. Finally a single socioeconomic variable was included in order to assess the influence non built environment factors that also may have an impact on walking (age, income, motorization rate, etc.). The association among variables is worked out using bi-variate correlation analysis and multivariate-analysis. Correlations are calculated among the 21 independent variables and the dependent one, the percentage of walking trips. Then, three types of multi-variate studies are run: general linear, curvilinear and discriminant multi-variate analysis. The latter are fully capable of generating complex association models among several variables, assessing quite precisely to what extent each model reproduces the behavior of the dependent variable, and also the weight or influence of each variable in the model. This study’s results show a consistent influence of three particular indexes in the two final alternative models of the multi-variate study (best, R2=0,6789, p<0,0000). Not surprisingly, two of them correspond to density and mix of land uses. But perhaps more interesting is that the third one is a measure of the accessibility of the public space network, a variable less important in the literature up to now. Additional precisions about them and their relative weight could also be of some interest. The density index is not only about population but includes most important activities in an area (nº residents + nº jobs+ nº students/Ha). The configurational index (radius 5 integration) is a measure of the accessibility of the area, i.e. centrality, at the scale of, more a less, a district. Regarding the mix of land uses index, this one is a measure of the balance between retail, in fact local basic retail, and the number of residents (nº of convenience shops / nº of residents). Referring to their weights, configurational index (radius 5 integration) gets the higher standardized coefficient of the final equation. However, in the final equations, there are a higher number of indexes coming from the density or land use mix categories than from public space network enter. Therefore, these findings seem to support part of the field’s knowledge, especially those concerning land uses, but at the same time they seem to bring in the idea that the configuration of the urban grid could have an influence in the proportion of walkers (as a part of total trips on any transport mode) that do single journey trips in the neighborhoods of Madrid, Spain. Of course this conclusion has, at present, a limited validity since it’s the result of a single case. The reasons of why this can be so, are discussed in the last part of the thesis.

Specialization and optimization of constraint programs with dynamic scheduling

In this report we discuss some of the issues involved in the specialization and optimization of constraint logic programs with dynamic scheduling. Dynamic scheduling, as any other form of concurrency, increases the expressive power of constraint logic programs, but also introduces run-time overhead. The objective of the specialization and optimization is to reduce as much as possible such overhead automatically, while preserving the semantics of the original programs. This is done by program transformation based on global analysis. We present implementation techniques for this purpose and report on experimental results obtained from an implementation of the techniques in the context of the CIAO compiler.

Automatic compile-time parallelization of CLP programs by analysis and transformation to a concurrent constraint language.

The concept of independence has been recently generalized to the constraint logic programming (CLP) paradigm. Also, several abstract domains specifically designed for CLP languages, and whose information can be used to detect the generalized independence conditions, have been recently defined. As a result we are now in a position where automatic parallelization of CLP programs is feasible. In this paper we study the task of automatically parallelizing CLP programs based on such analyses, by transforming them to explicitly concurrent programs in our parallel CC platform (CIAO) as well as to AKL. We describe the analysis and transformation process, and study its efficiency, accuracy, and effectiveness in program parallelization. The information gathered by the analyzers is evaluated not only in terms of its accuracy, i.e. its ability to determine the actual dependencies among the program variables, but also of its effectiveness, measured in terms of code reduction in the resulting parallelized programs. Given that only a few abstract domains have been already defined for CLP, and that none of them were specifically designed for dependency detection, the aim of the evaluation is not only to asses the effectiveness of the available domains, but also to study what additional information it would be desirable to infer, and what domains would be appropriate for further improving the parallelization process.

Independence and search space preservation in dynamically scheduled constraint logic languages

This paper performs a further generalization of the notion of independence in constraint logic programs to the context of constraint logic programs with dynamic scheduling. The complexity of this new environment made necessary to first formally define the relationship between independence and search space preservation in the context of CLP languages. In particular, we show that search space preservation is, in the context of CLP languages, not only a sufficient but also a necessary condition for ensuring that both the intended solutions and the number of transitions performed do not change. These results are then extended to dynamically scheduled languages and used as the basis for the extension of the concepts of independence. We also propose several a priori sufficient conditions for independence and also give correctness and efficiency results for parallel execution of constraint logic programs based on the proposed notions of independence.

Rebalancing urban mobility: a tale of four cities

The key of mobility in urban planning is not in dispute. Integrated strategies that take into account the interrelations among land use, transport supply and demand and the different transportation modes are more necessary than ever. In Europe, regulatory tools such as local mobility plans or traffic plans have been enforced for a long time, evolving into so-called sustainable urban transport plans (SUTP) ? that is, plans thatmerge urban planning,mobility governance, social awareness and environmental safeguards to develop a vision based on sustainability and equity. Indeed, SUTP are aimed at solving typical problems in current land use, such as urban sprawl, which make clear the need for a paradigm shift from transport (or mobility) planning to land use (or city) planning, thereby producing urban mobility plans that are fully aligned with integrated urban development plans. This paper describes how SUTP are articulated across Europe according to four case studies: Peterborough (UK), Chambe¿ry (France), Ferrara (Italy) and Pinto (Spain), to highlight variations and commonalities, both among the four national legal frameworks and the actual planning processes at the local level. Objectives, measures and indicators used in the monitoring and evaluation phases have been analysed and the results assessed. The main conclusion of the paper is that, as seen in these real-life examples, the lack of integration between spatial planning and transport strategies results in the unsustainability of urban areas and, therefore, in a significant loss of competitiveness.

A constraint-based approach to quality assurance in service choreographies.

Knowledge about the quality characteristics (QoS) of service com- positions is crucial for determining their usability and economic value. Ser- vice quality is usually regulated using Service Level Agreements (SLA). While end-to-end SLAs are well suited for request-reply interactions, more complex, decentralized, multiparticipant compositions (service choreographies) typ- ically involve multiple message exchanges between stateful parties and the corresponding SLAs thus encompass several cooperating parties with interde- pendent QoS. The usual approaches to determining QoS ranges structurally (which are by construction easily composable) are not applicable in this sce- nario. Additionally, the intervening SLAs may depend on the exchanged data. We present an approach to data-aware QoS assurance in choreographies through the automatic derivation of composable QoS models from partici- pant descriptions. Such models are based on a message typing system with size constraints and are derived using abstract interpretation. The models ob- tained have multiple uses including run-time prediction, adaptive participant selection, or design-time compliance checking. We also present an experimen- tal evaluation and discuss the benefits of the proposed approach.

Management of Urban Mobility to Control Climate Change in Cities

The need of decarbonization of urban mobility is one of the main priorities for all countries to achieve greenhouse gas (GHG) emissions reduction targets. In general, the transport modes which have experienced the most growth in recent years tend to be the most polluting. Most efforts have been focused on the vehicle efficiency improvements and vehicle fleet renewal; nevertheless more emphasis should be placed on strategies related to the management of urban mobility and modal share. Research of individual travel which analyzes CO2 emissions and car and public transport share in daily mobility will enable better assessments of the potential of urban mobility measures introduced to limit GHG emissions produced by transport in cities. This paper explores the sustainability impacts of daily mobility in Spain using data from two National Travel Surveys (NTSs) (2000 and 2006) and includes a method by which to estimate the CO2 emissions associated with each journey and each surveyed individual. The results demonstrate that in the 2000 to 2006 period, there has been an increase in daily mobility which has led to a 17% increase in CO2 emissions. When separated by transport mode, cars prove to be the main contributor to that increase, followed by public transport. More focus should be directed toward modal shift strategies which not only take the number of journeys into account but also consider distance. The contributions of this paper have potential applications in the assessment of current and future urban transport policies.