Teaching computer science (CS) at all school levels is an increasingly important issue that has recently attracted the attention of institutions and policymakers. However, there is a shortage of qualified teachers which highlights an urgent need for training initiatives. To design such initiatives, it is crucial to assess teachers' baseline CS knowledge, identifying possible gaps. This study aims to articulate a proposal for a classification of tools that can be employed to assess teachers' CS knowledge. A literature review was conducted to collect relevant studies that present and/or utilize tools for assessing teachers' CS knowledge and competencies. We have identified key dimensions under which the tools can be examined: the data collection method, the nature of tasks assigned, how their reflection and action are triggered, whether the tool focuses on teachers' products or cognitive processes, and whether it also assesses their pedagogical content knowledge. For each dimension, we have identified a range of possible descriptors, leading to the development of a synoptic table categorizing the tools. This framework also enables us to compare the tools based on their features, highlighting their strengths and applications. This work makes two contributions: first, it introduces a framework for describing and comparing tools to unveil teachers' CS knowledge. Second, it offers a collection of tools for assessing it. This approach not only aids in selecting suitable tools for specific contexts but also provides a foundation for designing CS-knowledge assessment tools, enriching the resources available for analyzing educational needs and developing high-quality teacher training programs.

In the rapidly evolving landscape of STEAM disciplines, the demand for multidisciplinary communication, problem-solving skills, and creativity has become increasingly critical. Traditional educational curricula often fall short in preparing students with the competencies needed to navigate these complex, interdisciplinary challenges in their professional careers. This study explores the outcomes of a three-day co-design spring school involving 27 students from diverse STEAM fields. The focus is on how participation in community-driven, real-world design activities influenced their self-efficacy, growth mindset, and creative problem-solving abilities. To achieve this, we employed a mixed-methods approach, incorporating pre- and post-questionnaires, student diaries, design artifacts, and observational notes. The pre-questionnaire aimed to establish a baseline for creative problem-solving styles and mindset using a reduced version of the Basadur Creative Problem Solving Profile (CPSP), as well as self-efficacy using selected items from Limeri's mindset scale. The post-program assessments measured changes in these dimensions and further explored participants' perceptions of the experience. The results indicate that students reported experimenting with a different creative approach than their usual one. Additionally, their involvement in a co-design activity targeting the local community and a real world problem significantly influenced the way they approached tasks. Creative style “contamination” was particularly observed in engineering students, who shifted from evaluative to ideative and thinking styles. While mindsets, due to their nature, exhibited limited and non-significant shifts, participants expressed a stronger belief in their ability to con-tribute to meaningful, real-world projects in terms of a growth mindset. Self-efficacy showed significant improvement, but only in terms of increased confidence in performing diverse tasks. The findings emphasize the importance of co-design ‘for people’ and real-world design projects to promote creative adaptability, improve teamwork between disciplines, and encourage students to step outside their comfort zones. In the long term, this approach offers a promising model for STEAM education, preparing students for an increasingly complex and interdisciplinary professional world.

This paper presents an exploratory sociological research study focusing on the perceptions and awareness of coding among youth aged 16 to 24 in Trento, Italy, with an emphasis on gender inclusivity. It combines theoretical and practical perspectives to understand the role of coding in today's knowledge society, focusing on gender dynamics in coding education. Using qualitative methods such as interviews and focus groups, the study involved a gender-balanced mix of students and educators from various backgrounds. It centers on four themes: coding knowledge among youth, the benefits of coding, the effectiveness of coding education, and the role of gamification in enhancing coding awareness. The findings highlight significant gender differences in interest and participation in coding, stressing the need for inclusive teaching methods like gamification to promote coding literacy across genders. The paper underscores the importance of gender inclusivity in computer science education to enhance future digital competencies and employability.11Acknowledgments: We would like to extend our gratitude to the students from the Qualitative Research courses in the Sociology Department at the University of Trento, under the guidance of Prof. Chiara Bassetti and Prof. Vincenzo D'Andrea, for their contribution to this research: Alice Conati, Giulia Fasoli, Irene Negri, Alessio Roat, Nadia Scatola, and Filippo Tomezzoli. Their engagement in conducting the interviews and coding the results was instrumental to the success of this study.

We present an interactive Web platform that, given a directed graph, allows identifying the most relevant nodes related to a given query node. Besides well-established algorithms such as PageRank and Personalized PageRank, the demo includes Cyclerank, a novel algorithm that addresses some of their limitations by leveraging cyclic paths to compute personalized relevance scores. Our demo design enables two use cases: (a) algorithm comparison, comparing the results obtained with different algorithms, and (b) dataset comparison, for exploring and gaining insights into a dataset and comparing it with others. We provide 50 pre-loaded datasets from Wikipedia, Twitter, and Amazon and seven algorithms. Users can upload new datasets, and new algorithms can be easily added. By showcasing efficient algorithms to compute relevance scores in directed graphs, our tool helps to uncover hidden relationships within the data, which makes of it a valuable addition to the repertoire of graph analysis algorithms.

