Compiler optimizations may lead to loss of debug information, hampering developer productivity and techniques that rely on binary-to-source mappings, such as sampling-based feedback-directed optimization. While recent endeavors exposed debug information correctness and completeness bugs in compiler transformations, understanding where a complex optimizing pipeline "loses" debug information is an understudied problem.In this paper, we first rectify accuracy issues in methods for measuring the availability of debug information, and show that the synthetic programs evaluated so far lead to metric values that differ from those we observe for real-world programs. Building on this, we present DebugTuner, a framework for systematically analyzing the impact of individual compiler optimization passes on debug information, and assemble a test suite of programs for collecting more realistic metrics. Using DebugTuner and the test suite, we identify transformations in gcc and clang that cause more debug information loss, and construct modified optimization levels that improve debuggability while retaining competitive performance. We obtain levels that outperform gcc’s Og for both debuggability and performance, and make recommendations for constructing an Og level for clang. Finally, we present a case study on AutoFDO where, by disabling selected passes in the profiling stage, the final optimized binary is more performant due to the improved quality of the binary-to-source mapping.

Automated fuzz testing is now standard practice, yet key blind spots persist. Coverage-guided fuzzers typically rely on edge coverage as a lightweight proxy for program behavior. However, this metric captures path variations only weakly: it cannot differentiate executions that follow distinct control-flow paths but traverse the same edges—causing many path-dependent bugs to go undetected. Path awareness would offer a richer coverage view but has been considered too costly for fuzzing.We introduce a lightweight method for tracking intra-procedural execution paths, enabling efficient path-aware feedback. This enhances the fuzzer’s ability to detect subtle bugs, even in well-tested software. To counter the resulting seed explosion, we evaluate two strategies—culling and opportunistic path-aware fuzzing—that balance precision and throughput. Our findings show that path-aware fuzzing, when properly guided, uncovers more bugs and reveals untapped potential in fuzzing research.

Process injection is a core technique for malware authors to evade detection and enhance stealth. Despite its widespread use and importance in malware analysis, process injection remains underexplored in academic research, with prior work often limited to specific techniques or lacking a systematic approach. This paper proposes a principled analysis methodology centered on fundamental operational steps inherent to all known process injection variants. By looking for the co-occurrence of a minimal set of said steps and correlating them via memory address identity, our approach overcomes the accuracy and overhead limitations of prior studies, enables reliable detection and fine-grained analysis of process injection attacks with tenable run-time costs. We provide fresh insights into how threat actors leverage this technique by analyzing malware spotted in the wild from 2017 to 2023. An analysis of 56,340 representative samples from 2,667 malware families estimates process injection as a dominant evasion strategy, and suggests that threat actors continuously adapt their choices and implementation variants in response to evolving defense mechanisms and community knowledge. Comparative experiments then show that our method outperforms dedicated solutions and mainstream sandboxes in identifying injection activity. To foster future research, we share with the community the implementation, dataset, and experimental logs from this study.

Ensuring the security and confidentiality of cloud computing workloads is essential. To this end, major cloud providers offer computing instances based on trusted execution environments (TEEs) to support confidential computing in virtual machines. TEEs are hardware-based shielded environments building on technologies available today, such as Intel TDX or AMD SEV-SNP or that will soon be, as with ARM CCA.To lower the barriers to experimenting with these technologies for researchers and practitioners, we developed ConfBench, a tool for easy evaluation of confidential virtual machines. ConfBench supports both cloud-native workloads (Function-as-a-Service) and classic applications. ConfBench facilitates the management of the full lifecycle of such workloads, from their deployment to the gathering of performance metrics, taking into account the specifics of TEE-enabled confidential virtual machines. We use ConfBench to collect execution overhead measurements for different VM-enabled TEEs (Intel TDX and AMD SEV-SNP) through extensive experiments. We also showcase how ConfBench’s architecture allows for validating also simulation-based TEEs, reporting preliminary results with ARM CCA. We highlight the intrinsic overheads of such confidential VMs by conducting stress tests against machine learning inference tasks, DBMS and native-OS operations benchmarking, as well as by evaluating the costs of attestation operations required in the context of confidential computing. The results indicate generally tenable overheads with modern TEEs, with exceptions mainly from I/O-intensive tasks, especially with TDX. ConfBench’s multi-language support for FaaS workloads also lets us gain insights into differences stemming from varying complexities behind language runtimes. We release ConfBench to the research community and provide instructions to reproduce our experiments.

