Graph analytics play a crucial role in a wide range of fields, including social network analysis, bioinformatics, and scientific computing, due to their ability to model and explore complex relationships. However, optimizing graph algorithms is inherently difficult due to their memory-bound constraints, often resulting in poor performance on modern massively parallel hardware. In addition, most state-of-the-art implementations are designed in CUDA for NVIDIA GPUs, and thus they can not run on supercomputers equipped with AMD and Intel GPUs. To address these challenges, we propose SYgraph, a portable heterogeneous graph analytics framework written in SYCL. SYgraph provides an efficient two-layer bitmap data layout optimized for GPU memory, eliminates the need for pre- or post-processing steps, and abstracts the complexity of working with diverse target platforms. Experimental results demonstrate that SYgraph delivers competitive performance against state-of-the-art frameworks on datasets with up to 21 million nodes and 530 million edges on NVIDIA GPUs while being able to target any SYCL-supported device, such as AMD and Intel GPUs.

Socially engaging interactive systems, like virtual agents, can be employed as "companions" or "therapists", promoting wellbeing and mental health. To favor the actual usage of this kind of technologies, it is crucial to identify the features influencing users’ perception and acceptance toward them. Traditionally, user acceptance is assessed through self-report questionnaires which, however, do not shed light on the affective and motivational state of users during the interaction. These important aspects could be explored through EEG signal analysis, which would provide an objective measure of users’ preferences and usage intentions. This work investigates the relationship between users’ willingness to interact with virtual agents and frontal alpha activity, trying to provide useful insights on the affective and motivational states of users, with and without depressive symptoms, when interacting with happy, neutral and sad virtual agents.

Subgraph isomorphism is a fundamental graph problem with applications in diverse domains from biology to social network analysis. Of particular interest is molecular matching, which uses a subgraph isomorphism formulation for the drug discovery process. While subgraph isomorphism is known to be NP-complete and computationally expensive, in the molecular matching formulation a number of domain constraints allow for efficient implementations. This paper presents SIGMo, a high-throughput, portable subgraph isomorphism framework for GPUs, specifically designed for batch molecular matching. SIGMo takes advantage of the specific domain formulation to provide a more efficient filter-and-join strategy: the framework introduces a novel multi-level iterative filtering technique based on neighborhood signature encoding to efficiently prune candidates prior to a GPU-optimized join phase using a stack-based DFS traversal. The GPU implementation is written in SYCL, allowing portable execution on AMD, Intel, and NVIDIA GPUs. Our experimental evaluation on a large dataset from ZINC demonstrates up to 1470 × speedup over state-of-the-art subgraph isomorphism frameworks, and achieves a throughput of 7.7 billion matches per second on a cluster with 256 GPUs.

This study addresses the increasing threat to Psychological Well-Being (PWB) posed by Depression, Anxiety, and Stress conditions. Machine learning methods have shown promising results for several psychological conditions. However, the lack of transparency in existing models impedes practical application. The study aims to develop explainable machine learning models for depression, anxiety and stress prediction, focusing on features extracted from tasks involving handwriting and drawing. Two hundred patients completed the Depression, Anxiety, and Stress Scale (DASS-21) and performed seven tasks related to handwriting and drawing. Extracted features, encompassing pressure, stroke pattern, time, space, and pen inclination, were used to train the explainable-by-design Entropy-based Logic Explained Network (e-LEN) model, employing first-order logic rules for explanation. Performance comparison was performed with XGBoost, enhanced by the SHAP explanation method. The trained models achieved notable accuracy in predicting depression (0.749 ±0.089), anxiety (0.721 ±0.088), and stress (0.761 ±0.086) through 10-fold cross-validation (repeated 20 times). The e-LEN model’s logic rules facilitated clinical validation, uncovering correlations with existing clinical literature. While performance remained consistent for depression and anxiety on an independent test dataset, a slight degradation was observed for stress prediction in the test task.

The EMPATHIC project aimed to design an emotionally expressive virtual coach capable of engaging healthy seniors to improve well-being and promote independent aging. In particular, the system's human sensing capabilities allow for the perception of emotional states to provide a personalized experience. This paper outlines the development of the emotion expression recognition module of the virtual coach, encompassing data collection, annotation design, and a first methodological approach, all tailored to the project requirements. With the latter, we investigate the role of various modalities, individually and combined, for discrete emotion expression recognition in this context: speech from audio, and facial expressions, gaze, and head dynamics from video. The collected corpus includes users from Spain, France, and Norway, and was annotated separately for the audio and video channels with distinct emotional labels, allowing for a performance comparison across cultures and label types. Results confirm the informative power of the modalities studied for the emotional categories considered, with multimodal methods generally outperforming others (around 68% accuracy with audio labels and 72-74% with video labels). The findings are expected to contribute to the limited literature on emotion recognition applied to older adults in conversational human-machine interaction, and guide the development of future systems.