Recently developed at the University of Trento in Italy, ApeLab is a Fablab on wheels that encompasses the concept, design, and tools necessary to provide a mobile laboratory experience. The Piaggio Ape Car has been converted into a Fablab, making ApeLab a portable space equipped with digital manufacturing machines and other features. The project aims to promote STEAM education and digital manufacturing through hands-on learning activities, encourage scientific communication in an easy and creative way, and generate curiosity and creativity among people of all ages by raising awareness of important scientific topics that are often overlooked.

Contribution: This study aimed to develop, test, and evaluate an educational kit for high schools that fosters a multidisciplinary bond between physics and computer science. Grounded in constructionism, the kit encourages students to take a more practical approach towards STEM subjects by using simple Arduino-based boards and sensors to measure physical quantities during simple experiments. The project was a collaborative effort between the University of Trento and Level Up, a local company that produces innovative educational materials related to physics and science for schools. The study involved 16 high schools with over 300 students and about 20 physics and informatics teachers. The kits were validated through questionnaires and interviews, with an emphasis on assessing changes in student motivation, interest in STEM subjects, and practical experience. Background: The learning-by-doing approach is central to constructionism, which emphasizes the importance of hands-on, experiential learning in education. This approach is often neglected in the Italian school system, which tends to prioritize theoretical studies that are distant from real-world problems and applications. Part of the problem is the lack of experimental sets available to each student. Intended outcomes: First, to create an educational kit that high school teachers could use to provide their students with practical experience in their physics curricula and enable them to apply their knowledge of computer science to arrive at better results. Second, to measure a change in students' interest in STEM subjects once they experience a more practical approach using the educational instrumentation created in the project. Another goal was to increase their motivation and engagement in the learning-by-doing process and to help them understand the importance of a multidisciplinary approach. Findings: The students who participated in the project were asked to complete two questionnaires regarding their approach and motivation towards STEM subjects, both before and after using the educational kit. The answers were divided by gender to determine if there were any differences in approach. The study recorded a very positive response from the students and a growing motivation towards this type of hands-on method used during classes.

One of the primary difficulties of fishermen engaged in deep-sea fishing is the lack of effective communication systems to the shore. The Offshore Communication Network(OCN) resolves this problem by providing Internet over the ocean through a fishing vessel network. OCN is a multi-layered architecture with heterogeneous connectivity ranges, directionality, resources, and mobility patterns. Connectivity maintenance is challenging due to the lack of infrastructure, expanded mobility, network sparsity, and sea-wave-induced movements. This paper discusses a framework to improve OCN connectivity with a multi-level optimization strategy. We propose a predictive model to generate real-time forecasts of link status. At the physical level, node position re-orientations to higher connectivity locations are suggested. The transmission queue management and prioritized scheduling in the link-layer minimize the queuing delay. A reinforcement routing strategy in the network layer determines the best next-hop for message dissemination. The proposed three-level optimization approach facilitates communication capability enhancement in OCN.

In recommender systems (RSs), predicting the next item that a user interacts with is critical for user retention. While the last decade has seen an explosion of RSs aimed at identifying relevant items that match user preferences, there is still a range of aspects that could be considered to further improve their performance. For example, often RSs are centered around the user, who is modeled using her recent sequence of activities. Recent studies, however, have shown the effectiveness of modeling the mutual interactions between users and items using separate user and item embeddings.

This paper introduces a data model for representing humans-chatbots interactions. Despite there are many models that allow representing the usage and the behaviour of bots, a service that can store information from any conversational agent regardless the architecture is still missing. With this work, we introduce a general-purpose data model to store both messages and logs. To succeed, we raise the level of abstraction of the other analyzed models and we focused on the core logic of chatbots: conversations and interactions with the users

Many optimization techniques for networking protocols take advantage of topological information to improve performance. Often, the topological information at the core of these techniques is a centrality metric such as the Betweenness Centrality (BC) index. BC is, in fact, a centrality metric with many well-known successful applications documented in the literature, from resource allocation to routing. To compute BC, however, each node must run a centralized algorithm and needs to have the global topological knowledge; such requirements limit the feasibility of optimization procedures based on BC. To overcome restrictions of this kind, we present a novel distributed algorithm that requires only local information to compute an alternative similar metric, called Load Centrality (LC). We present the new algorithm together with a proof of its convergence and the analysis of its time complexity. The proposed algorithm is general enough to be integrated with any distance vector (DV) routing protocol. In support of this claim, we provide an implementation on top of Babel, a real-world DV protocol. We use this implementation in an emulation framework to show how LC can be exploited to reduce Babel's convergence time upon node failure, without increasing control overhead. As a key step towards the adoption of centrality-based optimization for routing, we study how the algorithm can be incrementally introduced in a network running a DV routing protocol. We show that even when only a small fraction of nodes participate in the protocol, the algorithm accurately ranks nodes according to their centrality.