Among the behaviors and tactics that malware can exhibit, environment-sensitive logic likely poses the longest-standing challenge to the analysis capabilities of automatic systems such as sandboxes. Current analysis approaches either fall short in anticipating adversarial tactics by design, or incur prohibitive costs and other roadblocks when reasoning on real-world code. As a result, manual analysis remains the primary way to identify behaviors that show only when a machine meets specific expectations of the sample.To address these issues, we present the first practical, sound, and effective solution for multi-path exploration of environment-sensitive malware. We argue how the popular coverage-guided fuzzing paradigm from software testing can effectively achieve this task, provided we can devise original design solutions (such as coverage feedback and environment mutations) tailored to the unique characteristics of malware to enable this application. Our approach not only can disarm many evasions without requiring expert knowledge, but also unveil additional activities that would not show in a baseline run due to environmental conditions unrelated to evasion.We build a manually annotated dataset of environment-sensitive malware and use it to estimate the analysis capabilities of the approach. Our Pfuzzer implementation reveals activity that the best competitor misses for 36.09% of the samples: such activity either follows evasions that deceive existing systems or comes from behaviors that show only in other "right" environments. Pfuzzer also unveils dormant evasive tactics for 70.64% of the samples that one may wrongly deem as non-evasive after a baseline run.

Binary function similarity, which often relies on learning-based algorithms to identify what functions in a pool are most similar to a given query function, is a sought-after topic in different communities, including machine learning, software engineering, and security. Its importance stems from the impact it has in facilitating several crucial tasks, from reverse engineering and malware analysis to automated vulnerability detection. Whereas recent work cast light around performance on this long-studied problem, the research landscape remains largely lackluster in understanding the resiliency of the state-of-the-art machine learning models against adversarial attacks. As security requires to reason about adversaries, in this work we assess the robustness of such models through a simple yet effective black-box greedy attack, which modifies the topology and the content of the control flow of the attacked functions. We demonstrate that this attack is successful in compromising all the models, achieving average attack success rates of 57.06% and 95.81% depending on the problem settings (targeted and untargeted attacks). Our findings are insightful: top performance on clean data does not necessarily relate to top robustness properties, which explicitly highlights performance-robustness trade-offs one should consider when deploying such models, calling for further research.

A recent trend in binary code analysis promotes the use of neural solutions based on instruction embedding models. An instruction embedding model is a neural network that transforms assembly instructions into embedding vectors. If the embedding network is able to processes sequences of assembly instructions transforming them into a sequence of embedding vectors, then the network effectively represents anassembly code model. In this paper we present BinBert, a novel assembly code model. BinBert is built on a transformer pre-trained on a huge dataset of both assembly instruction sequences and symbolic execution information. BinBert can be applied to assembly instructions sequences and it isfine-tunable, i.e. it can be re-trained as part of a neural architecture on task-specific data. Through fine-tuning, BinBert learns how to apply the general knowledge acquired with pre-training to the specific task. We evaluated BinBert on a multi-task benchmark that we specifically designed to test the understanding of assembly code. The benchmark is composed of several tasks, some taken from the literature, and a few novel tasks that we designed, with a mix of intrinsic and downstream tasks. Our results show that BinBert outperforms state-of-the-art models for binary instruction embedding, raising the bar for binary code understanding.

The availability of debug information for optimized executables can largely ease crucial tasks such as crash analysis. Source-level debuggers use this information to display program state in terms of source code, allowing users to reason on it even when optimizations alter program structure extensively. A few recent endeavors have proposed effective methodologies for identifying incorrect instances of debug information, which can mislead users by presenting them with an inconsistent program state.

The growing adoption of IT solutions in the healthcare sector is accompanied by a steady increase in cybersecurity incidents. In response to this phenomenon regulations, standards, and best practices have been introduced to address cybersecurity and data protection issues in this sector. However, applying this large corpus of documents poses several operational hurdles, while operators continue to lag behind the growing number of cyber attacks. This paper contributes a Systematization of Knowledge (SoK) of the main cybersecurity documents relevant to the healthcare sector. We collected and analyzed 49 relevant documents and used the NIST Cybersecurity Framework as a taxonomical instrument to categorize key information extracted through a three-step analysis. We provide and quantify seven findings emerging from this analysis and propose a way to exploit the extracted measures to support cybersecurity assessments.