This research involved 88 young adults aged between 20 years and 35 years from two different countries, Spain and Italy. This work aims to explore preferences of the two groups toward synthetic voices, created for the experiment with variations in gender and quality for each language. The Spanish group was asked to evaluate the two high-quality voices of Elena and Pablo and the two low-quality voices of Maria and Juan while the Italian group was asked to assess the high-quality voices of Giulia and Antonio and the low-quality voices of Clara and Edoardo. The shortened and digitized version of the Virtual Agent Voice Acceptance Questionnaire (VAVAQ) was administered, respectively, in the Spanish or Italian version on the basis of the referring group to collect participants’ preferences. Due to the pandemic situation, participants were mainly contacted via email. Each participant was provided with a specific link. Outcomes revealed that Spanish and Italian young adults showed a greater appreciation toward the high-quality female voice compared to the other proposed voices. Regarding participants’ cross-cultural differences, Italian participants seem to judge the voices as more emotionally engaging than the Spanish participants whereas Spanish participants consider the audited voices as more natural and expressive than the Italian participants.

This study contributes knowledge on the detection of depression through handwriting/drawing features, to identify quantitative and noninvasive indicators of the disorder for implementing algorithms for its automatic detection. For this purpose, an original online approach was adopted to provide a dynamic evaluation of handwriting/drawing performance of healthy participants with no history of any psychiatric disorders ([Formula: see text]), and patients with a clinical diagnosis of depression ([Formula: see text]). Both groups were asked to complete seven tasks requiring either the writing or drawing on a paper while five handwriting/drawing features’ categories (i.e. pressure on the paper, time, ductus, space among characters, and pen inclination) were recorded by using a digitalized tablet. The collected records were statistically analyzed. Results showed that, except for pressure, all the considered features, successfully discriminate between depressed and nondepressed subjects. In addition, it was observed that depression affects different writing/drawing functionalities. These findings suggest the adoption of writing/drawing tasks in the clinical practice as tools to support the current depression detection methods. This would have important repercussions on reducing the diagnostic times and treatment formulation.

The growth of data-driven approaches typical of Machine Learning leads to an ever-increasing need for large quantities of labeled data. Unfortunately, these attributions are often made automatically and/or crudely, thus destroying the very concept of “ground truth” they are supposed to represent. To address this problem, we introduce HUM-CARD, a dataset of human trajectories in crowded contexts manually annotated by nine experts in engineering and psychology, totaling approximately 5000 hours. Our multidisciplinary labeling process has enabled the creation of a well-structured ontology, accounting for both individual and contextual factors influencing human movement dynamics in shared environments. Preliminary and descriptive analyzes are presented, highlighting the potential benefits of this dataset and its methodology in various research challenges.

Abstract Parameterized complexity, introduced to efficiently solve NP‐hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity () for several graph theoretic problems in : Maximum ‐Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular‐width () and consequently—as is a special case of —by . However, the proposed novel algorithms allow for improving the computational complexity from time —where and denote, respectively, the number of vertices and edges in the input graph—to time which is only additive in the size of the input. Then we consider some classical NP‐hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter.

Abstract We consider the problem of keeping under control the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node’s resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and $$\ell $$ ℓ , is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most $$\ell $$ ℓ nodes? We consider several parameters associated with the input, including the bounds k and $$\ell $$ ℓ , the maximum node degree $$\Delta $$ Δ , the number $$\zeta $$ ζ of initially contaminated nodes, the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.

The growing presence of robots in our daily life brings out the need to develop systems that are ever more user-friendly, considering users' needs and preferences. This is necessary in particular when robots are developed to be introduced into welfare settings. For this reason, a study is proposed with the aim to investigate differently aged (young, middle-aged, and seniors) potential users' assessment of male android robots as opposed to male virtual agents, in order to compare interactive systems characterized by different levels of embodiment. 180 participants joined the experiment, which consisted of watching video clips depicting android robots and virtual agents, and subsequently fulfilling the RAQ (Robot Acceptance Questionnaire) and the VAAQ (Virtual Agent Acceptance Questionnaire). Results highlighted substantial differences in robots and agents' assessment, differences which seem to be affected by participants' age, as well.