A relevant task in the exploration and understanding of large datasets is the discovery of hidden relationships in the data. In particular, functional dependencies have received considerable attention in the past. However, there are other kinds of relationships that are significant both for understanding the data and for performing query optimization. Order dependencies belong to this category. An order dependency states that if a table is ordered on a list of attributes, then it is also ordered on another list of attributes. The discovery of order dependencies has been only recently studied. In this paper, we propose a novel approach for discovering order dependencies in a given dataset. Our approach leverages the observation that discovering order dependencies can be guided by the discovery of a more specific form of dependencies called order compatibility dependencies. We show that our algorithm outperforms existing approaches on real datasets. Furthermore, our algorithm can be parallelized leading to further improvements when it is executed on multiple threads. We present several experiments that illustrate the effectiveness and efficiency of our proposal and discuss our findings.

The old mantra of decentralizing the Internet is coming again with fanfare, this time around the blockchain technology hype. We have already seen a technology supposed to change the nature of the Internet: peer-to-peer. The reality is that peer-to-peer naming systems failed, peer-to-peer social networks failed, and yes, peer-to-peer storage failed as well. In this paper, we will review the research on distributed systems in the last few years to identify the limits of open peer-to-peer networks. We will address issues like system complexity, security and frailty, instability and performance. We will show how many of the aforementioned problems also apply to the recent breed of permissionless blockchain networks. The applicability of such systems to mature industrial applications is undermined by the same properties that make them so interesting for a libertarian audience: namely, their openness, their pseudo-anonymity and their unregulated cryptocurrencies. As such, we argue that permissionless blockchain networks are unsuitable to be the substrate for a decentralized Internet. Yet, there is still hope for more decentralization, albeit in a form somewhat limited with respect to the libertarian view of decentralized Internet: in cooperation rather than in competition with the superpowerful datacenters that dominate the world today. This is derived from the recent surge in interest in byzantine fault tolerance and permissioned blockchains, which opens the door to a world where use of trusted third parties is not the only way to arbitrate an ensemble of entities. The ability of establish trust through permissioned blockchains enables to move the control from the datacenters to the edge, truly realizing the promises of edge-centric computing.

Centrality metrics are a key instrument for graph analysis and play a central role in many problems related to networking such as service placement, robustness analysis and network optimization. Betweenness centrality is one of the most popular and well-studied metric. While distributed algorithms to compute this metric exist, they are either approximated or limited to certain topologies (directed acyclic graphs or trees). Exact distributed algorithms for betweenness centrality are computationally complex, because its calculation requires the knowledge of all possible shortest paths within the graph. In this paper we consider load centrality, a metric that usually converges to betweenness, and we present the first distributed and exact algorithm to compute it. We prove its convergence, we estimate its complexity and we show it is directly applicable-with minimal modifications-to any distance-vector routing protocol based on Bellman-Ford. We finally implement it on top of the Babel routing protocol and we show that, exploiting centrality, we can significantly reduce Babel's convergence time upon node failure without increasing signalling overhead. Our contribution is relevant in the realm of wireless distributed networks, but the algorithm can be adopted in any distributed system where it is not possible, or computationally impractical, to reconstruct the whole network graph at each node and compute betweenness centrality with the classical approach based on Dijkstra's algorithm.

In many aspects of human activity, there has been a continuous struggle between the forces of centralization and decentralization. Computing exhibits the same phenomenon; after having abandoned mainframes in favor of PCs, the last decade has witnessed an unparalleled centralization and consolidation of services in data centers and clouds. Yet, trust, privacy, security and autonomy concerns are requiring to shift control again, taking services from the central nodes (the "core") to the other logical extreme (the "edge") of the Internet. This development can help blurring the boundary between man and machine, and embrace social computing in which humans are part of the computation and decision-making loop, resulting in a human-centered system design. In this tutorial we will elaborate on the necessary steps to be taken and challenges to be solved to realize this vision. The tutorial will include an overview of related research topics, including peerto-peer networks, blockchains, hybrid and decentralized cloud architectures.

Distributed graph processing has become a very popular research topic recently, particularly in domains such as the analysis of social networks, web graphs and spatial networks. In this context, graph partitioning is an important task. Several partitioning algorithms have been proposed, such as DFEP, JABEJA and POWERGRAPH, but they are limited to static graphs only. In fact, they do not consider dynamic graphs in which vertices and edges are added and/or removed. In this paper, we propose a graph partitioning method for large dynamic graphs. We present an implementation of the proposed approach on top of the AKKA framework, and we experimentally show that our approach is efficient in the case of large dynamic graphs.