Artificial diversification of a software program can be a versatile tool in a wide range of software engineering and security scenarios. For example, randomizing implementation aspects can increase the costs for attackers as it prevents them from benefiting of precise knowledge of their target. A promising angle for diversification can be having two runs of a program on the same input yield inherently diverse instruction traces. Inspired by on-stack replacement designs for managed runtimes, in this paper we study how to transform a C program to realize continuous transfers of control and program state among function variants as they run. We discuss the technical challenges toward such goal and propose effective compiler techniques for it that enable the re-use of existing techniques for static diversification with no modifications. We implement our approach in LLVM and evaluate it on both synthetic and real-world subjects.

The binary similarity problem consists in determining if two functions are similar considering only their compiled form. Advanced techniques for binary similarity recently gained momentum as they can be applied in several fields, such as copyright disputes, malware analysis, vulnerability detection, etc. In this article we describe SAFE, a novel architecture for function representation based on a self-attentive neural network. SAFE works directly on disassembled binary functions, does not require manual feature extraction, is computationally more efficient than existing solutions, and is more general as it works on stripped binaries and on multiple architectures. Results from our experimental evaluation show how SAFE provides a performance improvement with respect to previous solutions. Furthermore, we show how SAFE can be used in widely different use cases, thus providing a general solution for several application scenarios.

Despite the advancements in software testing, bugs still plague deployed software and result in crashes in production. When debugging issues —sometimes caused by “heisenbugs”— there is the need to interpret core dumps and reproduce the issue offline on the same binary deployed. This requires the entire toolchain (compiler, linker, debugger) to correctly generate and use debug information. Little attention has been devoted to checking that such information is correctly preserved by modern toolchains’ optimization stages. This is particularly important as managing debug information in optimized production binaries is non-trivial, often leading to toolchain bugs that may hinder post-deployment debugging efforts.

In the era of microarchitectural side channels, vendors scramble to deploy mitigations for transient execution attacks, but leave traditional side-channel attacks against sensitive software (e.g., crypto programs) to be fixed by developers by means of constant-time programming (i.e., absence of secret-dependent code/data patterns). Unfortunately, writing constant-time code by hand is hard, as evidenced by the many flaws discovered in production side channel-resistant code. Prior efforts to automatically transform programs into constant-time equivalents offer limited security or compatibility guarantees, hindering their applicability to real-world software.

Modern stream processing engines (SPEs) process large volumes of events propagated at high velocity through multiple queries. To improve performance, existing SPEs generally aim to minimize query output latency by minimizing, in turn, the propagation delay of events in query pipelines. However, for queries containing commonly used blocking operators such as windows, this scheduling approach can be inefficient. Watermarks are events popularly utilized by SPEs to correctly process window operators. Watermarks are injected into the stream to signify that no events preceding their timestamp should be further expected. Through the design and development of Klink, we leverage these watermarks to robustly infer stream progress based on window deadlines and network delay, and to schedule query pipeline execution that reflects stream progress. Klink aims to unblock window operators and to rapidly propagate events to output operators while performing judicious memory management. We integrate Klink into the popular open source SPE Apache Flink and demonstrate that Klink delivers significant performance gains over existing scheduling policies on benchmark workloads for both scale-up and scale-out deployments.

In the Lattice Agreement (LA) problem, originally proposed by Attiya et al. [1], a set of processes has to decide on a chain of a lattice. More precisely, each correct process proposes an element e of a certain join-semi lattice L and it has to decide on a value that contains e. Moreover, any pair pi, pjof correct processes has to decide two values deciand decjthat are comparable (e.g., deci≤ decjor decji). In this paper we present new contributions for the synchronous case. We investigate the problem in the usual message passing model for a system of n processes with distinct unique IDs. We first prove that, when only authenticated channels are available, the problem cannot be solved if f = n/3 or more processes are Byzantine. We then propose a novel algorithm that works in a synchronous system model with signatures (i.e., the authenticated message model), tolerates up to f byzantine failures (where f <; n/3) and that terminates in O(log f) rounds. We discuss how to remove authenticated messages at the price of algorithm resiliency (f <; n/4). Finally, we present a transformer that converts any synchronous LA algorithm to an algorithm for synchronous Generalised Lattice Agreement.