Considered the increasing use of assistive technologies in the shape of virtual agents, it is necessary to investigate those factors which characterize and affect the interaction between the user and the agent, among these emerges the way in which people interpret and decode synthetic emotions, i.e., emotional expressions conveyed by virtual agents. For these reasons, an article is proposed, which involved 278 participants split in differently aged groups (young, middle-aged, and elders). Within each age group, some participants were administered a “naturalistic decoding task,” a recognition task of human emotional faces, while others were administered a “synthetic decoding task” namely emotional expressions conveyed by virtual agents. Participants were required to label pictures of female and male humans or virtual agents of different ages (young, middle-aged, and old) displaying static expressions of disgust, anger, sadness, fear, happiness, surprise, and neutrality. Results showed that young participants showed better recognition performances (compared to older groups) of anger, sadness, and neutrality, while female participants showed better recognition performances (compared to males) of sadness, fear, and neutrality; sadness and fear were better recognized when conveyed by real human faces, while happiness, surprise, and neutrality were better recognized when represented by virtual agents. Young faces were better decoded when expressing anger and surprise, middle-aged faces were better decoded when expressing sadness, fear, and happiness, while old faces were better decoded in the case of disgust; on average, female faces where better decoded compared to male ones.

The main objective of the EMPATHIC project has been the design and development of a virtual coach to engage the healthy-senior user and to enhance well-being through awareness of personal status. The EMPATHIC approach addresses this objective through multimodal interactions supported by the GROW coaching model. The paper summarizes the main components of the EMPATHIC Virtual Coach (EMPATHIC-VC) and introduces a demonstration of the coaching sessions in selected scenarios.

The growing number of people suffering from depression makes it increasingly necessary to find new approaches able to support medical experts in its diagnosis. The early detection of depressive symptoms is crucial in limiting the co-occurrence of associated behavioural disorders such as psycho-motor retardation symptoms and social withdrawal. Therefore, automatic detection systems represent promising solutions not only for supporting the early diagnosis of the disease but also for monitoring patient’s health status, thus improving both the quality of the care process and life quality of patients. At the light of these considerations, this paper proposes an automatic system exploiting a machine learning algorithm, to distinguish among depressed and healthy subjects through the analysis of selected acoustic features extracted from spontaneous speech narratives produced by healthy and depressed subjects. The proposed system achieves a classification accuracy of about 85%, proving to be a promising solution for supporting the diagnosis of depression in real-time in a reliable, fast, inexpensive and non-intrusive ways.

Summary The cloud computing paradigm has emerged as the backbone of modern price‐aware scalable computing systems. Many cloud service models are competing to become the leading doorway to access the computational power of cloud providers. Recently, a novel service model, called function‐as‐a‐service (FaaS), has been proposed, which enables users to exploit the cloud computational scalability, left out the configuration and management of huge computing infrastructures. This article discloses Fly, a domain‐specific language, which aims at reconciling cloud and high‐performance computing paradigms adopting a multicloud strategy by providing a powerful, effective, and pricing‐efficient tool for developing scalable workflow‐based scientific applications by exploiting different and at the same time FaaS cloud providers as computational backends in a transparent fashion. We present several improvements of the Fly language, as well as a new enhanced version of a source‐to‐source compiler, which currently supports Symmetric Multiprocessing, Amazon AWS, and Microsoft Azure backends and translation of functions in Java, JavaScript, and Python programming languages. Furthermore, we discuss a performance evaluation of Fly on a popular benchmark for distributed computing frameworks, along with a collection of case studies with an analysis of their performance results and costs.

The present investigation aims at assessing elders' ability to decode facial emotional expressions conveyed by differently aged people in order to confirm (or disconfirm) the appropriateness of the “own age bias” theory, as well as investigate effects of different ages and different emotional categories. The study, involves 44 healthy elders (23 females), aged 65+ (mean age=75.09; SD=±7.9) which were requested to label 76 pictures depicting elders, middle-aged and young women and men displaying the six facial emotional expressions of disgust, anger, fear, sadness, happiness and neutrality. Results show a complex pattern of influences that calls for more deep investigations on the features to be accounted by providing socially and emotionally believable interfaces of effective and efficient algorithms to detect and decode their users' emotional facial expressions.

Abstract Assistive Ambient Living (AAL) in ageing refers to any device used to support ageing related psychological and physical changes aimed at improving seniors’ quality of life and reducing caregivers’ burdens. The diffusion of these devices opens the ethical issues related to their use in the human personal space. This is particularly relevant when AAL technologies are devoted to the ageing population that exhibits special bio-psycho-social aspects and needs. In spite of this, relatively little research has focused on ethical issues that emerge from AAL technologies. The present article addresses ethical issues emerging when AAL technologies are implemented for assisting the elderly population and is aimed at raising awareness of these aspects among healthcare providers. The overall conclusion encourages a person-oriented approach when designing healthcare facilities. This process must be fulfilled in compliance with the general principles of ethics and individual nature of the person devoted to. This perspective will develop new research paradigms, paving the way for fulfilling essential ethical principles in the development of future generations of personalized AAL devices to support ageing people living independently at their home.