In peer-to-peer applications deployed on the Internet, it is common to assign greater responsibility to supernodes, which are usually peers with high computational power, large amount of memory, or high network bandwidth capacity. In this paper, we describe a practical solution to the problem of supernode selection, that is the process of discovering the best peers in the network by some application-specific metric. We provide a distributed heuristic that allows to identify the best K nodes in the P2P overlay, by taking into consideration the realities of actual deployments, such as the presence of NATs. Our approach consists of an epidemic protocol which does not require new connections to be established, but rather relies on established connections, such as the ones provided by a NAT-resilient peer sampling framework. We support our claims with a thorough evaluation of our solution in simulation and in a real deployment on thousands of consumer machines.

When Google first introduced the Map/Reduce paradigm in 2004, no comparable system had been available to the general public. The situation has changed since then. The Map/Reduce paradigm has become increasingly popular and there is no shortage of Map/Reduce implementations in today's computing world. The predominant solution is currently Apache Hadoop, started by Yahoo. Besides employing custom Map/Reduce installations, customers of cloud services can now exploit ready-made made installations (e.g. the Elastic Map/Reduce System). In the mean time, other, second generation frameworks have started to appear. They either fine tune the Map/Reduce model for specific scenarios, or change the paradigm altogether, such as Google's Pregel. In this paper, we present a comparison between these second generation frameworks and the current de-facto standard Hadoop, by focusing on a specific scenario: large-scale graph analysis. We analyze the different means of fine-tuning those systems by exploiting their unique features. We base our analysis on the k-core decomposition problem, whose goal is to compute the centrality of each node in a given graph; we tested our implementation in a cluster of Amazon EC2 nodes with realistic datasets made publicly available by the SNAP project.

Monitoring the global state of an overlay network is vital for the self-management of peer-to-peer (P2P) systems. Gossip-based algorithms are a well-known technique that can provide nodes locally with aggregated knowledge about the state of the overlay network. In this paper, we present a gossip-based protocol to estimate the global distribution of attribute values stored across a set of nodes in the system. Our algorithm estimates the distribution both efficiently and accurately. The key contribution of our algorithm is that it has substantially lower overhead than existing distribution estimation algorithms. We evaluated our system in simulation, and compared it against the state-of-the-art solutions. The results show similar accuracy to its counterparts, but with a communication overhead of an order of magnitude lower than them.

Decentralized social networks are an emerging solution to the privacy issues plaguing mainstream centralized architectures. Social overlays-overlay networks mirroring the social relationships among node owners-are particularly intriguing, as they limit communication within one's friend circle. Previous work investigated efficient protocols for P2P dissemination in social overlays, but also showed that the churn induced by users, combined with the topology constraints posed by these overlays, may yield unacceptable latency. In this paper, we combine P2P dissemination on the social overlay with occasional access to the cloud. When updates from a friend are not received for a long time, the cloud serves as an external channel to verify their presence. The outcome is disseminated in a P2P fashion, quenching cloud access from other nodes and speeding dissemination of existing updates. We show that our protocol performs close to centralized architectures and incurs only modest monetary costs.

Several novel metrics have been proposed in recent literature in order to study the relative importance of nodes in complex networks. Among those, k-coreness has found a number of applications in areas as diverse as sociology, proteinomics, graph visualization, and distributed system analysis and design. This paper proposes new distributed algorithms for the computation of the k-coreness of a network, a process also known as k-core decomposition. This technique 1) allows the decomposition, over a set of connected machines, of very large graphs, when size does not allow storing and processing them on a single host, and 2) enables the runtime computation of k-cores in “live” distributed systems. Lower bounds on the algorithms complexity are given, and an exhaustive experimental analysis on real-world data sets is provided.

Peer-to-peer systems based on an overlay network that mirrors the social relationships among the nodes' owners are increasingly attracting interest. Yet, the churn induced by the availability of users raises the question-still unanswered-of whether these social overlays represent a viable solution. Indeed, although constraining communication to take place only among “friends” brings many benefits, it also introduces significant limitations when healing the overlay in the presence of churn. This paper puts forth two contributions. First, we show through simulation on real datasets that churn induces relevant delays in information dissemination, which may ultimately hamper the practical application of social overlays. Yet, identifying opportunities for improvement and evaluating design alternatives through simulation is impractical, due to the size of the target networks, the large parameter space, and the many sources of randomness involved. Therefore, in our second contribution we combine analytical and simulation techniques to enable the estimation of dissemination delays at a practical cost.

