Self-organising coordination systems

Many research fields are pushing the engineering of large-scale, mobile, and open systems towards the adoption of techniques inspired by self-organisation: pervasive computing, but also distributed artificial intelligence, multi-agent systems, social networks, peer-topeer and grid architectures exploit adaptive techniques to make global system properties emerge in spite of the unpredictability of interactions and behaviour. Such a trend is visible also in coordination models and languages, whenever a coordination infrastructure needs to cope with managing interactions in highly dynamic and unpredictable environments. As a consequence, self-organisation can be regarded as a feasible metaphor to define a radically new conceptual coordination framework. The resulting framework defines a novel coordination paradigm, called self-organising coordination, based on the idea of spreading coordination media over the network, and charge them with services to manage interactions based on local criteria, resulting in the emergence of desired and fruitful global coordination properties of the system. Features like topology, locality, time-reactiveness, and stochastic behaviour play a key role in both the definition of such a conceptual framework and the consequent development of self-organising coordination services. According to this framework, the thesis presents several self-organising coordination techniques developed during the PhD course, mainly concerning data distribution in tuplespace-based coordination systems. Some of these techniques have been also implemented in ReSpecT, a coordination language for tuple spaces, based on logic tuples and reactions to events occurring in a tuple space. In addition, the key role played by simulation and formal verification has been investigated, leading to analysing how automatic verification techniques like probabilistic model checking can be exploited in order to formally prove the emergence of desired behaviours when dealing with coordination approaches based on self-organisation. To this end, a concrete case study is presented and discussed.

Paleontological studies of Cretaceous vertebrate fossil beds in the Tataouine Basin (southern Tunisia)

The ‘Continental Intercalaire’ deposits of the Tataouine basin of southern Tunisia preserve one of the most diverse Cretaceous vertebrate fauna from Africa. This research project focuses on a detailed revision of the stratigraphic distribution of mid-Cretaceous fossil beds in the Tataouine Basin and includes the description of four, newly discovered vertebrate tracksites. In the Tataouine region, macro- and microvertebrate remains are recovered from three stratigraphic intervals: the lower Douiret Formation (Barremian), the Chenini (rare) and Oum ed Diab members of the Aïn El Guettar Formation (Albian). A detailed, basin-scale revision of the stratigraphic occurrence of fossil-bearing strata indicates 1. lateral facies variability within the context of a low gradient, circalittoral to coastal-plain environment; 2. multiple and diachronous fossil beds which include elasmobranchs, actinopterygians, sarcopterygians, turtles, crocodyliforms, pterosaurs, and non-avian dinosaurs remains. Four vertebrate tracksites have been discovered in the study area: 1. the Middle Jurassic Beni Ghedir site which preserves approximately 130 tridactyl footprints distributed over an area of 200 square meters, representing the oldest evidence of a dinosaur fauna in Tunisia; 2. the late Albian Chenini tracksite, which includes poorly preserved crocodilian tracks and the dinosaur ichnospecies Apulosauripus federicianus; 3. the Cenomanian Ksar Ayaat locality, where footprints assigned to a pleurodiran turtle are exposed, and 4. the upper Cenomanian Jebel Boulouha site which presents almost 100 well-preserved tridactyl tracks referred to small-sized theropods, fossil bird tracks - ichnogenus Koreanaorins – and tracks referred to a mammalian trackmaker, representing the first report of fossil bird and mammal from the Cretaceous of continental Africa and Tunisia respectively. In addition, data collected from the Tunisian tracksites have been compared with coeval tracksites in Italy and Croatia, showing analogies in morphology and paleoenvironment of dinosaur ichnoassociations, supporting the already hypothesized subaerial connection between these areas during the mid-Cretaceous.

Use of shared memory in the context of embedded multi-core processors: exploration of the technology and its limits

Modern embedded systems embrace many-core shared-memory designs. Due to constrained power and area budgets, most of them feature software-managed scratchpad memories instead of data caches to increase the data locality. It is therefore programmers’ responsibility to explicitly manage the memory transfers, and this make programming these platform cumbersome. Moreover, complex modern applications must be adequately parallelized before they can the parallel potential of the platform into actual performance. To support this, programming languages were proposed, which work at a high level of abstraction, and rely on a runtime whose cost hinders performance, especially in embedded systems, where resources and power budget are constrained. This dissertation explores the applicability of the shared-memory paradigm on modern many-core systems, focusing on the ease-of-programming. It focuses on OpenMP, the de-facto standard for shared memory programming. In a first part, the cost of algorithms for synchronization and data partitioning are analyzed, and they are adapted to modern embedded many-cores. Then, the original design of an OpenMP runtime library is presented, which supports complex forms of parallelism such as multi-level and irregular parallelism. In the second part of the thesis, the focus is on heterogeneous systems, where hardware accelerators are coupled to (many-)cores to implement key functional kernels with orders-of-magnitude of speedup and energy efficiency compared to the “pure software” version. However, three main issues rise, namely i) platform design complexity, ii) architectural scalability and iii) programmability. To tackle them, a template for a generic hardware processing unit (HWPU) is proposed, which share the memory banks with cores, and the template for a scalable architecture is shown, which integrates them through the shared-memory system. Then, a full software stack and toolchain are developed to support platform design and to let programmers exploiting the accelerators of the platform. The OpenMP frontend is extended to interact with it.

Engineering Complex Computational Ecosystems

Self-organising pervasive ecosystems of devices are set to become a major vehicle for delivering infrastructure and end-user services. The inherent complexity of such systems poses new challenges to those who want to dominate it by applying the principles of engineering. The recent growth in number and distribution of devices with decent computational and communicational abilities, that suddenly accelerated with the massive diffusion of smartphones and tablets, is delivering a world with a much higher density of devices in space. Also, communication technologies seem to be focussing on short-range device-to-device (P2P) interactions, with technologies such as Bluetooth and Near-Field Communication gaining greater adoption. Locality and situatedness become key to providing the best possible experience to users, and the classic model of a centralised, enormously powerful server gathering and processing data becomes less and less efficient with device density. Accomplishing complex global tasks without a centralised controller responsible of aggregating data, however, is a challenging task. In particular, there is a local-to-global issue that makes the application of engineering principles challenging at least: designing device-local programs that, through interaction, guarantee a certain global service level. In this thesis, we first analyse the state of the art in coordination systems, then motivate the work by describing the main issues of pre-existing tools and practices and identifying the improvements that would benefit the design of such complex software ecosystems. The contribution can be divided in three main branches. First, we introduce a novel simulation toolchain for pervasive ecosystems, designed for allowing good expressiveness still retaining high performance. Second, we leverage existing coordination models and patterns in order to create new spatial structures. Third, we introduce a novel language, based on the existing ``Field Calculus'' and integrated with the aforementioned toolchain, designed to be usable for practical aggregate programming.