The presented study investigated the preferences of seniors towards artificial avatars showing personality both from a pragmatic and a hedonic point of view. Also, preferences for technological devices were considered. The involved participants were 45 adults (20 female) aged 65+ years in good health. They were asked to watch video clips of 4 agents (two males and two females) showing different personality traits (i.e. angry, depressed, joyful, and practical), and subsequently had to complete a questionnaire. Subjects were not informed about an avatar’s personality and not openly interviewed regarding this subject. Rather, the administered questionnaire was devoted to test their perception of agents and whether such complies with the intended characteristics. Results show that subjects prefer female agents with a positive personality (joyful and practical) on both pragmatic and hedonic dimensions of the interactive system.

Humans are used to express their feelings of selfconfidence/ powerfulness or their distress/sadness through either expansive postures that occupy as much space as possible or closing postures occupying as less space as possible to avoid contact. This conduct suggests that feelings of selfconfidence/ powerfulness or distress/sadness change our body expressions/postures. It can be interesting to assess whether the reverse is also true, i.e. the way we arrange our body at a given moment would affect our feelings. The present research reports an investigation on such argument. To this aim, 50 subjects (25 females) aged between 23 and 31 years were requested to adopt either an expansive (high-powered) or contracted (low-powered) posture for as long as 3 minutes and then asked to bet money in a dice game. The results show that assuming high-power poses favors risk tolerant behaviors and rises feelings of powerfulness. This is not true in the case of low-power postures, which engender a sense of stress, sustained by a significant increase of skin conductance levels. Considerations are made on how to exploit these results for psychotherapy and rehabilitation purposes, as well as, for the implementation of artificial intelligent systems operating as tools for well-being and coaching.

We consider a population of interconnected individuals that, with respect to a piece of information, at each time instant can be subdivided into three (time‐dependent) categories: agnostics, influenced, and evangelists. A dynamical process of information diffusion evolves among the individuals of the population according to the following rules. Initially, all individuals are agnostic. Then, a set of people is chosen from the outside and convinced to start evangelizing, that is, to start spreading the information. When a number of evangelists, greater than a given threshold, communicate with a node v, the node v becomes influenced, whereas, as soon as the individual v is contacted by a sufficiently much larger number of evangelists, it is itself converted into an evangelist and consequently it starts spreading the information. The question is: How to choose a bounded cardinality initial set of evangelists so as to maximize the final number of influenced individuals? We prove that the problem is hard to solve, even in an approximate sense. On the positive side, we present exact polynomial time algorithms for trees and complete graphs. For general graphs, we derive exact parameterized algorithms. We also study the problem when the objective is to select a minimum number of evangelists capable of influencing the whole network. Our motivations to study these problems come from the areas of Viral Marketing and spread of influence in social networks. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 346–357 2018

This work reports on a series of experiments involving 960 participants (aged between 20-30 years and equally balanced by gender), asked to play the receiver role in a modified version of the Ultimatum Game, where together with information on the offer's fairness (e.g. 40 (fair) vs 10 (unfair) of 100 euros), a photo depicted the trader's appearance (trustworthy vs. untrustworthy) and a text provided his moral description (honest vs. dishonest). Receivers were asked to motivate their decision in connection with the appearance, moral judgment, and fairness of the offer, and report on how these variables affected their emotional feelings. Data analysis shows that, in all conditions containing a fair offer, the trader's appearance plays a significant role in the receivers' decisions in terms of acceptance rate. Moral descriptions play a significant role only in conditions containing an unfair offer. However, when asked to motivate their choices, subjects do not feel the interference of the social appearance, rather they provide more or less equal number of motivations with reference to the amount of offers and moral judgments. As for the emotions driving their decisions, non-converging feelings are observed both at intra and inter group level.

We consider the following multi-level opinion spreading model on networks. Initially, each node gets a weight, from the set {0,. . .,k – 1}, which measures the individual conviction of a new idea or product. Then, by proceeding in rounds, each node updates its weight according to those of its neighbours. We study k-dynamos that are initial assignments of weights leading each node to get the value k – 1 – e.g. unanimous maximum level of acceptance – within a given number of rounds; the goal is to minimize the sum of the initial weights of the nodes. We determine lower bounds on the sum of the initial weights under the irreversible simple majority rules, where a node increases its weight if and only if the majority of its neighbours have a weight that is higher than its own. We study the relations among 2-dynamos and k-dynamos, with and without a bound on the number of rounds needed to reach the desired all-(k – 1) configuration. Moreover, we provide constructive tight upper bounds for some classes of regular topologies: rings, tori and cliques.