Peer-to-peer (P2P) video streaming is an emerging technology that reduces the barrier to stream live events over the Internet. Unfortunately, satisfying soft real-time constraints on the delay between the generation of the stream and its actual delivery to users is still a challenging problem. Bottlenecks in the available upload bandwidth, both at the media source and inside the overlay network, may limit the quality of service (QoS) experienced by users. A potential solution for this problem is assisting the P2P streaming network by a cloud computing infrastructure to guarantee a minimum level of QoS. In such approach, rented cloud resources (helpers) are added on demand to the overlay, to increase the amount of total available bandwidth and the probability of receiving the video on time. Hence, the problem to be solved becomes minimizing the economical cost, provided that a set of constraints on QoS is satisfied. The main contribution of this paper is CLIVE, a cloud-assisted P2P live streaming system that demonstrates the feasibility of these ideas. CLIVE estimates the available capacity in the system through a gossip-based aggregation protocol and provisions the required resources from the cloud to guarantee a given level of QoS at low cost. We perform extensive simulations and evaluate CLIVE using large-scale experiments under dynamic realistic settings.

Online social networks (OSN) have attracted millions of users worldwide. This enormous success is not without problems; the centralized architectures of OSNs, storing the users' personal data, provides ample opportunity for privacy violation - a fact that has raised the demand for open, decentralized alternatives. We tackle the research question: is it possible to build a decentralized OSN over a social overlay, i.e., an overlay network whose links among nodes mirror the social network relationships among the nodes' owners? This paper provides a stepping stone to the answer, by focusing on the key OSN functionality of disseminating profile updates. Our approach relies on gossip protocols. We show that mainstream gossip protocols are inefficient, due to the properties that characterize social networks. We then leverage these very same properties towards our goal, by appropriately modifying gossip forwarding rules. Our evaluation, performed in simulation over a crawled real-world social network, shows that our protocols provide acceptable latency, foster load balancing across nodes, and tolerate churn.

Peer-to-peer (P2P) and cloud computing, two of the Internet trends of the last decade, hold similar promises: the (virtually) infinite availability of computing and storage resources. But there are important differences: the cloud provides highly-available resources, but at a cost; P2P resources are for free, but their availability is shaky. Several academic and commercial projects have explored the possibility of mixing the two, creating a large number of peer-assisted applications, particularly in the field of content distribution, where the cloud provides a highly-available and persistent service, while P2P resources are exploited for free whenever possible to reduce the economic cost. While executing active servers on elastic computing facilities like Amazon EC2 and pairing them with user-provided peers is definitely one way to go, this paper proposes a novel approach that further reduces the economic cost. Here, a passive storage service like Amazon S3 is exploited not only to distribute content to clients, but also to build and manage the P2P network linking them. An effort is made to guarantee that the read/write load imposed on the storage remains constant, regardless of the number of peers/clients. These two choices allows us to keep the monetary cost of the cloud always under control, in the presence of just one peer or with a million of them. We show the feasibility of our approach by discussing two cases studies for content distribution: the Dilbert's comic strips and the hourly News Update podcast from CNN.

Among the novel metrics used to study the relative importance of nodes in complex networks, k-core decomposition has found a number of applications in areas as diverse as sociology, proteinomics, graph visualization, and distributed system analysis and design. This paper proposes new distributed algorithms for the computation of the k-core decomposition of a network, with the purpose of (i) enabling the run-time computation of k-cores in "live" distributed systems and (ii) allowing the decomposition, over a set of connected machines, of very large graphs, that cannot be hosted in a single machine. Lower bounds on the algorithms complexity are given, and an exhaustive experimental analysis on real-world graphs is provided.

Botnets have become the most sophisticated and dangerous way of spreading malware. Their damaging actions can range from massive dispatching of e-mail messages, to denial of service attacks, to collection of private and sensitive information. Unlike standard computer viruses or worms, botnets spread silently without actively operating their damaging activity, and then are activated in a coordinated way to maximize the ``benefit'' of the malware. In this paper we propose two models based on compartmental differential equations derived from ``standard'' models in biological disease preading. These models offer insight into the general behavior of botnets, allowing both the optimal tuning of botnets' characteristics, and possible countermeasures to prevent them.

P2P-based optimization has recently gained interest among distributed function optimization scientists. Several well-known optimization heuristics have been recently re-designed to exploit the peculiarity of such a distributed environment. The final goal is to perform high quality function optimization by means of inexpensive, fully decentralized machines, which may either be purposely organized in a P2P network, or voluntarily join a running P2P optimization task. In this paper we present the GoDE algorithm (Gossip-based Differential Evolution), which obtains remarkable results on several test functions. We describe in detail the algorithm design and the epidemic mechanism that greatly improves the performance. Experimental results in a simulated environment show how GoDE adapts to network scale and how the epidemic communication protocol can make the algorithm achieve good results even in presence of a high churn rate.