The paper investigates the Lattice Agreement (LA) problem in asynchronous systems. In LA each process proposes an element e from a predetermined lattice, and has to decide on an element e' of the lattice such that e ≤ e'. Moreover, decisions of different processes have to be comparable (no two processes can decide two elements e' and e such that (e ≤ e') ∧ (e' ≤ e)).It has been shown that Generalized LA (i.e., a version of LA proposing and deciding on sequences of values) can be used to build a Replicated State Machine (RSM) with commutative update operations. The key advantage of LA and Generalized LA is that they can be solved in asynchronous systems prone to crash-failures (which is not the case with standard Consensus).In this paper we assume Byzantine failures. We propose the Wait Till Safe (WTS) algorithm for LA, and we show that its resilience to f ≤ (n - 1)/3 Byzantine processes is optimal. We then generalize WTS obtaining a Generalized LA algorithm, namely GWTS. We use GWTS to build a RSM with commutative updates. Our RSM works in asynchronous systems and tolerates f ≤ (n - 1)/3 malicious entities. All our algorithms use the minimal assumption of authenticated channels. When the more powerful public signatures are available, we discuss how to improve the message complexity of our results (from quadratic to linear, when f = O(1)). To the best of our knowledge this is the first paper proposing a solution for Byzantine LA that works on any possible lattice, and it is the first work proposing a Byzantine tolerant RSM built on it.

Distributed stream processing frameworks are designed to perform continuous computation on possibly unbounded data streams whose rates can change over time. Devising solutions to make such systems elastically scale is a fundamental goal to achieve desired performance and cut costs caused by resource over-provisioning. These systems can be scaled along two dimensions: the operator parallelism and the number of resources. In this paper, we show how these two dimensions, as two symbiotic entities, are independent but must mutually interact for the global benefit of the system. On the basis of this observation, we propose a fine-grained model for estimating the resource utilization of a stream processing application that enables the independent scaling of operators and resources. A simple, yet effective, combined management of the two dimensions allows us to propose ELYSIUM, a novel elastic scaling approach that provides efficient resource utilization. We implemented the proposed approach within Apache Storm and tested it by running two real-world applications with different input load curves. The outcomes backup our claims showing that the proposed symbiotic management outperforms elastic scaling strategies where operators and resources are jointly scaled.

Balanced graph partitioning is a fundamental problem that is receiving growing attention with the emergence of distributed graph-computing (DGC) frameworks. In these frameworks, the partitioning strategy plays an important role since it drives the communication cost and the workload balance among computing nodes, thereby affecting system performance. However, existing solutions only partially exploit a key characteristic of natural graphs commonly found in the real-world: their highly skewed power-law degree distributions. In this paper, we propose High-Degree (are) Replicated First (HDRF), a novel streaming vertex-cut graph partitioning algorithm that effectively exploits skewed degree distributions by explicitly taking into account vertex degree in the placement decision. We analytically and experimentally evaluate HDRF on both synthetic and real-world graphs and show that it outperforms all existing algorithms in partitioning quality.

Many organizations today still manage mid or large in-house data centers that require very expensive maintenance efforts, including fault detection. Common monitoring frameworks used to quickly detect faults are complex to deploy/maintain, expensive, and intrusive as they require the installation of probes on monitored hw/sw to collect raw data. Such intrusiveness can be problematic as it imposes installation/management overhead and may interfere with security/privacy policies. In this paper we introduce NIRVANA, a novel monitoring system for fault detection that works at rack-level and is (i) non-intrusive, i.e., it does not require the installation of software probes on the hosts to be monitored and (ii) black-box, i.e., agnostic with respect to monitored applications. At the core of our solution lies the observation that aggregated features that can be monitored at rack-level in a non-intrusive and black-box way, show predictable behaviors while the system works in both fault-free and faulty states, it is therefore possible to detect and identify faults by monitoring and analyzing any perturbations to these behaviors. An extensive experimental evaluation shows that non-intrusiveness does not significantly hamper the fault detection capabilities of the monitoring system, thus validating our approach.

A distributed event notification service (ENS) is at the core of modern messaging infrastructures providing applications with scalable and robust publish/subscribe communication primitives. Such ENSs can route events toward subscribers using multiple paths with different lengths and latencies. As a consequence, subscribers can receive events out of order. In this paper, we propose a novel solution for ordered notifications on top of an existing distributed topic-based ENS. Our solutions guarantees that each pair of events published in the system will be notified in the same order to all their target subscribers independently from the topics they are published in. It endows a distributed timestamping mechanism based on a multistage sequencer that produces timestamps whose size is dynamically adjusted to accommodate changing subscriptions in the system. An extensive experimental evaluation based on a prototype implementation shows that the timestamping mechanism is able to scale from several points of view (i.e., number of publisher and subscribers, event rate). Furthermore, it shows how the deployment flexibility of our solution makes it perform better in terms of timestamp size and timestamp generation latency when the system load exhibits geographic topic popularity, that is, matching subscriptions and publications are geographically clustered. This makes our solution particularly well suited to be deployed in geo-distributed infrastructures.

Matrix completion latent factors models are known to be an effective method to build recommender systems. Currently, stochastic gradient descent (SGD) is considered one of the best latent factor-based algorithm for matrix completion. In this paper we discuss GASGD, a distributed asynchronous variant of SGD for large-scale matrix completion, that (i) leverages data partitioning schemes based on graph partitioning techniques, (ii) exploits specific characteristics of the input data and (iii) introduces an explicit parameter to tune synchronization frequency among the computing nodes. We empirically show how, thanks to these features, GASGD achieves a fast convergence rate incurring in smaller communication cost with respect to current asynchronous distributed SGD implementations.

Energy management, and in particular its efficient optimization, is one of the hot trends in the current days, both at the enterprise level (optimization of whole corporate/government buildings) and single-citizens' homes. Energy efficiency is generally function of out-door techniques -- renewable energy, smart energy production and distribution, etc. -- and in-door techniques; in particular, very few energy managers -- each of us can be an energy manager of his own home - can state "who, when and why is consuming", conversely this knowledge is fundamental in order to diminish wasting of energy. Recent studies show that the energy wasted in the overall consumption is about the 30% of the total amount; examples of potential energy wasting are printers and PCs on during the night, status LED of different devices (TV, set-top-box, etc.) and/or lights, lights during normal day-light time, etc.

A distributed event notification service (ENS) is a middleware architecture commonly used to provide applications with scalable and robust publish/subscribe communication primitives. A distributed ENS can route events toward subscribers using multiple paths with different lengths and latencies, as a consequence, subscribers can receive events out of order. In this paper, we propose a novel solution for out-of-order notification detection on top of an existing topic based ENS. Our solution guarantees that events published on different topics will be either delivered in the same order to all the subscribers of those topics or tagged as out-of-order. The proposed algorithm is completely distributed and is able to scale with the system size while imposing a reasonable cost in terms of notification latency. Our solution improves the current state of the art solutions by dynamically handling subscriptions/unsubscriptions and by automatically adapting with respect to topic popularity changes.

Let consider a set of anonymous moving objects to be tracked in a binary sensor network. This article studies the problem of associating deterministically a track revealed by the sensor network with the trajectory of an unique anonymous object, namely the multiple object tracking and identification (MOTI) problem. In our model, the network is represented by a sparse connected graph where each vertex represents a binary sensor and there is an edge between two sensors if an object can pass from one sensed region to another one without activating any other sensor. The difficulty of MOTI lies in the fact that the trajectories of two or more objects can be so close that the corresponding tracks on the sensor network can no longer be distinguished (track merging), thus confusing the deterministic association between an object trajectory and a track. The article presents several results. We first show that MOTI cannot be solved on a general graph of ideal binary sensors even by an omniscient external observer if all the objects can freely move on the graph. Then we describe restrictions that can be imposed a priori either on the graph, on the object movements, or on both, to make the MOTI problem always solvable. In the absence of an omniscient observer, we show how our results can lead to the definition of distributed algorithms that are able to detect when the system is in a state where MOTI becomes unsolvable.

Telco providers are in the phase of migrating their services from PSTN to so called Next Generation Networks (NGNs) based on standard IP connectivity. This switch is expected to produce a cost degression of 50% for CAPEX, while OPEX remains fairly stable due to network management and energy costs. At the same time we are expecting a big increase of the load of a telco provider at the core level due to the istantiation of new telco services (VoIP, video conferencing etc) and to the support of third parties services (such as support to smartphone applications, etc.). The goal of this work is to show how management and energy costs can be effectively reduced by leveraging autonomic approaches to move some NGN services toward the telco network edge while still providing QoS levels comparable with those provided by a traditional fully-managed infrastructure.

Providing independent uniform samples from a system population poses considerable problems in highly dynamic settings, like P2P systems, where the number of participants and their unpredictable behavior (e.g., churn, crashes etc.) may introduce relevant bias. Current implementations of the Peer Sampling Service are designed to provide uniform samples only in static settings and do not consider that biased samples can directly affect the correctness of algorithms relying on a uniformity property or be exploited by a malicious adversary to increase the effectiveness of its attacks to the system. In this paper we provide a practical solution to the biasing problem by deploying a fully distributed Peer Sampling Correction Module on top of a given, possibly biased, peer sampling service. Samples provided by the peer sampling service will be locally processed by this module, using computationally efficient hashing functions, before getting to the application. The effectiveness of our approach is evaluated through an extensive simulation-based study.

This paper studies the problem of realizing a common software clock among a large set of nodes without an external time reference (i.e., internal clock synchronization), any centralized control, and where nodes can join and leave the distributed system at their will. The paper proposes an internal clock synchronization algorithm which combines the gossip-based paradigm with a nature-inspired approach, coming from the coupled oscillators phenomenon, to cope with scale and churn. The algorithm works on the top of an overlay network and uses a uniform peer sampling service to fulfill each node's local view. Therefore, differently from clock synchronization protocols for small scale and static distributed systems, here, each node synchronizes regularly with only the neighbors in its local view and not with the whole system. An evaluation of the convergence speed and the synchronization error of the coupled-based internal clock synchronization algorithm has been carried out, showing how convergence time and the synchronization error depends on the coupling factor and the local view size. Moreover, the variation of the synchronization error with respect to churn and the impact of a sudden variation of the number of nodes have been analyzed to show the stability of the algorithm. In all these contexts, the algorithm shows nice performance and very good self-organizing properties. Finally, we showed how the assumption on the existence of a uniform peer-sampling service is instrumental for the good behavior of the algorithm and how, in system models where network delays are unbounded, a mean-based convergence function reaches a lower synchronization error than median-based convergence functions exploiting the number of averaged clock values.

Abstract Random walks can be conveniently exploited for implementing probabilistic algorithms to solve many searching problems arised by distributed applications, for example, service discovery, p2p file sharing, etc. In this paper we consider random walks executed on uniform wireless networks and study how to reduce the expected number of walk steps required to reach a target, namely the hitting time. The latter is the main search performance metric of a random walk based algorithm, since it determines the average response to a search as well as its cost; thus, the actual convenience of using random walks compared to other solutions depends on achieving a low hitting time. We show how in uniform wireless networks, the natural implementation of a random walk which selects the next node to visit at random among all neighbors is not a good choice, since it has a strong negative effect on the hitting time. This paper studies such a negative effect analytically and proposes two neighbor selection rules aiming at reducing the hitting time. A simulation study confirms the benefits of the proposed solutions. Copyright © 2008 John Wiley & Sons, Ltd.

This paper proposes an internal clock synchronization algorithm for very large number of processes that is able to (i) self-synchronize their local clocks without any central control and (ii) resist to attacks of an adversary whose aim is to put out-of-synchronization as many correct processes as possible. To cope with scale the algorithm utilizes the gossip-based paradigm where each process has a limited view of the system, while to resist to attacks the algorithm employs a filtering mechanism based on the notion of ¿-trimmed mean to filter out out-of-range clock values. The algorithm shows nice convergence in presence of networks errors and in absence of the adversary. When the adversary takes control of some of the processes in the system, we define two goals for the adversary, actually two predicates, to measure the strength of the attack. The first one captures the percentage of time in which at least one correct is out of synchronization and the second one when all correct processes are out of synchronization. The paper presents an extensive simulation study showing under which conditions (in terms of number of corrupted processes and size of local views) these two goals can be achieved by the adversary. Interestingly, these results can be exploited by applications that can tolerate either a certain time in which some correct process is non-synchronized or a certain percentage of correct processes that is non-synchronized.

This paper studies the existence and the regularity of Logarithmic Harary Graphs (LHGs). This study is motivated by the fact that these graphs are employed for modeling the communication topology to support efficient flooding in presence of link and node failures when considering an initial arbitrary number of nodes n. Therefore, the capability to identify graph constraints that allow the construction of LHGs for the largest number of pairs (n, k) (where k is the desired degree of connectivity to be tolerant to failures) becomes of primary importance. The paper presents several results in that direction. We introduce a graph constraint, namely K-TREE, that allows the construction of a LHG for every pair (n, k) such that n ges 2k. Secondly we presents another graph constraint for LHG, namely KDIAMOND, which is equivalent to K-TREE in terms of capability to construct LHGs for any pair (n, k). The interest of K-DIAMOND lies in the fact that, for a given k, KDIAMOND allows to construct more regular graphs than K-TREE does. A k-regular graph shows the minimal number of links required by a k-connected graph, leading tominimal flooding cost. The paper formally shows, in particular, that there are an infinite number of pairs (n, k), such that there exists a k-regular LHG for the pair (n, k) that satisfies K-DIAMOND and does not satisfy K-TREE.

Overlay management protocols have been introduced to guarantee overlay network connectivity in dynamic large- scale peer-to-peer systems. Some of these protocols have been specifically designed to avoid the partitioning of the overlay in large clusters (network breakage) despite massive node failures and the continuous arrivals/departures of nodes (churn). In this paper we identify a second effect connected to churn, namely network erosion. We show how erosion affects overlay network connectivity and point out that even a strongly connected overlay network, when exposed to continuous churn, can be disgregated. More specifically the consequences of erosion are shown, through an experimental study, in the context of overlay management protocols based on the view-exchange technique. We finally propose a connection recovery mechanism to be endowed at each node which is able to collaboratively detect node isolation and the presence of small clusters. This mechanism is shown to be effective in reducing the erosion of an overlay network exposed to continuous churn and to quickly recover its connectivity during stability periods.

Recently many scalable and efficient solutions for event dissemination in publish/subscribe (pub/sub) systems have appeared in the literature. This dissemination is usually done over an overlay network of brokers and its cost can be measured as the number of messages sent over the overlay to allow the event to reach all intended subscribers. Efficient solutions to this problem are often obtained through smart dissemination algorithms that avoid flooding events on the overlay. In this paper, we propose a complementary approach that obtains efficient event dissemination by reorganizing the overlay network topology. More specifically, this reorganization is done through a self-organizing algorithm executed by brokers whose aim is to directly connect, through overlay links, pairs of brokers matching same events. In this way, on average, the number of brokers involved in an event dissemination decreases, thus reducing its cost. Even though the paradigm of the self-organizing algorithm is general and then applicable to any overlay-based pub/sub system, its concrete implementation depends on the specific system. As a consequence, we studied the effect of the introduction of the self-organizing algorithm in the context of a specific system implementing a tree-based routing strategy, namely SIENA, showing the actual performance benefits through an extensive simulation study. In particular, performance results point out the capacity of the algorithm to converge to an overlay topology accommodating efficient event with respect to (w.r.t) dissemination a specific scenario. Moreover, the algorithm shows a significant capacity to adapt the overlay network topology to continuously changing scenarios while keeping an efficient behavior w.r.t. event dissemination.

Peer-to-peer systems (P2P) have become a popular technique to architect decentralized systems. However, despite its popularity most P2P systems consist in simple applications such as file sharing or chat systems. The main reason is that more complex applications require levels of consistency that nowadays are not offered by P2P systems. In this paper, we explore how to provide consistency based on distributed mutual exclusion via quorum systems in DHT-based P2P networks. Our results show that quorum systems applied directly to such networks are not scalable due to the high traffic imposed onto the underlying network. The paper introduces some design principles for both quorum systems and protocols using them that help to boost their performance. These design principles consist in dynamic and decentralized selection of quorums and in the exposition and exploitation of internals of the DHT such as the finger table. We show that by combining both design principles it is possible to minimize the number of visited sites and the latency needed to obtain a quorum