The detection of negative emotions through daily activities such as writing and drawing is useful for promoting wellbeing. The spread of human-machine interfaces such as tablets makes the collection of handwriting and drawing samples easier. In this context, we present a first publicly available database which relates emotional states to handwriting and drawing, that we call EMOTHAW (EMOTion recognition from HAndWriting and draWing). This database includes samples of 129 participants whose emotional states, namely anxiety, depression, and stress, are assessed by the Depression-Anxiety-Stress Scales (DASS) questionnaire. Seven tasks are recorded through a digitizing tablet: pentagons and house drawing, words copied in handprint, circles and clock drawing, and one sentence copied in cursive writing. Records consist in pen positions, on-paper and in-air, time stamp, pressure, pen azimuth, and altitude. We report our analysis on this database. From collected data, we first compute measurements related to timing and ductus. We compute separate measurements according to the position of the writing device: on paper or in-air. We analyze and classify this set of measurements (referred to as features) using a random forest approach. This latter is a machine learning method, based on an ensemble of decision trees, which includes a feature ranking process. We use this ranking process to identify the features which best reveal a targeted emotional state. We then build random forest classifiers associated with each emotional state. We provide accuracy, sensitivity, and specificity evaluation measures obtained from cross-validation experiments. Our results show that anxiety and stress recognition perform better than depression recognition.

Simulation models are becoming an increasingly popular tool for the analysis and optimization of complex real systems in different fields. Finding an optimal system design requires performing a large parameter sweep. In this paper, we present the design of SOF (Simulation Optimization and exploration Framework on the cloud), a framework which exploits the computing power of a cloud computational environment in order to realize effective and efficient simulation optimization strategies. SOF offers several attractive features: SOF requires "zero configuration" as it does not require any additional software installed on the remote node, SOF is transparent to the user, since the user is totally unaware that system operates on a distributed environment, SOF is highly customizable and programmable, since it enables the running of different simulation optimization scenarios on different simulation toolkits. The tool has been fully developed and is available on a public repository under the Apache public licence.

Identifying the most influential spreaders is an important issue for the study of the dynamics of information diffusion in complex networks. In this paper we analyze the following spreading model. Initially, a few nodes know a piece of information and are active spreaders of it. At subsequent rounds, spreaders communicate the information to their neighbors. Upon receiving the information, a node becomes aware of it but does not necessarily become a spreader; it starts spreading only if it gets the information from a sufficiently large number of its neighbors. We study the problem of choosing a small set of initial spreaders so as to maximize the final number of nodes that become aware of the information.

We study the influence diffusion problem in online social networks. Formally, given a network represented by a directed graph G = (V,E), we consider a process of influence diffusion in G that proceeds as follows: Initially only the vertices of a given S ⊆ V are influenced; subsequently, at each round, the set of influenced vertices is augmented by all the vertices in the network that have a sufficiently large number of already influenced incoming neighbors. The question is to find a small subset of vertices that can influence the whole network (target set). This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known to be hard to approximate within a factor of 2log1--ϵn, for any ϵ > 0, and n = |V |.

Many modern computing platforms-notably clouds and desktop grids-exhibit dynamic heterogeneity: the availability and computing power of their constituent resources can change unexpectedly and dynamically, even in the midst of a computation. We introduce a new quality metric, AREA, for schedules that execute computations having interdependent constituent chores (jobs, tasks, etc.) on such platforms. AREA measures the average number of chores that a schedule renders eligible for execution at each step of a computation. Even though the definition of AREA does not mention any properties of host platforms (such as volatility), intuition suggests that rendering chores eligible at a faster rate will have a benign impact on the performance of volatile platforms. We report on simulation experiments that support this intuition. Earlier work has derived the basic properties of the AREA metric and has shown how to efficiently craft AREA-maximizing (A-M) schedules for several classes of significant computations. Even though A-M schedules always exist for every computation, it is not always known how to derive such schedules efficiently. In response, the current study develops an efficient algorithm that produces AREA-Oriented (A-O) schedules, which aim to efficiently approximate the AREAs of A-M schedules on arbitrary computations. The simulation experiments reported on here suggest that, in common with A-M schedules, A-O schedules complete computations on volatile heterogeneous platforms faster than a variety of heuristics that range from lightweight ones to computationally intensive ones-albeit not to the same degree as A-M schedules do. Our experiments suggest that schedules having larger AREAs have smaller completion times-but no proof of that yet exists.