Hyper-heuristics (HHs) are heuristics that work with an arbitrary set of search operators or algorithms and combine these algorithms adaptively to achieve a better performance than any of the original heuristics. While HHs lend themselves naturally for distributed deployment, relatively little attention has been paid so far on the design and evaluation of distributed HHs. To our knowledge, our work is the first to present a detailed evaluation and comparison of distributed HHs for real parameter optimization in an island model. Our set of test functions includes well-known benchmark functions and two realistic space-probe trajectory optimization problems. The set of algorithms available to the HHs include several variants of differential evolution, and uniform random search. Our main conclusion is that some of the simplest HHs are surprisingly successful in a distributed environment, and the best HHs we tested provide a robust and stable good performance over a wide range of scenarios and parameters.

This paper describes T-SIZE, a peer counting protocol that is based on gossip-based aggregation. Peer counting has become increasingly important as the size of the network is often a crucial parameter used to guarantee robustness, small diameter, load-balance, or to generally optimize the system. Our work improves the previous work by providing a protocol that is eventually accurate, i.e. the estimate will eventually converge to the true peer count in absence of churn. The protocol can handle extreme levels of churn, and automatically ensures that all participating nodes learn the outcome of the peer counting.

The key features of peer-to-peer (P2P) systems are scalability and dynamism. The evaluation of a P2P protocol in realistic environments is very expensive and difficult to reproduce, so simulation is crucial in P2P research. PeerSim is an extremely scalable simulation environment that supports dynamic scenarios such as churn and other failure models. Protocols need to be specifically implemented for the PeerSim Java API, but with a reasonable effort they can be evolved into a real implementation. Testing in specified parameter-spaces is supported as well. PeerSim started out as a tool for our own research.

Distributed estimation of global parameters in intermittently connected mobile environments is a challenging problem. In this paper, we introduce a set of methods, based on gossip techniques and population protocols, for performing such task. The applicability of such techniques to various environments, characterized by different mobility patterns, is evaluated through numerical simulations and discussed extensively. Guidelines are provided to help practitioners choosing the right method for their specific application problem.

We introduce a generic framework for the distributed execution of combinatorial optimization tasks. Instead of relying on custom hardware (like dedicated parallel machines or clusters), our approach exploits, in a peer-to-peer fashion, the computing and storage power of existing, off-the- shelf desktops and servers. Contributions of this paper are a description of the generic framework, together with a first instantiation based on particle swarm optimization (PSO). Simulation results are shown, proving the efficacy of our distributed PSO algorithm in optimizing a large number of benchmark functions.

Peer-to-peer (P2P) systems are slowly moving from application-specific architectures to a generic service- oriented design framework. The idea is to allow a dynamic collection of P2P applications to cohabit into a single system, with applications starting and terminating at will, or even changing their requirements at run-time. This raises an interesting problem in connection with managing resource assignment in a large-scale, heterogeneous and unreliable environment. Recently, the distributed slicing service has been proposed to allow for an automatic partitioning of P2P networks into groups (slices) that represent a controllable amount of some resource. A particular instantiation of such service has been described, called ordered slicing, in which nodes are ranked based on some metrics and then assigned to a slice based on their position in the ranking. In this paper, we present an alternative version of the problem called absolute slicing. Here, the goal is to assign a specified number of nodes to a slice and maintain such assignment in spite of churn. We propose a simple algorithm that solves the problem by combining well-known protocols such as peer sampling and aggregation, and we experimentally evaluate its performance.

Abstract This paper presents the design and implementation of Jgroup/ARM, a distributed object group platform with autonomous replication management along with a novel measurement‐based assessment technique that is used to validate the fault‐handling capability of Jgroup/ARM. Jgroup extends Java RMI through the group communication paradigm and has been designed specifically for application support in partitionable systems. ARM aims at improving the dependability characteristics of systems through a fault‐treatment mechanism. Hence, ARM focuses on deployment and operational aspects, where the gain in terms of improved dependability is likely to be the greatest. The main objective of ARM is to localize failures and to reconfigure the system according to application‐specific dependability requirements. Combining Jgroup and ARM can significantly reduce the effort necessary for developing, deploying and managing dependable, partition‐aware applications. Jgroup/ARM is evaluated experimentally to validate its fault‐handling capability; the recovery performance of a system deployed in a wide area network is evaluated. In this experiment multiple nearly coincident reachability changes are injected to emulate network partitions separating the service replicas. The results show that Jgroup/ARM is able to recover applications to their initial state in several realistic failure scenarios, including multiple, concurrent network partitionings. Copyright © 2007 John Wiley & Sons, Ltd.