Agent-Based Models (ABMs) are a class of models which, by simulating the behavior of multiple agents (i.e., ndependent actions, interactions and adaptation), aim to emulate and/or predict complex phenomena. One of the general features of ABM simulations is their experimental capacity, that requires a viable and reliable infrastructure to interact with a running simulation, monitoring its behaviour, as it proceeds, and applying changes to the configurations at run time, (the computational steering) in order to study "what if" scenarios.

We focus on agent-based simulations where a large number of agents move in the space, obeying to some simple rules. Since such kind of simulations are computational intensive, it is challenging, for such a contest, to let the number of agents to grow and to increase the quality of the simulation. A fascinating way to answer to this need is by exploiting parallel architectures. In this paper, we present a novel distributed load balancing schema for a parallel implementation of such simulations. The purpose of such schema is to achieve an high scalability. Our approach to load balancing is designed to be lightweight and totally distributed: the calculations for the balancing take place at each computational step, and influences the successive step. To the best of our knowledge, our approach is the first distributed load balancing schema in this context. We present both the design and the implementation that allowed us to perform a number of experiments, with up-to 1,000,000 agents. Tests show that, in spite of the fact that the load balancing algorithm is local, the workload distribution is balanced while the communication overhead is negligible.

Several proposals have been presented to supplement the traditional measure of routing efficiency in P2P networks, i.e. the (average) number of hops for lookup operations, with measures of the latency incurred in the underlying network. So far, no solution has been presented to this “latency” problem without incurring in extra and heavy management costs. We propose Relaxed-2-Chord, a new design of the traditional Chord protocol, that is able to fit the routing tables with low latency nodes, doing a parasitic measurement of nodes' latency without adding any overhead. The solution that we present is a Distributed Hash Table system whose aim is to combine the routing efficiency and flexibility of the Chord protocol - i.e. a good degree/diameter tradeoff - and a provable optimal hop by hop latency. Our work is inspired by the recent Lookup-parasitic random sampling (LPRS) strategies which allow to improve the network stretch, that is, the ratio between the latency of two nodes on the overlay network and the unicast latency between those nodes. Relaxed-2-Chord reaches the same results as LPRS without introducing any overhead

A new quality metric, called area, is introduced for schedules that execute dags, i.e., computations having intertask dependencies. Motivated by the temporal unpredictability encountered when computing over the Internet, the goal under the new metric is to maximize the average number of tasks that are eligible for execution at each step of a computation. Area-maximization is a weakening of IC-optimality, which strives to maximize the number of eligible tasks at every step of the computation. In contrast to IC-optimal schedules, area-maximizing schedules exist for every dag. For dags that admit IC-optimal schedules, all area-maximizing schedules are IC-optimal, and vice versa. The basic properties of this metric are derived in this paper, and tools for efficiently crafting area-maximizing schedules for large classes of computationally significant dags are developed. Several of these results emerge from a close connection between area-maximizing scheduling and the MAX Linear-Arrangement Problem for Dags.

We present the theoretical foundation, the design and the implementation of a library, called EulerVC to interactively handle Euler diagrams for the purposes of resource management. Fast on-line algorithms to interpret wellformed diagrams have been developed utilising a new notion of marked points to keep track of the zone sets. The interface allows the construction of overlapping ellipses to represent categories together with the drag and drop of resources in order to categories them. A visual indicator can be used to show if the diagram under construction is not wellformed to assist in reducing user mistakes, and sets of tags can be assigned to resources upon export. The generic approach is demonstrated via an integration with the bookmarking site delicious.

Strategies are developed for "fattening" the tasks ofcomputation-dags so as to accommodate the heterogeneity of remote clients in Internet-based computing (IC). Earlier work has developed the underpinnings of IC-Scheduling theory, an algorithmic framework for scheduling computations having intertask dependencies for IC. The theory's schedules strive to render tasks eligible for execution at the maximum possible rate, so as to: (a) utilize remoteclients' computational resources well, by enhancing the likelihood of having work to allocate to an available client; (b) lessen the likelihood of a computation's stalling for lack of tasks that are eligible for allocation. The current study begins to enhance IC-Scheduling theory so that it can accommodate the varying computational resources of remote clients. The techniques developed here render a dag multi-granular by clustering its tasks. Several clustering strategies are developed: one works for any dag but produces only a limited variety of "fattened" tasks; others exploit the detailed structure of the dag being scheduled but allow a broad range of "fattened" tasks.