The concept of superpeer has been introduced to improve the performance of popular P2P applications. A superpeer is a "powerful" node that acts as a server for a set of clients, and as an equal with respect to other superpeers. By exploiting heterogeneity, the superpeer paradigm can lead to improved efficiency, without compromising the decentralized nature of P2P networks. The main issues in constructing superpeer-based overlays are the selection of superpeers and the association between superpeers and clients. Generally, superpeers are either run voluntarily (without an explicit selection process), or chosen among the "best" nodes in the network, for example those with the most abundant resources, such as bandwidth or storage. In several contexts, however, shared resources are not the only factor; latency between clients and superpeers may play an important role, for example in online games and IP-Telephony applications. This paper presents SG-2, a novel protocol for building and maintaining proximity-aware superpeer topologies. SG-2 uses a gossip-based protocol to spread messages to nearby nodes and a biology-inspired task allocation mechanism to promote the "best" nodes to superpeer status. The paper includes extensive simulation experiments to prove the efficiency, scalability and robustness of SG-2.

Recent developments in information technology have brought about important changes in distributed computing. New environments such as massively large-scale, wide-area computer networks and mobile ad hoc networks have emerged. Common characteristics of these environments include extreme dynamicity, unreliability, and large scale. Traditional approaches to designing distributed applications in these environments based on central control, small scale, or strong reliability assumptions are not suitable for exploiting their enormous potential. Based on the observation that living organisms can effectively organize large numbers of unreliable and dynamically-changing components (cells, molecules, individuals, etc.) into robust and adaptive structures, it has long been a research challenge to characterize the key ideas and mechanisms that make biological systems work and to apply them to distributed systems engineering. In this article we propose a conceptual framework that captures several basic biological processes in the form of a family of design patterns. Examples include plain diffusion, replication, chemotaxis, and stigmergy. We show through examples how to implement important functions for distributed computing based on these patterns. Using a common evaluation methodology, we show that our bio-inspired solutions have performance comparable to traditional, state-of-the-art solutions while they inherit desirable properties of biological systems including adaptivity and robustness.

Structured peer-to-peer overlay networks are now an established paradigm for implementing a wide range of distributed services. While the problem of maintaining these networks in the presence of churn and other failures is the subject of intensive research, the problem of building them from scratch has not been addressed (apart from individual nodes joining an already functioning overlay). In this paper we address the problem of jump-starting a popular structured overlay, Chord, from scratch. This problem is of crucial importance in scenarios where one is assigned a limited time interval in a distributed environment such as Planet-Lab, or a grid, and the overlay infrastructure needs to be set up from the ground up as quickly and efficiently as possible, or when a temporary overlay has to be generated to solve a specific task on demand. We introduce T-Chord, that can build a Chord network efficiently starting from a random unstructured overlay. After jump-starting, the structured overlay can be handed over to the Chord protocol for further maintenance. We demonstrate through extensive simulation experiments that the proposed protocol can create a perfect Chord topology in a logarithmic number of steps. Furthermore, using a simple extension of the protocol, we can optimize the network from the point of view of message latency.

As computer networks increase in size, become more heterogeneous and span greater geographic distances, applications must be designed to cope with the very large scale, poor reliability, and often, with the extreme dynamism of the underlying network. Aggregation is a key functional building block for such applications: it refers to a set of functions that provide components of a distributed system access to global information including network size, average load, average uptime, location and description of hotspots, and so on. Local access to global information is often very useful, if not indispensable for building applications that are robust and adaptive. For example, in an industrial control application, some aggregate value reaching a threshold may trigger the execution of certain actions; a distributed storage system will want to know the total available free space; load-balancing protocols may benefit from knowing the target average load so as to minimize the load they transfer. We propose a gossip-based protocol for computing aggregate values over network components in a fully decentralized fashion. The class of aggregate functions we can compute is very broad and includes many useful special cases such as counting, averages, sums, products, and extremal values. The protocol is suitable for extremely large and highly dynamic systems due to its proactive structure---all nodes receive the aggregate value continuously, thus being able to track any changes in the system. The protocol is also extremely lightweight, making it suitable for many distributed applications including peer-to-peer and grid computing systems. We demonstrate the efficiency and robustness of our gossip-based protocol both theoretically and experimentally under a variety of scenarios including node and communication failures.

Aggregation refers to a set of functions that provide global information about a distributed system. These junctions operate on numeric values distributed over the system and can be used to count network size, determine extremal values and compute averages, products or sums. Aggregation allows important basic functionality to be achieved in fully distributed and peer-to-peer networks. For example, in a monitoring application, some aggregate reaching a specific value may trigger the execution of certain operations; distributed storage systems may need to know the total free space available; load-balancing protocols may benefit from knowing the target average load so as to minimize the transfered load. Building on the simple but efficient idea of antientropy aggregation (a scheme based on the antientropy epidemic communication model), in this paper we introduce practically applicable robust and adaptive protocols for proactive aggregation, including the calculation of average, product and extremal values. We show how the averaging protocol can be applied to compute further aggregates like sum, variance and the network size. We present theoretical and empirical evidence supporting the robustness of the averaging protocol under different scenarios.