We present a load-balancing technique that exploits the temporal coherence, among successive computation phases, in mesh-like computations to be mapped on a cluster of processors. Our method partitions the computation in balanced tasks and distributes them to independent processors through the prediction binary tree (PBT). At each new phase, current PBT is updated by using previous phase computing time (for each task) as (next phase) cost estimate. The PBT is designed so that it balances the load across the tasks as well as reduce {\em dependency} among processors for higher performances. Reducing dependency is obtained by using rectangular tiles of the mesh, of almost-square shape (i.e. one dimension is at most twice the other). By reducing dependency, one can reduce inter-processors communication or exploit local dependencies among tasks (such as data locality).Our strategy has been assessed on a significant problem, parallel ray tracing. Our implementation shows a good scalability, and improves over coherence-oblivious implementations. We report different measurements showing that granularity of tasks is a key point for the performances of our decomposition/mapping strategy.

Earlier work has developed the rudiments of a scheduling theory for computations having intertask dependencies - modeled via dags - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution as fast as possible, with the aim of: (a) utilizing clients' computational resources well, by always having work to allocate to an available client; (b) lessening the likelihood of a computation's stalling for lack of eligible tasks. Simulation studies suggest that this goal does accelerate computation over the Internet. The theory crafts a schedule for a dag Q by "parsing" Q (if possible) into connected building-block dags that one can "compose " to form Q and then analyzing the scheduling dependencies among these building blocks. The current paper extends the theory by developing the Sweep Algorithm, a tool that allows one to: (1) schedule using building blocks that are not necessarily connected, and (2) craft schedules that interleave the execution of subdags that have no interdependencies. The augmented scheduling algorithms allow one to craft optimal schedules for previously unschedulable dags. Examples presented include artificial dags that are "close" to ones arising in real computations, as well as a component of a dag that arises in a functional MRI application.

Abstract The Chord protocol is the best known example of implementation of logarithmic complexity routing for structured peer‐to‐peer networks. Its routing algorithm, however, does not provide an optimal trade‐off between resources exploited (the size of the ‘finger table’) and performance (the average or worst‐case number of hops to reach destination). Cordasco et al. showed that a finger table based on Fibonacci distances provides lower number of hops with fewer table entries. In this paper we generalize this result, showing how to construct an improved finger table when the objective is to reduce the number of hops, possibly at the expense of an increased size of the finger table. Our results can also be exploited to guarantee low routing time in case a fraction of nodes fails. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract We propose a family of novel Chord‐based P2P schemes retaining all positive aspects that made Chord a popular topology for routing in P2P networks. The schemes, based on the Fibonacci number system, allow to simultaneously improve on the maximum/average number of hops for lookups and the routing table size per node. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Earlier work has developed the underpinnings of IC-scheduling theory, an algorithmic framework for scheduling computations having intertask dependencies for Internet-based computing (IC). The theory aims to produce schedules that render tasks eligible for execution at the maximum possible rate, so as to: (a) utilize remote clients' computational resources well, by always having work available for allocation; (b) lessen the likelihood that a computation can stall for lack of tasks that are eligible for execution. The current paper reconnects the theory, which models computations abstractly, with a variety of significant real computations and computational paradigms, by illustrating how to schedule these computations optimally.

We define a proximity overlay network (PON) which allow to realize DHT systems whose aim is to combine routing efficiency - i.e. an optimal degree/diameter tradeoff - and proximity awareness. The proposed systems is parameterized with a positive integer s which measures the amount of flexibility offered by the network. Varying the value of s the system goes from a quite rigid network (s=2) which offer an optimal degree/diameter tradeoff. Increasing s to relatively low values allows to increase the flexibility of the network and consequently improves the stretch, that is, the ratio between the latency of two nodes on the overlay network and the unicast latency between those nodes. We are able to reconcile the conflict between the load balancing and proximity relationship by proving the efficiency of the main performance metrics. In particular we analytically prove that our system can result in lookup latencies proportional to the maximum latency of the underlying physical network, provided that the physical network has a power law latency expansion.

Earlier work has developed the underpinnings of the IC-scheduling theory, a framework for scheduling computations having intertask dependencies - modeled via directed acyclic graphs (DAGs) - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate, with the dual aim of 1) utilizing remote clients' computational resources well by always having work to allocate to an available client and 2) lessening the likelihood of a computation's stalling for lack of eligible tasks. The DAGs handled by the theory thus far are those that can be decomposed into a given collection of bipartite building block DAGs via the operation of DAG decomposition. A basic tool in constructing schedules is a relation >, which allows one to "prioritize" the scheduling of a complex DAG's building blocks. The current paper extends the IC-scheduling theory in two ways: by expanding significantly the repertoire of DAGs that the theory can schedule optimally and by allowing one sometimes to shortcut the algorithmic process required to find optimal schedules. The expanded repertoire now allows the theory to schedule optimally, among other DAGs, a large range of DAGs that are either "expansive", in the sense that they grow outward from their sources, or "reductive", in the sense that they grow inward toward their sinks. The algorithmic shortcuts allow one to "read off" an optimal schedule for a DAG from a given optimal schedule for the DAG's dual, which is obtained by reversing all arcs (thereby exchanging the roles of sources and sinks).

Techniques are developed for mapping structured data to an ensemble of parallel memory modules in a way that limits the number of conflicts, i.e., simultaneous accesses by distinct processors to the same memory module. The techniques determine, for any given conflict tolerance c, the smallest ensemble that allows one to store any n-node data structure "of type X" in such a way that no more than c nodes of a structure are stored on the same module. This goal is achieved by determining the smallest c-perfect universal graphs for data structures "of type X." Such a graph is the smallest graph that contains a homomorphic image of each n-node structure "of type X" with each node of the image holding < c nodes of the structure. In the current paper, "type X" refers to rooted binary trees and three array-like structures: chaotic arrays, ragged arrays, and rectangular arrays. For each of these families of data structures, the number of memory modules needed to achieve conflict tolerance c is determined to within constant factors.

Earlier work has developed the underpinnings of a theory of scheduling computations having intertask dependencies - modeled via dags - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate. This goal aims: (a) to utilize remote clients’ computational resources well, by always having work to allocate to an available client; (b) to lessen the likelihood of the "gridlock" that ensues when a computation stalls for lack of eligible tasks. The dags handled by the theory thus far are those that can be constructed from a given collection of bipartite building-block dags via the operation of dagcomposition. The current paper extends the range of applicability of the theory by significantly expanding the repertoire of building-block dags that the scheduling algorithms can handle. Thereby, the theory can now schedule large classes of "expansive" and "reductive" dags optimally.

The chord protocol is the best known example of implementation of logarithmic complexity routing for structured peer-to-peer networks. Its routing algorithm, however, does not provide an optimal trade-off between resources exploited (the size of the "finger table") and performance (the average or worst-case number of hops to reach destination). Cordasco et al. showed that a finger table based on Fibonacci distances provides lower number of hops with fewer table entries. In this paper, we generalize this result, showing how to construct an improved finger table when the objective is to reduce the number of hops, possibly at the expense of an increased size of the finger table. Our results can also be exploited to guarantee low routing time in case a fraction of nodes is assumed to fail.

We propose routing schemes that optimize the average number of hops for lookup requests in peer-to-peer (P2P) systems without adding any overhead to the system. Our work is inspired by the recently introduced variation of greedy routing, called neighbor-of-neighbor (NoN), which allows to get optimal average path length with respect to the degree. Our proposal has the advantage of first "limiting" and then "eliminating" the use of randomization. As a consequence, the NoN technique can be implemented with our schemes without adding any overhead. Analyzed networks include several popular topologies: chord, hypercube based networks, symphony, skip-graphs. Theoretical results and extensive simulations show that the proposed simplifications (while maintaining the original node degree) do not increase the average path length of the networks, which is often improved in practice. The improvement is obtained with no harm to the operational efficiency (e.g. stability, ease of programming, scalability, fault-tolerance) of the considered systems.

Greedy routing has been used in most of the proposed P2P networks because of several reasons. One of the main advantages is that greedy routing is very simple to implement and has some “implicit” fault-tolerance capabilities. It was however noticed that greedy routing usually produces paths of length larger than what would be required in a network of the given node degree. As an example some popular topologies like Chord have degree O(log n) and the greedy routing produces an average path length O(log n) whereas the lower bound is Ω(log n/log log n). The use of randomization allowed to show networks with optimal average path length. Recently a novel approach for routing in DHTs which improves on greedy routing has been proposed [4]. This approach, called NoN (Neighbors–of–Neighbors), substantially consists in making the greedy choice by looking not only at the neighbors of a node but at all the nodes at distance at most 2 from the node itself. The NoN approach together with the use of randomization in establishing the neighbors of the nodes which are present in the network, can optimally reduce the latency in several well known topologies. Hence the use of randomization, inspired by the Small-world idea introduced by Kleinberg [2], together with the NoN routing allows to maintain, to some extent, the advantages of greedy routing while optimizing the latency. Our goal is to retain the improvements given by the NoN routing over randomized networks, while eliminating the drawback in system overhead implied by this technique. In fact, randomization and NoN routing require the transmission to a node of its neighbors’s neighbors. While the authors in [4] argue that this can be done without extra cost by using keep-alive TCP messages, we eliminate the extracommunication at all and, similarly, eliminate the need of storing in each node its neighbors’s neighbors. To this aim we need to eliminate the random factor in establishing each neighbor of a node. In fact, determinism allows each node to calculate locally the neighbors of its neighbors. ∗ Work partially supported by EU RTN project ARACNE and by Italian FIRB WEBMINDS project