Aggregation - that is, the computation of global properties like average or maximal load, or the number of nodes - is an important basic functionality in fully distributed environments. In many cases - which include protocols responsible for self-organization in large-scale systems and collaborative environments - it is useful if all nodes know the value of some aggregates continuously. We present and analyze novel protocols capable of providing this service. The proposed antientropy aggregation protocols compute different aggregates of component properties like extremal values, average and counting. Our protocols are inspired by the antientropy epidemic protocol where random pairs of databases periodically resolve their differences. In the case of aggregation, resolving difference is generalized to an arbitrary (numeric) computation based on the states of the two communicating peers. The advantage of this approach is that it is proactive and "democratic", which means it has no performance bottlenecks, and the approximation of the aggregates is present continuously at all nodes. These properties make our protocol suitable for implementing e.g. collective decision making or automatic system maintenance based on global information in a fully distributed fashion. As our main contribution we provide fundamental theoretical results on the proposed averaging protocol.

The concept of superpeer has been introduced to improve the performance of popular file-sharing applications. A superpeer is a node in a P2P network that operates as a server for a set of clients, and as an equal w.r.t. other superpeers. By exploiting heterogeneity, the superpeer paradigm allows P2P networks to run more efficiently, without compromising their decentralized nature. This paper describes SG-1, a novel generic mechanism for the construction and the maintenance of overlay topologies based on superpeers. SG-1 is based on the well-known gossip paradigm, with nodes exchanging information with randomly selected peers and re-arranging the topology according to the requirements of the particular P2P application. The resulting protocol is extremely efficient and robust, capable to deal with a continuous flow of nodes joining and leaving the system, as well as to repair a network where up to 100% of the existing super-peers have been removed.

Peer-to-peer (P2P) has recently emerged as a promising model for supporting scalable networks composed of autonomous and spontaneously cooperating entities. The key concept in P2P is decentralization: the resources, the services, as well as the control are not in charge of specialized nodes in the network, but each node (called peer in this context) is directly involved in the management of all these aspects. Besides the advantages of decentralization (autonomy, adaptability, collaboration, and dinamicity just to mention few of them) one of the main drawbacks is the impossibility to predict the topology of the network, thus leaving at run-time any decision about the management of the interaction among the peers. For this reason, we consider useful to provide the developers of P2P applications with a high-level coordination language to be exploited to program the coordination among the peers. In this paper, we present [Formula: see text], a new data-driven coordination model suitable for P2P networks, and we describe [Formula: see text], an implementation of the [Formula: see text] coordination model based on the JXTA peer-to-peer technology.

Recent peer-to-peer (P2P) systems are characterized by decentralized control, large scale and extreme dynamism of their operating environment. As such, they can be seen as instances of complex adaptive systems (CAS) typically found in biological and social sciences. We describe Anthill, a framework to support the design, implementation and evaluation of P2P applications based on ideas such as multi-agent and evolutionary programming borrowed from CAS. An Anthill system consists of a dynamic network of peer nodes; societies of adaptive agents travel through this network, interacting with nodes and cooperating with other agents in order to solve complex problems. Anthill can be used to construct different classes of P2P services that exhibit resilience, adaptation and self-organization properties. We also describe preliminary experiences with Anthill in implementing a file sharing application.

Gives a formal specification and an implementation for a partitionable group communication service in asynchronous distributed systems. Our specification is motivated by the requirements for building "partition-aware" applications that can continue operating without blocking in multiple concurrent partitions and can reconfigure themselves dynamically when partitions merge. The specified service guarantees liveness and excludes trivial solutions, it constitutes a useful basis for building realistic partition-aware applications, and it is implementable in practical asynchronous distributed systems where certain stability conditions hold.

Network applications and services need to be environment-aware in order to meet non-functional requirements in increasingly dynamic contexts. We consider partition awareness as an instance of environment awareness in network applications that need to be reliable and self-managing. Partition-aware applications dynamically reconfigure themselves and adjust the quality of their services in response to partitioning and merging of networks. As such, they can automatically adapt to changes in the environment so as to remain available in multiple partitions without blocking, albeit with reduced or degraded functionality. We propose a system layer consisting of group membership and reliable multicast services that provides systematic support for partition-aware application development. We illustrate the effectiveness of the proposed interface by solving several problems that represent different classes of realistic network applications.