Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

Blockchain validators can reduce block processing time by exploiting multi-core CPUs, but deterministic execution must preserve a given total order while respecting transaction conflicts and per-block runtime limits. This paper systematically examines how validators can exploit multi-core parallelism during both block construction and execution without violating blockchain semantics. We formalize two validator-side optimization problems: (i) executing an already ordered block on p cores to minimize makespan while ensuring equivalence to sequential execution; and (ii) selecting and scheduling a subset of mempool transactions under a runtime limit B to maximize validator reward. For both, we develop exact Mixed-Integer Linear Programming (MILP) formulations that capture conflict, order, and capacity constraints, and propose fast deterministic heuristics that scale to realistic workloads. Using Ethereum mainnet traces and including a Solana-inspired declared-access baseline (Sol) for ordered-block scheduling and a simple reward-greedy baseline (RG) for block construction, we empirically quantify the trade-offs between optimality and runtime. MILPs quickly become intractable as heterogeneity or core count increases, whereas our heuristics run in milliseconds and achieve near-optimal quality. For ordered-block execution, heuristic makespans are typically within a few percent of the MILP solutions (and can even surpass the MILP incumbent when the solver times out), yielding up to 1.5 speedup with p = 2 and 2.3 speedup with p = 8 over sequential execution, despite tight ordering constraints. For block construction, the heuristic achieves 99-100% of the MILP optimum reward on homogeneous workloads, and 74-100% of an LP-relaxation upper bound on heterogeneous workloads, where exact optimization often times out. The resulting block-construction throughput scales close to linearly with p, reaching up to 7.9 speedup with p = 8 in our experiments. These results demonstrate that lightweight, conflict-aware scheduling and selection can unlock substantial parallelism in blockchain validation, bridging the gap between sequential execution and the true potential of multi-core hardware.

In order to formalize Distributed Ledger Technologies and their interconnections, recent research has introduced the concept of a Distributed Ledger Object (denoted $$\mathcal {O}^L$$ ), a concurrent abstraction that maintains a totally ordered sequence of records, capturing the essence of blockchains and distributed ledgers. In this work, we introduce the Distributed Grow-only Set object (denoted $$\mathcal {O}^{GS}$$ ), a novel abstraction that, unlike the $$\mathcal {O}^L$$ , maintains an immutable set of records by supporting only Add and Get operations. This object is inspired by the Grow-only Set (G-Set) a well-known Conflict-free Replicated Data Type (CRDT). We formally define the $$\mathcal {O}^{GS}$$ and present a Byzantine-tolerant, consensus-free implementation (denoted as $$\mathcal {O}^{GS}_B$$ ) that ensures eventual consistency. Building on this implementation, we propose consensus-free algorithmic solutions to two fundamental problems: the Atomic Appends problem, which concerns atomically appending multiple records to distinct ledgers, and the Atomic Adds problem, its counterpart in the context of G-Sets. Additionally, we show how the $$\mathcal {O}^{GS}_B$$ can be leveraged to construct a consensus-free, Single-Writer Byzantine-tolerant $$\mathcal {O}^L$$ . We argue that the applicability of the $$\mathcal {O}^{GS}_B$$ extends well beyond these specific use cases, offering a lightweight and efficient foundation for a variety of distributed applications.

Nowadays the traditional file systems cannot handle the new requirements in terms of volume of data, high performance, fault-tolerance, and improved capabilities. So Distributed Storage Systems (DSS) took place to cover the need of a shared storage between separate systems, provide a scalable storage to serve thousands of servers, and improve the fault-tolerance. To this respect, a series of issues need to be properly addressed: scalability, the ability to handle large data, high performance even under heavy access concurrency, versioning, and fault-tolerance. In this work, we propose CoBFS , a framework of a DSS designed to boost the concurrent access to large shared data objects (such as files), while maintaining strong consistency guarantees. CoBFS has two key design factors: data striping and versioning-based concurrency control (through coverability) to enable higher operation performance on large concurrent data objects. To this respect, we introduce the notions of a block as a “bounded” Read/Write register, of a fragmented object as a sequence of blocks, and of fragmented coverable linearizability , a strong consistency property suitable for fragmented objects. CoBFS adopts a modular architecture, separating the object fragmentation process from the shared memory service allowing to use different shared memory implementations. At first, we use as storage a static atomic distributed shared memory (ADSM) emulation, the well known ABD , yielding CoABDF , which satisfies fragmented coverable linearizability. Then, we substitute the storage layer of CoBFS with a dynamic (reconfigurable) storage algorithm, called Ares , yielding CoAresF ; CoAresF allows the addition and removal of servers without system interruptions and improves the storage efficiency due to the use of an erasure-coded mechanism. We conduct an extensive experimental evaluation on the Emulab and AWS EC2 testbeds, illustrating the benefits of our approaches, as well as other interesting tradeoffs. We believe that CoBFS ’s features (versioning, high concurrent accesses, handling large objects) has the potential of benefiting any static or dynamic storage algorithm to further extend its functionality for data-intensive applications at large scale.

Epidemiologists and social scientists have used the Network Scale-Up Method (NSUM) for over thirty years to estimate the size of a hidden sub-population within a social network. This method involves querying a subset of network nodes about the number of their neighbors belonging to the hidden sub-population. In general, NSUM assumes that the social network topology and the hidden sub-population distribution are well-behaved; hence, the NSUM estimate is close to the actual value. However, bounds on NSUM estimation errors have not been analytically proven. This paper provides analytical bounds on the error incurred by the two most popular NSUM estimators. These bounds assume that the queried nodes accurately provide their degree and the number of neighbors belonging to the hidden sub-population. Our key findings are twofold. First, we show that when an adversary designs the network and places the hidden sub-population, then the estimate can be a factor of Ω(√n) off from the real value (in a network with n nodes). Second, we also prove error bounds when the underlying network is randomly generated, showing that a small constant factor can be achieved with high probability using samples of logarithmic size O(log n). We present improved analytical bounds for Erdős-Rényi and Scale-Free networks. Our theoretical analysis is supported by an extensive set of numerical experiments designed to determine the effect of the sample size on the accuracy of the estimates in both synthetic and real networks.

This paper explores necessary and sufficient system conditions to solve distributed tasks with binary outputs (i.e., tasks with output values in {0,1}). We focus on the distinct output sets of values a task can produce (intentionally disregarding validity and value multiplicity), considering that some processes may output no value. In a distributed system with n processes, of which up to t ≤ n can crash, we provide a complete characterization of the tight conditions on n and t under which every class of tasks with binary outputs is solvable, for both synchronous and asynchronous systems. This output-set approach yields highly general results: it unifies multiple distributed computing problems, such as binary consensus and symmetry breaking, and it produces impossibility proofs that hold for stronger task formulations, including those that consider validity, account for value multiplicity, or move beyond binary outputs.

Auditing data accesses helps preserve privacy and ensures accountability by allowing one to determine who accessed (potentially sensitive) information. A prior formal definition of register auditability was based on the values returned by read operations, without accounting for cases where a reader might learn a value without explicitly reading it or gain knowledge of data access without being an auditor.

Auditability allows to track operations performed on a shared object, recording who accessed which information. This gives data owners more control on their data. Initially studied in the context of single-writer registers, this work extends the notion of auditability to other shared objects, and studies their properties. We start by moving from single-writer to multi-writer registers, and provide an implementation of an auditable n-writer m-reader read / write register, with O(n+m) step complexity. This implementation uses (m+n)-sliding registers, which have consensus number m+n. We show that this consensus number is necessary. The implementation extends naturally to support an auditable load-linked / store-conditional (LL/SC) shared object. LL/SC is a primitive that supports efficient implementation of many shared objects. Finally, we relate auditable registers to other access control objects, by implementing an anti-flickering deny list from auditable registers.

Indirect surveys, in which respondents provide information about other people they know, have been proposed for estimating (nowcasting) the size of a hidden population where privacy is important or the hidden population is hard to reach. Examples include estimating casualties in an earthquake, conditions among female sex workers, and the prevalence of drug use and infectious diseases. The Network Scale-up Method (NSUM) is the classical approach to developing estimates from indirect surveys, but it was designed for one-shot surveys. Further, it requires certain assumptions and asking for or estimating the number of individuals in each respondent's network. In recent years, surveys have been increasingly deployed online and can collect data continuously (e.g., COVID-19 surveys on Facebook during much of the pandemic). Conventional NSUM can be applied to these scenarios by analyzing the data independently at each point in time, but this misses the opportunity of leveraging the temporal dimension. We propose to use the responses from indirect surveys collected over time and develop analytical tools (i) to prove that indirect surveys can provide better estimates for the trends of the hidden population over time, as compared to direct surveys and (ii) to identify appropriate temporal aggregations to improve the estimates. We demonstrate through extensive simulations that our approach outperforms traditional NSUM and direct surveying methods. We also empirically demonstrate the superiority of our approach on a real indirect survey dataset of COVID-19 cases.

The COVID-19 pandemic exposed the importance of research on the spread of epidemic diseases. In the case of COVID-19, official data about infection prevalence was based on PCR and antigen tests reports, which can be unreliable. In our work, we construct prediction models based on Genetic Programming to estimate the SARS-Co V-2 seroprevalence of a given population from multiple estimates of the COVID-19 prevalence (official prevalence data, estimates derived from wastewater data, and estimates obtained from massive surveys with different rules and ML methods). To do that, we propose the use of stacking techniques based on Genetic Programming to obtain Machine Learning Ensemble Methods. Our approach produces more accurate prediction models than conventional stacking techniques based on Linear Regression.

In this work, we introduce a modular framework for specifying distributed systems that we call AMECOS. Specifically, our framework departs from the traditional use of sequential specification, which presents limitations both on the specification expressiveness and implementation efficiency of inherently concurrent objects, as documented by Castañeda, Rajsbaum and Raynal in CACM 2023. Our framework focuses on the interactions between the various system components, specified as concurrent objects. Interactions are described with sequences of object events. This provides a modular way of specifying distributed systems and separates legality (object semantics) from other issues, such as consistency. We demonstrate the usability of our framework by (i) specifying various well-known concurrent objects, such as registers, shared memory, message-passing, reliable broadcast, and consensus, (ii) providing hierarchies of ordering semantics (namely, consistency hierarchy, memory hierarchy, and reliable broadcast hierarchy), and (iii) presenting a novel axiomatic proof of the impossibility of the well-known Consensus problem.

Edge computing processes data near the source, minimizing latency and reducing bandwidth consumption by avoiding unnecessary data transmission to cloud servers. This decentralized approach is beneficial for real-time applications such as augmented reality, autonomous vehicles, and industrial automation. Fog computing, on the other hand, extends the cloud closer to the network edge, creating a distributed layer of intermediate fog nodes that provide additional processing and storage capabilities. This architecture balances the low-latency benefits of edge computing and the resource scalability of cloud computing. In parallel, the rapid growth of the Internet of Things (IoT) has led to an unprecedented increase in data generation and connectivity requirements. As a result, traditional cloud computing models have faced significant challenges in handling the high data transmission, processing, and storage volume while maintaining low latency and high efficiency. Novel computing paradigms like edge computing and fog computing have become critical components in IoT ecosystems. This paper reviews recent developments on edge computing, fog computing, and IoT recently published in The Computer Journal. By analyzing this broad range of research, we will examine how these technologies complement each other and address the growing demands of modern networked environments. Edge computing refers to processing data closer to where they are generated, at the edge of the network. It reduces latency by performing computations locally rather than sending all data to the cloud. Fog computing, on the other hand, extends cloud computing closer to the edge, providing an intermediate layer between edge devices and the cloud. It distributes processing across multiple fog nodes to enhance performance. Finally, the IoT is a network of interconnected devices that collect, share, and act on data. These devices include sensors, cameras, and smart home appliances. IoT relies on edge and fog computing to manage the vast amount of data generated, ensuring efficient processing and timely decision-making. Edge computing offers the lowest latency, making it ideal for real-time applications. Fog computing provides more scalability by distributing processing power across intermediate nodes, though with slightly higher latency. IoT, on the other hand, depends on both edge and fog computing to process and manage the data generated by connected devices. While edge computing focuses on immediate data processing, fog computing balances the need for quick processing with cloud scalability, supporting larger, more complex networks. In this section, articles with a focus on edge computing are reviewed. Tang et al. [1] propose a data-cleaning method to improve object localization accuracy in edge computing environments. The authors address how to deal with noisy and incomplete data, a problem often encountered in edge-based localization systems. They introduce a hybrid data cleaning approach, combining statistical techniques with machine learning models to enhance data quality. The proposed method outperforms existing techniques by reducing localization errors and improving the reliability of edge-based systems. Simulation results demonstrate that the scheme can significantly enhance accuracy and efficiency in real-time applications, especially in dynamic and complex environments. Tian et al. [2] propose CCESHP, which is a causal consistency model using a hash ring structure and partial geo-replication, specifically designed for edge storage systems. The model addresses the challenge of maintaining consistency across distributed edge nodes, particularly with IoT devices. The key contribution is the use of a two-hash system to map data keys and servers on a hash ring, enabling efficient grouping and partial replication of data across edge nodes. This allows for lower latency and higher fault tolerance compared with full replication models. Additionally, CCESHP minimizes data storage and transmission overhead by only replicating essential subsets of data in geo-distributed regions. The model provides causal consistency, ensuring that operations on data respect the order of causal dependencies. Simulations demonstrate good performance in terms of consistency, latency, and system throughput, making it suitable for large-scale edge computing environments. Yang et al. [3] develop an analytical model to evaluate the performance of a heterogeneous edge data center (EDC), which is crucial for IoT applications. The model captures the dynamics of EDC systems that are subject to security threats and heterogeneous workloads. The authors focus on how attacks and failures impact the performance of these systems, which are essential for delay-sensitive IoT jobs. Using their model, they derive performance metrics such as system throughput and resource utilization. They also examine profit-related metrics for EDC administrators, providing insights on how to maximize profitability while maintaining performance under vulnerable conditions. Simulation experiments validate the accuracy of the model and suggest strategies for optimizing EDC performance and security. The results highlight the importance of balancing resource allocation and system protection in edge computing environments. Brahmi and Selmi [4] propose a trust-aware web services composition approach using a coordinate system in an edge and cloud environment. The method, called CWS_SMA, focuses on optimizing trust and quality of service by leveraging mathematical coordinates. This framework enhances web service composition by improving the selection of trustworthy services based on their spatial coordinates in a multidimensional space. Additionally, it introduces cooperative intelligent agents to reduce composition response time. The proposed system is evaluated for performance, showcasing significant improvements in response time and trust computation. The approach targets applications in environments like edge computing, where dynamic service compositions are essential for maintaining efficiency and security. Hsu [5] presents a computational offloading method based on a dueling Deep Q-Network (DQN) model for mobile edge computing (MEC) in the Industrial Internet of Things (IIoT). The proposed method addresses task offloading problems in MEC using reinforcement learning to optimize decision-making. The dueling DQN model is employed to enhance the efficiency of offloading tasks by separating the estimation of state value and action value, thus improving the learning process. The method reduces the latency of task processing while optimizing energy consumption in IIoT networks, critical for real-time industrial applications. Simulation results show that the proposed approach outperforms traditional DQN models in terms of task execution time, resource utilization, and energy efficiency. The article contributes to developing intelligent offloading methods in dynamic IIoT environments with limited resources. Yao et al. [6] address the optimization problem of model caching and request routing in edge-enabled wireless sensor networks (WSNs). The focus is on improving the efficiency of deep neural network (DNN) models under constraints like budget, latency, and accuracy. The proposed solution considers both loading cost and resource sharing in a collaborative edge environment. The problem is proven to be NP-hard, and an approximation algorithm based on randomized rounding is presented. The algorithm achieves a provable approximation ratio and demonstrates a 58.8% improvement in system throughput compared with baseline approaches. Extensive simulations validate the effectiveness of the proposed solution in improving model caching and routing performance in WSNs. Jiang et al. [7] present a model-based analysis of resource allocation policies in cloud-edge computing environments. The article explores various strategies for allocating resources between cloud and edge layers, with a focus on balancing computational load, reducing latency, and maximizing resource utilization. Through modeling and simulations, they demonstrate how different policies impact system performance under varying workloads. The study evaluates policies based on key metrics such as response time, energy consumption, and overall system throughput. It highlights the trade-offs involved in prioritizing either edge or cloud resources, offering insights into the best allocation strategies depending on specific application requirements. The article concludes that hybrid approaches, combining both edge and cloud resources, generally provide better performance for heterogeneous workloads. Zhang et al. [8] propose a framework for task offloading in MEC, aiming to balance energy consumption and task latency. The article proposes a collaborative task offloading scheme, where tasks are offloaded to edge servers, and computation results are reused to further improve efficiency. By leveraging partial offloading and result caching, the system reduces redundant computations, thus optimizing resource use. A game-theoretic approach is adopted to model user cooperation and task offloading, minimizing energy consumption. The article also explores the benefits of computation result sharing between users, reducing overall computational load. Extensive simulation results show that the proposed method significantly lowers latency and energy consumption compared with traditional offloading strategies. The framework is particularly effective in environments with dynamic and heterogeneous user demands. Pourian et al. [9] present a deep learning model for energy-aware task scheduling in fog computing environments. The focus is on reducing energy consumption, a key challenge in fog-based IoT systems. The proposed model uses a scheduling algorithm based on Learning Automata (LA) to optimize task scheduling for energy efficiency, makespan, and cost. The article further enhances the LA algorithm by integrating a neural network-based prediction model to forecast the relationship between makespan, energy consumption, and cost. The model successfully reduces the energy usage by 20% while maintaining efficient task scheduling. Extensive simulations validate the model’s accuracy and reliability, showing significant improvements over existing approaches. Hala and Sridevi [10] propose an approach to improve task processing in mobile real-time IoT applications within fog-cloud computing environments. The article addresses the challenges of mobility, security, and resource constraints in task scheduling. They introduce three algorithms to allocate mobile IoT devices to the appropriate edge device, considering factors like distance and bandwidth load. Additionally, a fuzzy-logic-based scheduling algorithm is developed to optimize task distribution between fog and cloud layers while ensuring security requirements are met. The proposed approach improves task processing time, turnaround time, and success ratio compared with existing methods. The results demonstrate that integrating distance and bandwidth considerations can enhance overall task processing efficiency. Xu et al. [11] propose a hybrid optimization algorithm for resource recommendation in fog-based IoT environments. The article focuses on improving resource allocation efficiency, by addressing the challenge of having unpredictable and highly dynamic fog environments. The authors develop a hybrid approach that combines cooperative filtering with the Artificial Bee Colony algorithm to enhance the accuracy of resource recommendations. Using CloudSim for simulation, the proposed method demonstrates improvements in accuracy by 1%–8% compared with traditional methods. Ma et al. [12] introduce KEFSAR, a solar-aware routing strategy for rechargeable IoT networks. The article addresses energy management challenges in WSNs powered by solar energy. KEFSAR uses high-accuracy prediction algorithms to optimize energy usage by taking into account the unpredictable nature of solar energy availability, such as weather changes and shadows. The routing strategy employs a combination of classification and recurrent neural networks (RNNs) for energy prediction and incorporates a shadow judgment method to improve accuracy. KEFSAR dynamically adjusts network routing based on solar intensity, improving both the energy efficiency and longevity of the network. Experimental results show that KEFSAR enhances prediction accuracy by 30%–50% and extends network lifetime by 10%–42%. Gökçen et al. [13] investigate the use of machine learning algorithms to forecast Li-ion battery discharge patterns in IoT devices. The article assumes that IoT devices are subject to random usage patterns. The authors evaluated various machine learning models, such as artificial neural networks (ANNs), Gaussian processes, and nonlinear regression, to predict battery capacity and internal resistance changes as a function of discharged energy. The discharge patterns are modeled using data from the NASA Ames prognostics data repository. The ANN model, with a radial basis function and a single hidden layer of 20 neurons, outperformed other models, achieving high prediction accuracy with |$R^{2}=1.0000$| and a low normalized mean square error. Wang et al. [14] introduce KVFL, a fuzzing framework tailored for IoT web servers. Unlike conventional fuzzing techniques, KVFL leverages key-value-based persistent fuzzing to effectively identify vulnerabilities in resource-constrained IoT devices. IoT web servers, widely used for management and data collection, are an attractive attack surface. KVFL operates by flipping specific data bits and injecting anomalous inputs to expose weaknesses. The framework enhances the fuzzing process by incorporating domain-specific key-value pairs that help achieve a high vulnerability detection rate while minimizing performance overhead. KVFL also supports continuous fuzzing sessions, increasing its potential for discovering complex bugs that require prolonged fuzzing periods. Experimental results show KVFL detects security flaws faster and with higher accuracy compared with traditional fuzzers. Cao et al. [15] propose an efficient deep learning-based approach to intrusion detection in IoT networks, addressing the increasing security risks in the IoT environment. The method leverages a convolutional neural network (CNN) to automatically extract features from network traffic data. A combination of CNN and an RNN is employed to enhance the detection of malicious activity by analyzing temporal patterns in the data. The approach was tested on the NSL-KDD dataset, achieving high accuracy and low false positive rates. The authors highlight that their system requires less manual feature engineering, improving efficiency compared with traditional methods. Moreover, the proposed model is scalable and can adapt to the high-volume, dynamic data characteristic of IoT systems. This makes the model well suited for real-time intrusion detection in large IoT infrastructures. Dung et al. [16] propose CAIMP, which is a cross-architecture malware detection and prediction framework for IoT devices. The proposed method relies on static features, such as opcode sequences, to detect malware across different hardware architectures. Using a machine learning model trained on these static features, CAIMP achieves high accuracy in detecting malware, reaching up to 99.4% in experiments. The approach is particularly effective in addressing the challenge of detecting malware that can operate on various hardware platforms, a key concern in heterogeneous IoT environments. CAIMP also includes predictive capabilities to anticipate malware behavior before full execution. The authors emphasize that CAIMP offers significant improvements in malware detection across IoT devices while maintaining a low false-positive rate. Zeng et al. [17] present a privacy-preserving framework for IoT data sharing using federated learning (FL) and generative adversarial networks (GANs). Federated learning enables decentralized data training on local devices, ensuring that sensitive data never leave the device. However, IoT data are vulnerable to privacy attacks. To mitigate this, the authors propose an enhanced FL model using GANs to generate synthetic data while protecting privacy. The model introduces noise to the GAN during training to prevent privacy leakage while preserving data utility. The proposed solution effectively balances data utility and privacy, as demonstrated in experimental results showing minimal performance degradation compared with traditional methods. Gómez et al. [18] propose a forensic methodology to investigate cyber incidents in IoT environments. The authors address the growing need for forensic tools capable of handling the complexity and scale of IoT systems. The methodology integrates traditional forensic models with IoT-specific adaptations, ensuring the ability to trace, collect, and analyze data effectively in distributed and heterogeneous networks. Key features include a layered approach to forensic investigation, addressing data volatility, and the need for secure evidence collection. Additionally, the method considers both technical and legal constraints, ensuring that the forensic process adheres to legal requirements while maintaining data integrity. Experimental validation demonstrates the methodology’s efficacy in identifying and addressing IoT-related cyber incidents. Zhang et al. [19] focus on the challenges of verifying the robustness of DNNs in smart IoT devices. As IoT devices are exposed to diverse environments and adversarial attacks, ensuring the robustness of their DNNs is critical to maintaining their functionality and security. The authors propose a formal verification method to improve the efficiency and accuracy of verifying DNN robustness in IoT systems. The key contribution is a tight linear approximation technique, which enables the efficient handling of complex neural network structures without sacrificing verification precision. This method helps in detecting adversarial inputs, reducing the risk of incorrect classifications in IoT devices. The results show that the proposed method outperforms previous approaches, especially in terms of scalability and computational efficiency. Noor [20] presents an innovative approach to crowd management using IoT technologies combined with behavior analysis. With growing populations, managing large crowds, especially during events like the Hajj pilgrimage, is crucial for safety. The proposed system uses IoT devices, such as cameras, to collect data and monitor crowds in real-time. A behavior analysis algorithm based on hidden Markov models is employed to identify normal and abnormal behaviors by analyzing spatio-temporal video segments. The approach allows for the classification of crowd dynamics and provides decision-makers with real-time insights to manage crowds effectively. Experimental results, based on real datasets from the Hajj pilgrimage, show that the system performs well in real-time environments. Antony and Singh [21] present a blockchain-based public key infrastructure designed for IoT-based healthcare systems. The proposed system leverages blockchain’s decentralized nature to overcome security challenges commonly faced in IoT networks. Using elliptic curve cryptography and smart contracts, the system allows secure communication and data exchange between IoT devices in healthcare environments. The article highlights how the integration of blockchain with IoT enhances data integrity, transparency, and resistance to cyberattacks. The system uses a secure key generation and distribution mechanism that ensures robustness against common threats, such as man-in-the-middle and replay attacks. Furthermore, the use of smart contracts ensures automated validation and revocation of certificates, reducing the need for a centralized authority. The proposed infrastructure addresses scalability and security issues in healthcare IoT applications, ensuring patient data privacy and secure communication across distributed IoT devices. Abid et al. [22] propose a blockchain and smart contract-based framework designed to address access control challenges in smart healthcare systems. Traditional access control models often rely on a centralized third party, which raises transparency and privacy concerns. To overcome this, the framework leverages blockchain technology and smart contracts to provide a decentralized, trustworthy solution. It integrates the generalized temporal role-based access control model to enforce fine-grained policies with temporal constraints. An initial implementation of the framework was evaluated for performance, showing linear increases in cost relative to policy complexity. Experimental results indicate that the approach is secure, efficient, and requires low operational costs. ChatGPT 4o has been used to summarize and extract keywords from articles.

Blockchain technologies are facing a scalability challenge, which must be overcome to guarantee a wider adoption of the technology. This scalability issue is due to the use of consensus algorithms to guarantee the total order of the chain of blocks (and of the transactions within each block). However, total order is often not fully necessary, since important advanced applications of smart-contracts do not require a total order among all operations. A much higher scalability can potentially be achieved if a more relaxed order (instead of a total order) can be exploited. In this article, we propose a novel distributed concurrent data type, Setchain , which significantly improves scalability. A Setchain implements a grow-only set whose elements are not ordered, unlike conventional blockchain operations. When convenient, the Setchain allows forcing a synchronization barrier that assigns permanently an epoch number to a subset of the latest elements added, agreed by consensus. Therefore, two operations in the same epoch are not ordered, while two operations in different epochs are ordered by their respective epoch number. We present different Byzantine-tolerant implementations of Setchain, prove their correctness, and report on an empirical evaluation of a prototype implementation. Our results show that Setchain is orders of magnitude faster than consensus-based ledgers, since it implements grow-only sets with epoch synchronization instead of total order. Since the Setchain barriers can be synchronized with the underlying blockchain, Setchain objects can be used as a sidechain to implement many decentralized solutions with much faster operations than direct implementations on top of blockchains. Finally, we also present an algorithm that encompasses into a single process the combined behavior of the Byzantine servers, which simplifies correctness proofs by encoding the general attacker in a concrete implementation.

The COVID-19 pandemic exposed the importance of research on the spread of epidemic diseases. In this paper, we apply Artificial Intelligence and statistics techniques to build prediction models to estimate the SARS-CoV-2 seroprevalence in the United States, using multiple estimates of COVID-19 prevalence and other explanatory variables. We propose the use of stacking techniques based on multiple model building techniques (Linear and Beta Regression, Genetic Programming and Neural Networks) to obtain Predictive Ensemble Models. There has been extensive research on this field, but there has not been in-depth research on the application of stacking methods to estimate and forecast seroprevalence in the USA specifically. This paper provides a novel comparison of the behaviour and performance of different building techniques for stacking ensemble models and presents which methods are better for different scenarios. We find that Genetic Programming and Neural Networks are the best models with trained data within single states, and when multiple states are considered Genetic Programming is still better than the Regression models, but Neural Networks fail to estimate the seroprevalence accurately. Another novelty of our work is the use of cross-state validation to evaluate the models with new data, as well as temporal forecasting. Depending on how the data is processed, Linear Regression performs very well with cross-state validation and temporal forecasting, and Genetic Programming is very accurate with the former while Neural Networks work better with the latter.

To simplify definitions of network-wide behaviors (e.g., in datacenter transports), networks are often represented by virtual switches. In most cases, the buffering architecture of a representing virtual switch is inherited from analytic models implementing the desired properties, and is completely decoupled from the represented network topology. Thus, it is unclear how well the network infrastructure is exploited. This paper makes the first attempt in understanding which buffering architectures can best represent a given network, and how buffer management decisions can be mapped back to a represented network.

Leveraging machine learning (ML) for the detection of network problems dates back to handling call-dropping issues in telephony. However, troubleshooting cellular networks is still a manual task, assigned to experts who monitor the network around the clock. We present here TTrees (from Troubleshooting Trees), a practical and interpretable ML software tool that implements a methodology we have designed to automate the identification of the causes of performance anomalies in a cellular network. This methodology is unsupervised and combines multiple ML algorithms (e.g., decision trees and clustering). TTrees requires small volumes of data and is quick at training. Our experiments using real data from operational commercial mobile networks show that TTrees can automatically identify and accurately classify network anomalies - e.g., cases for which a network low performance is not apparently justified by op-erational conditions - training with just a few hundreds of data samples, hence enabling precise troubleshooting actions.

Superintelligence is a hypothetical agent that possesses intelligence far surpassing that of the brightest and most gifted human minds. In light of recent advances in machine intelligence, a number of scientists, philosophers and technologists have revived the discussion about the potentially catastrophic risks entailed by such an entity. In this article, we trace the origins and development of the neo-fear of superintelligence, and some of the major proposals for its containment. We argue that total containment is, in principle, impossible, due to fundamental limits inherent to computing itself. Assuming that a superintelligence will contain a program that includes all the programs that can be executed by a universal Turing machine on input potentially as complex as the state of the world, strict containment requires simulations of such a program, something theoretically (and practically) impossible. This article is part of the special track on AI and Society.

Millimeter wave (mmWave) communication not only provides ultra-high speed radio access but is also ideally suited for efficient and flexible wireless backhauling. Specifically for dense deployments, a mmWave macro base station (MBS) that serves a large number of mmWave micro base stations (μBSs) is much more cost effective than legacy cellular architectures which connect μBSs to the core network through fibers. In addition, μBSs can cooperate with each other by acting as relay nodes. The directional nature of mmWave communication allows for spatial reuse, even in the presence of interference, which can be exploited to optimize mmWave wireless backhaul performance. The optimization opportunistically prioritizes the use of good connections at the MBS and further leverages compact and concurrent transmissions between μBS. Relays and directional antennas speed up communication, but increase the complexity of the scheduling problem. In this work, we study the mmWave backhaul scheduling problem and derive an MILP formulation for it as well as upper and lower bounds. We prove that the problem is NP-hard and can be approximated, but only if interference is negligible. By means of numerical simulations, we compare theoretical results with heuristics in small system sizes. Results validate the analysis and demonstrate the high performance of our heuristics in realistic cellular settings.

Modern privacy regulations, including the General Data Protection Regulation (GDPR) in the European Union, aim to control user tracking activities in websites and mobile applications. These privacy rules typically contain specific provisions and strict requirements for websites that provide sensitive material to end users such as sexual, religious, and health services. However, little is known about the privacy risks that users face when visiting such websites, and about their regulatory compliance. In this paper, we present the first comprehensive and large-scale analysis of 6,843 pornographic websites. We provide an exhaustive behavioral analysis of the use of tracking methods by these websites, and their lack of regulatory compliance, including the absence of age-verification mechanisms and methods to obtain informed user consent. The results indicate that, as in the regular web, tracking is prevalent across pornographic sites: 72% of the websites use third-party cookies and 5% leverage advanced user fingerprinting technologies. Yet, our analysis reveals a third-party tracking ecosystem semi-decoupled from the regular web in which various analytics and advertising services track users across, and outside, pornographic websites. We complete the paper with a regulatory compliance analysis in the context of the EU GDPR, and newer legal requirements to implement verifiable access control mechanisms (e.g., UK's Digital Economy Act). We find that only 16% of the analyzed websites have an accessible privacy policy and only 4% provide a cookie consent banner. The use of verifiable access control mechanisms is limited to prominent pornographic websites.

Advanced Driver Assistance Systems require a tremendous amount of sensor information to support the driver's comfort and safety. In particular, systems that provide (good) route options to a vehicle rely on information, such as traffic jams and road blockages, which is sensed by other (possibly distant) vehicles and distributed by a central server. This information is clearly dynamic and may be invalid by the time the vehicle arrives at the affected location. In this work, we develop an innovative approach to determine optimal routes (minimizing the costs like travel-time to their destination) for vehicles whose original route is adversely impacted by a (severe) road event. A set of recursive equations is developed that yields the optimal decision for each vehicle at each decision-point. Simulations show that our approach adapts to the considered event and finds routes of similar quality as a full-knowledge approach with limited communication overhead.

This work provides a proper formalization for Distributed Ledger Objects (as first defined in [Antonio Fernández Anta et al., 2018]), when processes may be Byzantine. The formal definitions are accompanied by algorithms to implement Byzantine Distributed Ledgers by utilizing a Byzantine Atomic Broadcast service.

With the widespread adoption of temporal graphs to study fast evolving interactions in dynamic networks, attention is needed to provide graph metrics in time and at scale. In this paper, we introduce ATMoN, an open-source library developed to computationally offload graph processing engines and ease the communication overhead in dynamic networks over an unprecedented wealth of data. This is achieved, by efficiently adapting, in place and inexpensively, the temporal granularity at which graph metrics are computed based on runtime knowledge captured by a low-cost probabilistic learning model capable of approximating both the metric stream evolution and the volatility of the graph topology. After a thorough evaluation with real-world data from mobile, face-to-face and vehicular networks, results show that ATMoN is able to reduce the compute overhead by at least 76%, data volume by 60% and overall cloud costs by at least 54%, while always maintaining accuracy above 88%.

We introduce structural transformations that allow simplifying a given network while preserving its original “bandwidth” and “routing” capabilities, transparently to specific allocations. We minimize a certain objective such as the aggregate capacity of network links, number of nodes, or number of links, in such a way that all the bandwidth that could be routed in the original network can also be routed in the reduced one. This improves cost-efficiency for both inter- and intra-datacenter connections and simplifies network management. We also identify a fundamental tradeoff between extra added capacity and simplicity of representation for a given network. Our analytic results are supported by extensive simulation results on hundreds of real network topologies. One result is that by adding 10-30% extra capacity to evaluated real-world networks one can simplify them down to a star topology with a single switch, while all routing and bandwidth allocation decisions on the simplified topology can be mapped back to the original network. This is an important step towards simplifying network management via a reduced virtualized network infrastructure.

A distributed system is considered that carries out computational tasks according to the master-worker paradigm. A master has a set of computational tasks to resolve. She assigns each task to a set of workers over the Internet, instead of computing the task locally. For each task each worker reply to the master with the task result. Since the task was not computed locally, the master can not trust the result for two main reasons: (i) workers might deliberately provide an incorrect result, (ii) the result is corrupted due to some hardware or software failure during the execution of the task. Given the above, we can model our workers as either “altruistic”, always willing to provide the correct result to each task, or “troll” that are trying to provide an incorrect result to each task. Moreover we model the failure of the worker to comply with her intended behavior, as an error probability ε. The goal of the master is to compute the correct result of all the tasks with high probability. In the literature two techniques have been used to achieve this goal: (i) “voting”, that determines the correct result of a task given multiple replies of distinct workers; (ii) “challenges”, that are tasks whose result is known and can be used to detect altruistic workers. What separates our work from the current literature is the realistic modelling of the worker's behavior and the fact that we do not restrict the task result to a binary set of answers; the domain of possible replies for a task can have multiple correct and multiple incorrect results. Given the above we evaluate the performance of the two techniques described in the literature in the scenario where ε = 0 and when ε > 0. Performance is measured in terms of: (1) time, i.e., the number of rounds performed by an algorithm for the computation of all the tasks, and (2) work, i.e., the number of total task computations performed by the workers. The case where ε = 0 is used as a best case scenario that provides the optimal time and work bounds of the problem. In the case where ε > 0 we propose two “natural” algorithms: one using a combination of both voting and challenges, and a second one using only voting. Both algorithms assume that certain system parameters are known. Since this might not always be the case we also provide an algorithm that estimates correctly these parameters with high probability.

An object type characterizes the domain space and the operations that can be invoked on an object of that type. In this paper we introduce a new property for concurrent objects, we call coverability, that aims to provide precise guarantees on the consistent evolution of the version (and thus value) of an object. This new property is suitable for a variety of distributed objects, including concurrent file objects, that demand operations to manipulate the latest version of the object. To preserve the order of versions, traditional approaches use locking, compare-and-swap (CAS), or linked-load/conditional-store (LL/SC) primitives to allow a single modification at a time on such objects. Such primitives however can be used to solve consensus, and thus are impossible to be implemented in an asynchronous, message-passing environment with failures. Coverability, relaxes the strong requirements imposed by stronger primitives, and allows us to define and implement consistent versioning in the aforementioned adversarial environment. In particular, coverability allows multiple operations to modify the same version of an object concurrently, leading to a set of different versions. Given an order of operations, coverability properties specify a single version in that set that any subsequent operation may modify, preserving this way the consistent evolution of the object. We first define versioned objects and then provide the specification of coverability. We then combine coverability with atomic guarantees to yield coverable atomic read/write registers; we show that coverable registers cannot be implemented by similar types of registers, such as ranked-registers. Next, we show how coverable registers may be implemented by modifying an existing MWMR atomic register implementation, and we continue by showing that coverable registers may be used to implement basic (weak) read-modify-write and file objects.

Communication demands are usually the leading factor that defines the efficiency of operations on a read/write shared memory emulation in the message-passing environment. In the quest for minimizing the communication demands, the algorithms proposed either require restrictions in the system or incur high computation demands. As a result, such solutions may be not suitable to be used in practice. In this paper we focus on the practicality of implementations of atomic read/write shared memory emulation in the message-passing environment. In particular we investigate implementations that reduce both communication and computation demands. We first examine the shortcomings of the best two (in terms of communication demands) known algorithms that implement atomic single-writer multiple-reader (SWMR) atomic memory. The algorithm ccFast proposed by A. Fernández et al., achieves optimal communication by allowing each operation to complete in one round trip, with light computation requirements. Unfortunately, it relies on strict limitations on the number of readers. On the other hand, algorithm OhSam, imposes no restrictions on the system, but provides operations that require one and a half communication rounds. In the light of these shortcomings, we present two algorithms that implement multi-speed operations with light computation, and without imposing any restriction on the system. In particular, algorithm ccHybrid adopts the fast (one-round) writes and makes clients to switch to a slow (two-round) mode whenever the system is congested. On the other hand, algorithm OhFast, pushes the responsibility of deciding for the speed switch to the servers. This allows the algorithm to utilize the fast operations, and the slow one-and-a-half-rounds operations of the algorithm presented by T. Hadjistasi et al., whenever is necessary. We prove that both new algorithms preserve atomicity. To evaluate the new algorithms we implement five different atomic memory algorithms in the NS3 simulator, and we compare their performance in terms of operation latency, and ratio of slow over fast operations performed. We test the algorithms over different: (i) topologies, and (ii) operation loads. Our results support that the newly presented algorithms increase the practicality of atomic read/write atomic shared memory implementations in the message-passing, asynchronous environment.

We consider a computing system where a master processor assigns tasks for execution to worker processors through the Internet. We model the workers' decision of whether to comply (compute the task) or not (return a bogus result to save the computation cost) as a mixed extension of a strategic game among workers. That is, we assume that workers are rational in a game-theoretic sense, and that they randomize their strategic choice. Workers are assigned multiple tasks in subsequent rounds. We model the system as an infinitely repeated game of the mixed extension of the strategic game. In each round, the master decides stochastically whether to accept the answer of the majority or verify the answers received, at some cost. Incentives and/or penalties are applied to workers accordingly. Under the above framework, we study the conditions in which the master can reliably obtain tasks results, exploiting that the repeated game model captures the effect of long-term interaction. That is, workers take into account that their behavior in one computation will have an effect on the behavior of other workers in the future. Indeed, should a worker be found to deviate from some agreed strategic choice, the remaining workers would change their own strategy to penalize the deviator. Hence, being rational, workers do not deviate. We identify analytically the parameter conditions to induce a desired worker behavior, and we evaluate experimentally the mechanisms derived from such conditions. We also compare the performance of our mechanisms with a previously known multi-round mechanism based on reinforcement learning.

The proliferation of new online Internet services has substantially increased the energy consumption in wired networks, which has become a critical issue for Internet service providers. In this paper, we target the network-wide energy-saving problem by leveraging speed scaling as the energy-saving strategy. We propose a distributed routing scheme-HDEER-to improve network energy efficiency in a distributed manner without significantly compromising traffic delay. HDEER is a two-stage routing scheme where a simple distributed multipath finding algorithm is firstly performed to guarantee loop-free routing, and then a distributed routing algorithm is executed for energy-efficient routing in each node among the multiple loop-free paths. We conduct extensive experiments on the NS3 simulator and simulations with real network topologies in different scales under different traffic scenarios. Experiment results show that HDEER can reduce network energy consumption with a fair tradeoff between network energy consumption and traffic delay.

Peer to peer (P2P) systems have moved from application specific architectures to a generic service oriented design philosophy. This raised interesting problems in connection with providing useful P2P middleware services capable of dealing with resource assignment and management in a large-scale, heterogeneous and unreliable environment. The slicing problem consists of partitioning a P2P network into$k$groups (slices) of a given portion of the network nodes that share similar resource values. As the network is large and dynamic this partitioning is continuously updated without any node knowing the network size. In this paper, we propose the first algorithm to solve the slicing problem. We introduce the metric of slice disorder and show that the existing ordering algorithm cannot nullify this disorder. We propose a new algorithm that speeds up the existing ordering algorithm but that suffers from the same inaccuracy. Then, we propose another algorithm based on ranking that is provably convergent under reasonable assumptions. In particular, we notice experimentally that ordering algorithms suffer from resource-correlated churn while the ranking algorithm can cope with it. These algorithms are proved viable theoretically and experimentally.

With the rapid development of software defined networking and network function virtualization, researchers have proposed a new cloud networking model called Network-as-a-Service (NaaS) which enables both in-network packet processing and application-specific network control. In this paper, we revisit the problem of achieving network energy efficiency in data centers and identify some new optimization challenges under the NaaS model. Particularly, we extend the energy-efficient routing optimization from single-resource to multi-resource settings. We characterize the problem through a detailed model and provide a formal problem definition. Due to the high complexity of direct solutions, we propose a greedy routing scheme to approximate the optimum, where flows are selected progressively to exhaust residual capacities of active nodes, and routing paths are assigned based on the distributions of both node residual capacities and flow demands. By leveraging the structural regularity of data center networks, we also provide a fast topology-aware heuristic method based on hierarchically solving a series of vector bin packing instances. Extensive simulations show that the proposed routing scheme can achieve significant gain on energy savings and the topology-aware heuristic can produce comparably good results while reducing the computation time to a large extent.

Communication overhead is the most commonly used performance metric for the operation complexity of distributed algorithms in message-passing environments. However, aside with communication, many distributed operations utilize complex computations to reach their desired outcomes. Therefore, a most accurate operation latency measure should account of both computation and communication metrics. In this paper we focus on the efficiency of read and write operations in an atomic read/write shared memory emulation in the message-passing environment. We examine the operation complexity of the best known atomic register algorithm, that allows all read and write operations to complete in a single communication round-trip. Such operations are called fast. At its heart, the algorithm utilizes a predicate to allow processes to compute their outcome. We show that the predicate used is computationally hard, by devising a computationally equivalent problem and reducing that to Maximum Biclique, a known NP-hard problem. To improve the computational complexity of the algorithm we derive a new predicate that leads to a new algorithm, we call ccFast, and has the following properties: (i) can be computed in polynomial time, rendering each read operation in ccFast tractable compared to the read operations in the original algorithm, (ii) the messages used in ccFast are reduced in size, compared to the original algorithm, by almost a linear factor, (iii) allows all operations in ccFast to be fast, and (iv) allows ccFast to preserve atomicity. A linear time}algorithm for the computation of the new predicate is presented along with an analysis of the message complexity of the new algorithm. We believe that the new algorithm redefines the term fast capturing both the communication and the computation metrics of each operation.

The CONGEST model is a synchronous, message-passing model of distributed computation in which each node can send (possibly different) messages of O(log n) bits along each of its incident communication links in each round, where n is the number of computing nodes in the system. In the particular case where the communication network is a complete graph, we have the unicast congested clique model. On the other end is the broadcast version of the congested clique model, in which each node can only broadcast a single message over all its links in each round. In this paper we explore the space, in terms of round complexity, that lies between these two congested clique models. Hence, we parametrize the congested clique model with the range r, the maximum number of different messages a node can send over its incident links in one round. Additionally, we study the effect of the bandwidth b, the maximum size in bits of these messages. We show that the space between the unicast and broadcast congested clique models is very rich and interesting. For instance, we show that a problem (especially designed for this work) takes Ω(n/ log n) rounds in the broadcast model (r = 1), while it can be solved in two rounds if two messages can be sent (r = 2). Other gaps are found in other parts of the spectrum of values of r. We do this by providing techniques to simulate protocols with different parameters. Therefore, we conclude that, with respect to their power to solve certain problems, there is a strict hierarchy of congested clique models.

In this work, we present an exhaustive empirical characterization of the power requirements of multiple components of data center servers. To do so, we devise different experiments to stress these components, taking into account the multiple available frequencies and the fact that we are working with multicore servers. In these experiments, we measure energy consumption of server components and identify their optimal operational points. Our study proves that the curve defining the minimal CPU power utilization, as a function of the load in active cycles per second, is neither concave nor purely convex. Instead, it definitively shows a super-linear dependence on the load. Similarly, we present results on how to improve the efficiency of network cards and disks. Finally, we validate the accuracy of the model derived from our characterization by comparing the real energy consumed by two Hadoop applications-PageRank and WordCount-with the estimation from our model, obtaining errors below 4.1% on average.

Multilayer video streaming allows to provide different video qualities to a group of multicast receivers with heterogeneous receive rates. The number of layers received (and thus the receive rate) determines the quality of the decoded video stream. For such layered multicast streaming, network coding provides higher capacity than multicast routing. Network coding can be performed within a layer or across layers, and in general, interlayer coding outperforms intralayer coding. An optimal solution to a network-coded layered multicast problem may require decoding of the network code at interior nodes to extract information to be forwarded. However, decoding consumes resources and introduces delay, which is particularly undesirable at interior nodes (the routers) of the network. In this paper, we thus focus on the interlayer network coding problem without decoding at interior nodes. We show that the problem is NP-hard and propose a heuristic algorithm for rate allocation and coding based on the Edmonds-Karp maximum flow algorithm. We prove that our algorithm ensures decodability of the information received and provides some fairness properties. Finally, we perform extensive simulations and show that our algorithm may even outperform other heuristics that do require decoding at interior nodes.

We consider Internet-based master-worker computations, where a master processor assigns, across the Internet, a computational task to a set of untrusted worker processors, and collects their responses. Examples of such computations are the "@homeâ' projects such as SETI. In this work, various worker behaviors are considered. Altruistic workers always return the correct result of the task, malicious workers always return an incorrect result, and rational workers act based on their self-interest. In a massive computation platform, such as the Internet, it is expected that all three type of workers coexist. Therefore, in this work, we study Internet-based master-worker computations in the presence of malicious, altruistic, and rational workers. A stochastic distribution of the workers over the three types is assumed. In addition, we consider the possibility that the communication between the master and the workers is not reliable, and that workers could be unavailable. Considering all the three types of workers renders a combination of game-theoretic and classical distributed computing approaches to the design of mechanisms for reliable Internet-based computing. Indeed, in this work, we design and analyze two algorithmic mechanisms to provide appropriate incentives to rational workers to act correctly, despite the malicious workers' actions and the unreliability of the communication. Only when necessary, the incentives are used to force the rational players to a certain equilibrium (which forces the workers to be truthful) that overcomes the attempt of the malicious workers to deceive the master. Finally, the mechanisms are analyzed in two realistic Internet-based master-worker settings, a SETI-like one and a contractor-based one, such as Amazon's mechanical turk. We also present plots that illustrate the tradeoffs between reliability and cost, under different system parameters.

The bisection width of interconnection networks has always been important in parallel computing, since it bounds the speed at which information can be moved from one side of a network to another, i.e., the bisection bandwidth. Finding its exact value has proven to be challenging for some network families. For instance, the problem of finding the exact bisection width of the multidimensional torus was posed by Leighton [1, Problem 1.281] and has remained open for almost 20 years. We provide two general results that allow us to obtain upper and lower bounds on the bisection width of any product graph as a function of some properties of its factor graphs. The power of these results is shown by deriving the exact value of the bisection width of the torus, as well as of several d-dimensional classical parallel topologies that can be obtained by the application of the Cartesian product of graphs. We also apply these results to data centers, by obtaining bounds for the bisection bandwidth of the d-dimensional BCube network, a recently proposed topology for data centers.

SUMMARY We consider Internet‐based master–worker task computations, such as SETI@home, where a master process sends tasks, across the Internet, to worker processes; workers execute and report back some result. However, these workers are not trustworthy, and it might be at their best interest to report incorrect results. In such master–worker computations, the behavior and the best interest of the workers might change over time. We model such computations using evolutionary dynamics, and we study the conditions under which the master can reliably obtain task results. In particular, we develop and analyze an algorithmic mechanism based on reinforcement learning to provide workers with the necessary incentives to eventually become truthful. Our analysis identifies the conditions under which truthful behavior can be ensured and bounds the expected convergence time to that behavior. The analysis is complemented with illustrative simulations. Copyright © 2013 John Wiley & Sons, Ltd.

Abstract Energy conservation is drawing increasing attention in data networking. As networks are designed for peak traffic, network elements typically operate at full speed and consume maximum power even when carrying low traffic. One school of thought believes that a dominant amount of power saving comes from turning off network elements. The difficulty is that transitioning between the active and sleeping modes consumes considerable energy and time. This results in an obvious trade‐off between saving energy and provisioning performance guarantees such as end‐to‐end delays. We study the following routing and scheduling problem in a network in which each network element either operates in the full‐rate active mode or the zero‐rate sleeping mode. For a given network and traffic matrix, routing determines the path that each traffic stream traverses. For frame‐based periodic scheduling, a schedule determines the active period per element within each frame and prioritizes packets within each active period. For a line topology, we present a schedule with close‐to‐minimum delay for a minimum active period per element. For an arbitrary topology, we partition the network into a collection of lines and use the near‐optimal schedule along each line. Additional delay is incurred only when a path switches from one line to another. By minimizing the number of switchings via routing, we show a logarithmic approximation for both power consumption and end‐to‐end delays. If routing is given as input, we present two schedules one of which has active period proportional to the traffic load per network element, and the other has active period proportional to the maximum load over all elements. The end‐to‐end delay of the latter is much improved compared to the delay for the former. This demonstrates the trade‐off between power and delay. Finally, we provide simulation results to validate our algorithmic approaches. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

This paper is on homonymous distributed systems where processes are prone to crash failures and have no initial knowledge of the system membership (``homonymous'' means that several processes may have the same identifier). New classes of failure detectors suited to these systems are first defined. Among them, the classes $\HO$ and $\HS$ are introduced that are the homonymous counterparts of the classes $\Omega$ and $\Sigma$, respectively. (Recall that the pair $\langle \Omega, \Sigma\rangle$ defines the weakest failure detector to solve consensus.) Then, the paper shows how $\HO$ and $\HS$ can be implemented in homonymous systems without membership knowledge (under different synchrony requirements). Finally, two algorithms are presented that use these failure detectors to solve consensus in homonymous asynchronous systems where there is no initial knowledge of the membership. One algorithm solves consensus with $\langle \HO, \HS\rangle$, while the other uses only $\HO$, but needs a majority of correct processes. Observe that the systems with unique identifiers and anonymous systems are extreme cases of homonymous systems from which follows that all these results also apply to these systems. Interestingly, the new failure detector class $\HO$ can be implemented with partial synchrony, while the analogous class $\AO$ defined for anonymous systems can not be implemented (even in synchronous systems). Hence, the paper provides us with the first proof showing that consensus can be solved in anonymous systems with only partial synchrony (and a majority of correct processes).

Multi-layer video streaming allows to provide different video qualities to a group of multicast receivers with heterogeneous receive rates. The number of layers received determines the quality of the decoded video stream. For such layered multicast streaming, network coding provides higher capacity than multicast routing. Network coding can be performed within a layer (intra-layer) or across layers (inter-layer), and in general inter-layer coding outperforms intra-layer coding. An optimal solution to a network coded layered multicast problem may require decoding of the network code at interior nodes to extract information to be forwarded. However, decoding consumes resources and introduces delay, which is particularly undesirable at interior nodes (the routers) of the network. In this paper, we thus focus on the inter-layer network coding problem without decoding at interior nodes. We propose a heuristic algorithm for rate allocation and code assignment based on the Edmonds-Karp maximum flow algorithm and perform simulations that show that our algorithm may even outperform other heuristics that do require decoding at interior nodes.

The growth of the Internet has increased the need for scalable congestion control mechanisms in high speed networks. In this context, we propose a rate-based explicit congestion control mechanism with which the sources are provided with the rate at which they can transmit. These rates are computed with a distributed max-min fair algorithm, SLBN. The novelty of SLBN is that it combines two interesting features not simultaneously present in existing proposals: scalability and fast convergence to the max-min fair rates, even under high session churn. SLBN is scalable because routers only maintain a constant amount of state information (only three integer variables per link) and only incur a constant amount of computation per protocol packet, independently of the number of sessions that cross the router. Additionally, SLBN does not require processing any data packet, and it converges independently of sessions' RTT. Finally, by design, the protocol is conservative when assigning rates, even in the presence of high churn, which helps preventing link overshoots in transient periods. We claim that, with all these features, our mechanism is a good candidate to be used in real deployments.

Despite file distribution applications are responsible for a major portion of the current Internet traffic, so far little effort has been dedicated to study file distribution from the point of view of energy efficiency. In this paper, we present the first extensive and detailed theoretical study for the problem of energy efficiency in file distribution. Specifically, we first demonstrate that the general problem of minimizing energy consumption in file distribution is NP-hard. For restricted versions of the problem, we derive tight lower bounds on energy consumption, and we design a family of algorithms that achieve these bounds. Our results prove that through collaborative p2p schemes up to 50% energy savings are achievable with respect to the best available centralized file distribution scheme. Through simulation, we show that even in heterogeneous settings (e.g., considering network congestion, and link variability across hosts) our collaborative algorithms always achieve significant energy savings with respect to the power consumption of centralized file distribution systems.

This work considers Internet-based task computations in which a master process assigns tasks, over the Internet, to rational workers and collect their responses. The objective is for the master to obtain the correct task outcomes. For this purpose we formulate and study the dynamics of evolution of Internet-based master-worker computations through reinforcement learning.

Abstract Random walks have been proven useful in several applications in networks. Some variants of the basic random walk have been devised pursuing a suitable trade‐off between better performance and limited cost. A self‐avoiding random walk (SAW) is one that tries not to revisit nodes, therefore covering the network faster than a random walk. Suggested as a network search mechanism, the performance of the SAW has been analyzed using essentially empirical studies. A strict analytical approach is hard since, unlike the random walk, the SAW is not a Markovian stochastic process. We propose an analytical model to estimate the average search length of a SAW when used to locate a resource in a network. The model considers single or multiple instances of the resource sought and the possible availability of one‐hop replication in the network (nodes know about resources held by their neighbors). The model characterizes networks by their size and degree distribution, without assuming a particular topology. It is, therefore, a mean‐field model, whose applicability to real networks is validated by simulation. Experiments with sets of randomly built regular networks, Erdős–Rényi networks, and scale‐free networks of several sizes and degree averages, with and without one‐hop replication, show that model predictions are very close to simulation results, and allow us to draw conclusions about the applicability of SAWs to network search. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

We study network optimization that considers power minimization as an objective. Studies have shown that mechanisms such as speed scaling can significantly reduce the power consumption of telecommunication networks by matching the consumption of each network element to the amount of processing required for its carried traffic. Most existing research on speed scaling focuses on a single network element in isolation. We aim for a network-wide optimization. Specifically, we study a routing problem with the objective of provisioning guaranteed speed/bandwidth for a given demand matrix while minimizing power consumption. Optimizing the routes critically relies on the characteristic of the speed–power curve$f(s)$, which is how power is consumed as a function of the processing speed$s$. If$f$is superadditive, we show that there is no bounded approximation in general for integral routing, i.e., each traffic demand follows a single path. This contrasts with the well-known logarithmic approximation for subadditive functions. However, for common speed–power curves such as polynomials$f(s) = \mu s^{\alpha}$, we are able to show a constant approximation via a simple scheme of randomized rounding. We also generalize this rounding approach to handle the case in which a nonzero startup cost$\sigma$appears in the speed–power curve, i.e.,$f(s) = \cases{0, & if $s=0$\cr \sigma + \mu s^{\alpha},& if $s>0$.}$We present an$O((\sigma /\mu)^{1/\alpha})$-approximation, and we discuss why coming up with an approximation ratio independent of the startup cost may be hard. Finally, we provide simulation results to validate our algorithmic approaches.

This work, using a game-theoretic approach, considers Internet-based computations, where a master processor assigns, over the Internet, a computational task to a set of untrusted worker processors, and collects their responses. The master must obtain the correct task result, while maximizing its benefit. Building on prior work, we consider a framework where altruistic, malicious, and rational workers co-exist. In addition, we consider the possibility that the communication between the master and the workers is not reliable, and that workers could be unavailable assumptions that are very realistic for Internet-based master-worker computations. Within this framework, we design and analyze two algorithmic mechanisms that provide, when necessary, appropriate incentives to rational workers to act correctly, despite the malicious' workers actions and the unreliability of the network. These mechanisms are then applied to two realistic Internet-based master-worker settings, a SETI-like one and a contractor-based one, such as Amazon's mechanical turk.

The problem of fairly distributing the capacity of a network among a set of sessions has been widely studied. In this problem, each session connects via a single path a source and a destination, and its goal is to maximize its assigned transmission rate (i.e., its throughput). Since the links of the network have limited bandwidths, some criterion has to be defined to fairly distribute their capacity among the sessions. A popular criterion is max-min fairness that, in short, guarantees that each session i gets a rate λisuch that no session s can increase λswithout causing another session s' to end up with a rate λs/s. Many max-min fair algorithms have been proposed, both centralized and distributed. However, to our knowledge, all proposed distributed algorithms require control data being continuously transmitted to recompute the max-min fair rates when needed (because none of them has mechanisms to detect convergence to the max-min fair rates). In this paper we propose B-Neck, a distributed max-min fair algorithm that is also quiescent. This means that, in absence of changes (i.e., session arrivals or departures), once the max min rates have been computed, B-Neck stops generating network traffic. Quiescence is a key design concept of B-Neck, because B-Neck routers are capable of detecting and notifying changes in the convergence conditions of max-min fair rates. As far as we know, B-Neck is the first distributed max-min fair algorithm that does not require a continuous injection of control traffic to compute the rates. The correctness of B-Neck is formally proved, and extensive simulations are conducted. In them, it is shown that B-Neck converges relatively fast and behaves nicely in presence of sessions arriving and departing.

Recent work on shared-resource contention resolution has yielded fruitful results for local area networks and radio networks, although either the solution is suboptimal [2] or a (possibly loose) upper bound on the number of users needs to be known [5]. In this work, we present the first (two) protocols for contention resolution in radio networks that are asymptotically optimal (with high probability), work without collision detection, and do not require information about the number of contenders. In addition to the theoretical analysis, the protocols are evaluated and contrasted with the previous work by extensive simulations.

In this brief announcement we propose B-Neck, a max-min fair distributed algorithm that is also quiescent. As far as we know, B-Neck is the first max-min fair distributed algorithm that does not require a continuous injection of control traffic to compute the rates. When changes occur, affected sessions are asynchronously informed, so they can start the process of computing their new rate (i.e., sessions do not need to poll the network for changes). The correctness of B-Neck is formally proved, and extensive simulations are conducted. In them it is shown that B-Neck converges relatively fast and behaves nicely in presence of sessions arriving and departing.

Energy conservation is drawing increasing attention in data networking. One school of thought believes that a dominant amount of energy saving comes from turning off network elements. The difficulty is that transitioning between the active and sleeping modes consumes considerable energy and time. This results in an obvious trade-off between saving energy and provisioning performance guarantees such as end-to-end delays. We study the following routing and scheduling problem in a network in which each network element either operates in the full-rate active mode or the zero-rate sleeping mode. For a given network and traffic matrix, routing determines the path along which each traffic stream traverses. For frame-based periodic scheduling, a schedule determines the active period per element within each frame and prioritizes packets within each active period. For a line topology, we present a schedule with close-to-minimum delay for a minimum active period per element. For an arbitrary topology, we partition the network into a collection of lines and utilize the near-optimal schedule along each line. Additional delay is incurred only when a path switches from one line to another. By minimizing the number of switchings via routing, we show a logarithmic approximation for both energy consumption and end-to-end delays. If routing is given as input, we present two schedules one of which has active period proportional to the traffic load per network element, and the other proportional to the maximum load over all elements. The end-to-end delay of the latter is much improved compared to the delay for the former. This demonstrates the trade-off between energy and delay.

We study network optimization that considers energy minimization as an objective. Studies have shown that mechanisms such as speed scaling can significantly reduce the power consumption of telecommunication networks by matching the consumption of each network element to the amount of processing required for its carried traffic. Most existing research on speed scaling focuses on a single network element in isolation. We aim for a network-wide optimization. Specifically, we study a routing problem with the objective of provisioning guaranteed speed/bandwidth for a given demand matrix while minimizing energy consumption. Optimizing the routes critically relies on the characteristic of the energy curve $f(s)$, which is how energy is consumed as a function of the processing speed $s$. If $f$ is superadditive, we show that there is no bounded approximation in general for integral routing, i.e., each traffic demand follows a single path. This contrasts with the well-known logarithmic approximation for subadditive functions. However, for common energy curves such as polynomials $f(s) = \mu s^{\alpha}$, we are able to show a constant approximation via a simple scheme of randomized ounding. The scenario is quite different when a non-zero tartup cost $\sigma$ ppears in the energy curve, e.g.\ $f(s) = \left\{ \begin{array}{ll} 0 & \mbox{ if } s=0\\sigma + \mu s^{\alpha}& \mbox{ if } s>0 \end{array}\right.$. For this case a constant approximation is no longer feasible. In fact, for any \alpha>1$, we show an $\Omega(\log^{\frac{1}{4}}N)$ hardness result under a common complexity assumption. Here $N$ is the size of the network.) On the positive side we present $O((\sigma/\mu)^{1/\alpha})$ and $O(K)$ approximations, where $K$ is the number of demands.

We consider Internet-based master-worker computations, where a master processor assigns, across the Internet, a computational task to a set of untrusted worker processors, and collects their responses; examples of such computations are the ¿@home¿ projects such as SETI. Prior work dealing with Internet-based task computations has either considered only rational, or only malicious and altruistic workers. Altruistic workers always return the correct result of the task, malicious workers always return an incorrect result, and rational workers act based on their self-interest. However, in a massive computation platform, such as the Internet, it is expected that all three type of workers coexist. Therefore, in this work we study Internet-based master-worker computations in the presence of Malicious, Altruistic, and Rational workers. A stochastic distribution of the workers over the three types is assumed. Considering all the three types of workers renders a combination of game-theoretic and classical distributed computing approaches to the design of mechanisms for reliable Internet-based computing. Indeed, in this work, such an algorithmic mechanism that makes use of realistic incentives to obtain the correct task result with a parametrized probability is designed. Only when necessary, the incentives are used to force the rational players to a certain equilibrium (which forces the workers to be truthful) that overcomes the attempts of the malicious workers to deceive the master. Finally, the mechanism is analyzed in two realistic Internet-based master-worker applications. This work is an example of how game theory can be used as a tool to formalize and solve a practical Distributed Computing problem such as Internet supercomputing.

The paper proposes a simple protocol that ensures sequential consistency. The protocol assumes that the shared memory abstraction is supported by the local memories of nodes that can communicate only by exchanging messages through reliable channels. Unlike other sequential consistency protocols, the one proposed here does not rely on a strong synchronization mechanism, such as an atomic broadcast primitive or a central node managing a copy of every shared object. From a methodological point of view, the protocol is built incrementally starting from the very definition of sequential consistency. It has the noteworthy property that a process that issues a write operation never has to wait for other processes. Depending on the current local state, most read operations issued also have the same property.

Considering an asynchronous system made up of n processes and where up to t of them can crash, finding the weakest assumption that such a system has to satisfy for a common leader to be eventually elected is one of the holy grail quests of fault-tolerant asynchronous computing. This paper is a step in that direction. It has two contributions. Considering a simple and general asynchronous system model where processes generate asynchronous pulses during which they send and receive messages, it first introduces an additional assumption that allows to elect an eventual leader in all the runs that satisfy that assumption. That assumption is captured by the notion of asynchronous intermittent rotating t-star. An x-star is made up of one process p (the center of the star) plus a sequence of sets of x processes (the successive points of the star), which satisfies some properties. Intuitively, the intermittent rotating t-star assumption means that there are a process p, a subset of pulse numbers pn, and associated sets of processes Q(pn) such that each process of Q(pn) receives from p a message sent in pulse pn in a timely manner or among the first (n-t) messages tagged pn it ever receives. The t-star is called rotating because the set Q(pn) is allowed to change with pn; it is intermittent because it can disappear during finite periods; it is asynchronous because the points of a star are not required to be simultaneously at the same pulse. (This assumption combines and generalizes several synchrony and time-free assumptions that have been previously proposed to elect an eventual leader, e.g., eventual t-source, eventual t-moving source, and message pattern assumption.) The second contribution of the paper is an algorithm that eventually elects a common leader in the systems that satisfy the asynchronous intermittent rotating t-star assumption. This algorithm enjoys, among others, two noteworthy properties. First, from a design point of view, it is simple. Second, from a cost point of view, only the pulse numbers increase without bound. This means that, even in infinite executions, be links timely or not (or have the corresponding sender crashed or not), all the other local variables (including the timers) and message fields have a finite domain.

In the k-set agreement task, n processes propose values, and have to decide on at most k of these values. In particular, consensus is 1-set agreement. In PODC 2008 Zieliński showed that the anti-Ω failure detector is necessary and sufficient to solve (n − 1)-set agreement in an asynchronous read/write shared memory system where at most n − 1 processes can fail by crashing.

In this paper, we study algebraic aggregate computations in Sensor Networks. The main contribution is the presentation of an early-stopping protocol that computes the average function under a harsh model of the conditions under which sensor nodes operate. This protocol is shown to be time-optimal in presence of unfrequent failures. The approach followed saves time and energy by relying the computation on a small network of delegate nodes that can be rebuilt fast in case of node failures and communicate using a collision-free schedule. Delegate nodes run simultaneously two protocols, namely, a collection/dissemination tree-based algorithm, which is shown to be optimal, and a mass-distribution algorithm. Both algorithms are analyzed under a model where the frequency of failures is a parameter. Other aggregate computation algorithms can be easily derived from this protocol. To the best of our knowledge, this is the first optimal early-stopping algorithm for aggregate computations in Sensor Networks.

In this work, using a game-theoretic approach, cost-sensitive mechanisms that lead to reliable Internet-based computing are designed. In particular, we consider Internet-based master-worker computations, where a master processor assigns, across the Internet, a computational task to a set of potentially untrusted worker processors and collects their responses. Several game-theoretic models that capture the nature of the problem are analyzed and mechanisms that, for each given set of cost and system parameters, achieve high reliability are designed. Additionally, two specific realistic system scenarios are studied. These scenarios are a system of volunteering computing like SETI, and a company that buys computing cycles from Internet computers and sells them to its customers in the form of a task-computation service. Notably, under certain conditions, non redundant allocation yields the best trade-off between cost and reliability.

This paper considers the problem of electing an eventual leader in an asynchronous shared memory system. While this problem has received a lot of attention in message- passing systems, very few solutions have been proposed for shared memory systems. As an eventual leader cannot be elected in a pure asynchronous system prone to process crashes, the paper first proposes to enrich the asynchronous system model with an additional assumption. That assumption, denoted AWB, requires that after some time (1) there is a process whose write accesses to some shared variables are timely, and (2) the timers of the other processes are asymptotically well-behaved. The asymptotically well-behaved timer notion is a new notion that generalizes and weakens the traditional notion of timers whose durations are required to monotonically increase when the values they are set to increase. Then, the paper presents two A WB-based algorithms that elect an eventual leader. Both algorithms are independent of the value of t (the maximal number of processes that may crash). The first algorithm enjoys the following noteworthy properties: after some time only the elected leader has to write the shared memory, and all but one shared variables have a bounded domain, be the execution finite or infinite. This algorithm is consequently optimal with respect to the number of processes that have to write the shared memory. The second algorithm enjoys the following property: all the shared variables have a bounded domain. This is obtained at the following additional price: all the processes are required to forever write the shared memory. A theorem is proved which states that this price has to be paid by any algorithm that elects an eventual leader in a bounded shared memory model. This second algorithm is consequently optimal with respect to the number of processes that have to write in such a constrained memory model. In a very interesting way, these algorithms show an inherent tradeoff relating the number of processes that have to write the shared memory and the bounded/unbounded attribute of that memory.

Peer to peer (P2P) systems are moving from application specific architectures to a generic service oriented design philosophy. This raises interesting problems in connection with providing useful P2P middleware services capable of dealing with resource assignment and management in a large-scale, heterogeneous and unreliable environment. The 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 and that are also relatively homogeneous with respect to that resource. In this paper we propose two gossip-based algorithms to solve the distributed slicing problem. The first algorithm speeds up an existing algorithm sorting a set of uniform random numbers. The second algorithm statistically approximates the rank of nodes in the ordering. The scalability, efficiency and resilience to dynamics of both algorithms rely on their gossip-based models. These algorithms are proved viable theoretically and experimentally.

In this paper we generalize the Continuous Adversarial Queuing Theory (CAQT) model [5] by considering the possibility that the router clocks in the network are not synchronized. Clearly, this new extension to the model only affects those scheduling policies that use some form of timing. First, if all clocks run at the same speed, maintaining constant differences, we show that all universally stable policies in CAQT that use the injection time and the remaining path to schedule packets remain universally stable. These policies include, for instance, Shortest in System (SIS) and Longest in System (LIS). Then, if clock differences can vary over time, but difference is bounded, we show the universal stability of SIS and a family of policies related to LIS. The bounds we obtain in this case depend on the maximum difference between clocks. We then present a new policy that we call Longest in Queues (LIQ), which gives priority to the packet that has been waiting the longest in edge queues. This policy is universally stable and, if clocks maintain constant differences, the bounds do not depend on them. To finish, we provide with simulation results that compare the behavior of some of these protocols in a network with stochastic injection of packets.

While electing an eventual common leader, despite process crashes, in a shared memory system where the processes communicate only by reading and writing shared registers is possible when the processes progress synchronously, this problem becomes impossible to solve as soon as the processes can progress in a fully asynchronous way. So, an important problem consists in finding additional behavioral assumptions that are, at the same time, "as weak as possible" (in order they are practically always satisfied), and "strong enough" in order to allow implementing an eventual leader service despite the net effect of asynchrony and failures. This paper focuses on this dilemma. More explicitly, it investigates a timing assumption that allows implementing an eventual leader in presence of partial asynchrony and process crashes. The proposed timing assumptions are particularly weak. They are the following: after some time (i) there is a process that behaves synchronously, and (ii) (t - f) other processes have timers that work correctly (t is the maximal number of processes that may crash, and f the actual number of process crashes; a timer works incorrectly when it expires too early with respect to the value it has been set). Then, the paper proposes a t-resilient protocol that elects an eventual common leader in any shared memory system that satisfies the previous assumption. Interestingly, this protocol is based on simple design principles.

No abstract available.

This paper considers the eventual leader election problem in asynchronous message-passing systems where an arbitrary number t of processes can crash (t

In this paper we explore the minimal system requirements to implement unreliable failure detectors. We first consider systems formed by lossy asynchronous and eventually timely links. On these systems we define two properties, the weak property and the strong property, depending on whether all correct processes can be reached with links that are not lossy asynchronous from one or from all correct processes, respectively. We present necessary conditions based on these properties. We show that there is no algorithm that implements diamS, Omega, nor S (resp. diamP nor P) if we allow one single failure in a system that, when all processes are correct, does not satisfy the weak (resp. strong) property. Then, we propose an algorithm that implements diamP if the strong property is satisfied, and diamS (and Omega with an additional assumption) if only the weak property is satisfied. For systems formed by synchronous and lossy asynchronous links only, we propose another algorithm that implements detector class P4if the strong property is satisfied, and implements a new detector class S1(and Omega with an additional assumption) if only the weak property is satisfied

In this work we consider a distributed system formed by a master processor and a collection of n processors (workers) that can execute tasks; worker processors are untrusted and might act maliciously. The master assigns tasks to workers to be executed. Each task returns a binary value, and we want the master to accept only correct values with high probability. Furthermore, we assume that the service provided by the workers is not free; for each task that a worker is assigned, the master is charged with a work-unit. Therefore, considering a single task assigned to several workers, our goal is to have the master computer to accept the correct value of the task with high probability, with the smallest possible amount of work (number of workers the master assigns the task). We explore two ways of bounding the number of faulty processors: (a) we consider a fixed bound f < n/2 on the maximum number of workers that may fail, and (b) a probability p < 1/2 of any processor to be faulty (all processors are faulty with probability p, independently of the rest of processors). Our work demonstrates that it is possible to obtain high probability of correct acceptance with low work. In particular, by considering both mechanisms of bounding the number of malicious workers, we first show lower bounds on the minimum amount of (expected) work required, so that any algorithm accepts the correct value with probability of success 1 - epsiv, where epsiv Lt 1 (e.g., 1/n). Then we develop and analyze two algorithms, each using a different decision strategy, and show that both algorithms obtain the same probability of success 1 - epsiv, and in doing so, they require similar upper bounds on the (expected) work. Furthermore, under certain conditions, these upper bounds are asymptotically optimal with respect to our lower bounds

Autonomic communications seek to improve the ability of network and services to cope with unpredicted change, including changes in topology, load, task, the physical and logical characteristics of the networks that can be accessed, and so forth. Broad-ranging autonomic solutions require designers to account for a range of end-to-end issues affecting programming models, network and contextual modeling and reasoning, decentralised algorithms, trust acquisition and maintenance---issues whose solutions may draw on approaches and results from a surprisingly broad range of disciplines. We survey the current state of autonomic communications research and identify significant emerging trends and techniques.

In this paper we analyze a novel paradigm of reliable communications which is not based on the traditional timeout-and-retransmit mechanism of TCP. Our approach, which we call FBP (fountain based protocol), consists on using a digital fountain encoding which guarantees that duplicate packets are not possible. Using game theory, we analyze the behavior of TCP and FBP in the presence of congestion. We show that hosts using TCP have an incentive to switch to an FBP approach obtaining a higher throughput. Furthermore, we also show that a Nash equilibrium takes place when all hosts use FBP. At this equilibrium, the performance of the network is similar to the performance obtained when all hosts comply with TCP.

No abstract available.

We study routing and scheduling in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is admissible if no link in the network is overloaded. We present the first on-line routing algorithm that finds a set of admissible paths whenever this is feasible. Our algorithm calculates a path for each packet as soon as it is injected at its source using a simple shortest path computation. The length of a link reflects its current congestion. We also show how our algorithm can be implemented under today's Internet routing paradigms.When the paths are known (either given by the adversary or computed as above), our goal is to schedule the packets along the given paths so that the packets experience small end-to-end delays. The best previous delay bounds for deterministic and distributed scheduling protocols were exponential in the path length. In this article, we present the first deterministic and distributed scheduling protocol that guarantees a polynomial end-to-end delay for every packet.Finally, we discuss the effects of combining routing with scheduling. We first show that some unstable scheduling protocols remain unstable no matter how the paths are chosen. However, the freedom to choose paths can make a difference. For example, we show that a ring with parallel links is stable for all greedy scheduling protocols if paths are chosen intelligently, whereas this is not the case if the adversary specifies the paths.

Abstract In this article, we propose several variations of the adversarial queueing model and address stability issues of networks and protocols in those proposed models. The first such variation is thepriority model, which is directed at static network topologies and takes into account the case in which packets can have different priorities. Those priorities are assigned by an adversary at injection time. A second variation, thevariable priority model, is an extension of the priority model in which the adversary may dynamically change the priority of packets at each time step. Two more variations, namely thefailure modeland thereliable model, are proposed to cope with dynamic networks. In the failure and reliable models the adversary controls, under different constraints, the failures that the links of the topology might suffer. Concerning stability of networks in the proposed adversarial models, we show that the set ofuniversally stablenetworks in the adversarial model remains the same in the priority, variable priority, failure, and reliable models. From the point of view of protocols (or queueing policies), we show that several protocols that are universally stable in the adversarial queueing model remain so in the priority, failure, and reliable models. However, we show that thelongest‐in‐system(LIS) protocol, which is universally stable in the adversarial queueing model, is not universally stable in any of the other models we propose. Moreover, we show that no queueing policy is universally stable in the variable priority model. Finally, we analyze the problem of deciding stability of a given network under a fixed protocol. We provide a characterization of the networks that are stable underfirst‐in‐first‐out(FIFO) and LIS in the failure model (and therefore in the reliable and priority models). This characterization allows us to show that the stability problem under FIFO and LIS in the failure model can be solved in polynomial time. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 23–35 2005

A concurrent object is an object that can be concurrently accessed by several processes. Sequential consistency is a consistency criterion for such objects. Informally, it states that a multiprocess program executes correctly if its results could have been produced by executing that program on a single processor system. (Sequential consistency is weaker than atomic consistency -the usual consistency criterion- as it does not refer to real-time.) The paper proposes a simple protocol that ensures sequential consistency when the shared memory abstraction is supported by the local memories of nodes that can communicate only by exchanging messages through reliable channels. Differently from other sequential consistency protocols, the proposed protocol does not rely on a strong synchronization mechanism such as an atomic broadcast primitive or a central node managing a copy of every shared object. From a methodological point of view, the protocol is built incrementally starting from the very definition of sequential consistency. It lies the noteworthy property of providing fast writes operations (i.e., a process has never to wait when it writes a new value in a shared object). According to the current local state, some read operations can also be fast. An experimental evaluation of the protocol is also presented. The proposed protocol could be used to manage Web page caching.

Unreliable failure detectors were proposed by Chandra and Toueg as mechanisms that provide information about process failures. Chandra and Toueg defined eight classes of failure detectors, depending on how accurate this information is, and presented an algorithm implementing a failure detector of one of these classes in a partially synchronous system. This algorithm is based on all-to-all communication and periodically exchanges a number of messages that is quadratic on the number of processes. We study the implementability of different classes of failure detectors in several models of partial synchrony. We first show that no failure detector with perpetual accuracy (namely, P, Q, S, and W) can be implemented in these models in systems with even a single failure. We also show that, in these models of partial synchrony, it is necessary a majority of correct processes to implement a failure detector of the class /spl theta/ proposed by Aguilera et al. Then, we present a family of distributed algorithms that implement the four classes of unreliable failure detectors with eventual accuracy (namely, /spl diams/P, /spl diams/Q, /spl diams/S, and /spl diams/W). Our algorithms are based on a logical ring arrangement of the processes, which defines the monitoring and failure information propagation pattern. The resulting algorithms periodically exchange at most a linear number of messages.

We study routing and scheduling in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is admissible if no link in the network is overloaded. We present the first on-line routing algorithm that finds a set of admissible paths whenever this is feasible. Our algorithm calculates a path for each packet as soon as it is injected at its source using a simple shortest path computation. The length of a link reflects its current congestion. We also show how our algorithm can be implemented under today's Internet routing paradigms. When the paths are known (either given by the adversary or computed as above) our goal is to schedule the packets along the given paths so that the packets experience small end-to-end delays. The best previous delay bounds for deterministic and distributed scheduling protocols were exponential in the path length. In this paper we present the first deterministic and distributed scheduling protocol that guarantees a polynomial end-to-end delay for every packet. Finally, we discuss the effects of combining routing with scheduling. We first show that some, unstable scheduling protocols remain unstable no matter how the paths are chosen. However, the freedom to choose paths can make a difference. For example, we show that a ring with parallel links is stable for all greedy scheduling protocols if paths are chosen intelligently, whereas this is not the case if the adversary specifies the paths.

The concept of unreliable failure detecto was introduced by Chandra and Toueg [2] as a mechanism that provides (possibly incorrect) information about process failures. This mechanism has been used to solve different problems in async hronous systems, in particular the Consensus problem.

In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We focus on a basic adversarial model of packet arrival and path determination for which the time-averaged arrival rate of packets requiring the use of any edge is limited to be less than 1. This model can reflect the behavior of connection-oriented networks with transient connections (such as ATM networks) as well as connectionless networks (such as the Internet). We concentrate on greedy (also known as work-conserving) contention-resolution protocols. A crucial issue that arises in such a setting is that of stability —will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? We study the universal stability of network (i.e., stability under all greedy protocols) and universal stability of protocols (i.e., stability in all networks). Once the stability of a system is granted, we focus on the two main parameters that characterize its performance: maximum queue size required and maximum end-to-end delay experienced by any packet. Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n -node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n ). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size and polynomial delay. Our results resolve several questions posed by Borodin et al., and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

A large amount of work has been invested in devising algorithms to implement distributed shared memory (DSM) systems under different consistency models. However, to our knowledge, the possibility of interconnecting DSM systems with simple protocols and the consistency of the resulting system has never been studied. With this paper, we start a series of works on the properties of the interconnection of DSM systems, which tries to fill this void.

Unreliable failure detectors were introduced by Chandra and Toueg [2] as a mechanism that provides (possibly incorrect) information about process failures. They showed how unreliable failure detectors can be used to solve the Consensus problem in asynchronous systems. They also showed in [1] that one of the classes of failure detectors they defined, namely Eventually Strong (⋄S), is the weakest class allowing to solve Consensus1.

The concept of unreliable failure detector was introduced by T.D. Chandra and S. Toueg (1996) as a mechanism that provides information about process failures. Depending on the properties which the failure detectors guarantee, they proposed a taxonomy of failure detectors. It has been shown that one of the classes of this taxonomy, namely Eventually Strong (/spl nabla/S), is the weakest class allowing a solution of the Consensus problem. The authors present a new algorithm implementing /spl nabla/S. Our algorithm guarantees that eventually all the correct processes agree on a common correct process. This property trivially allows us to provide the accuracy and completeness properties required by /spl nabla/S. We show then that our algorithm is better than any other proposed implementation of /spl nabla/S in terms of the number of messages and the total amount of information periodically sent. In particular, previous algorithms require periodic exchange of at least a quadratic amount of information, while ours only requires O(n log n) (where n is the number of processes). However, we also propose a new measure to evaluate the efficiency of this kind of algorithm, the eventual monitoring degree, which does not rely on a periodic behavior and expresses the degree of processing required by the algorithms better. We show that the runs of our algorithm have optimal eventual monitoring degree.

A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support real-time traffic such as voice and video. The most critical performance parameter to bound is the delay experienced by a packet as it travels from its source to its destination. We study dynamic routing in a connection-oriented packet-switching network. We consider a network with arbitrary topology on which a set of sessions is defined. For each session i, packets are injected at a rate r i to follow a predetermined path of length d i . Due to limited bandwidth, only one packet at a time may advance on an edge (link). Session paths may overlap subject to the constraint that the total rate of sessions using any particular edge is at most $1-\varepsilon$ for any constant $\varepsilon \in (0,1)$. We address the problem of scheduling the sessions at each switch, so as to minimize worst-case packet delay and queue buildup at the switches. We show the existence of a periodic schedule that achieves a delay bound of O(1/r i +d i ) with only constant-size queues at the switches. This bound is asymptotically optimal for periodic schedules. A consequence of this result is an asymptotically optimal schedule for the static routing problem, wherein all packets are present at the outset. We obtain a delay bound of O(c i + d i ) for packets on path P i , where d i is the number of edges in P i and c i is the maximum congestion along edges in P i . This improves upon the previous known bound of O(c + d), where d = max i d i and c = max i c i . We also present a simple distributed algorithm that, with high probability, delivers every session-i packet to its destination within O(1/r i +d i \log(m/r min )) steps of its injection, where r min is the minimum session rate and m is the number of edges in the network. Our results can be generalized to (leaky-bucket constrained) bursty traffic, where session i tolerates a burst size of b i . In this case, our delay bounds become O(b i /r i + d i ) and O(b i /r i +d i \log(m/r min )), respectively.

In this paper we study the isolation of five work-conserving scheduling policies in connection-oriented packet-switched networks. We say that a policy has good isolation if its performance (end-to-end packet delay here) is not influenced by the session configuration. Here we study, by simulation on a very simple setup, how the average packet delay changes in one session when the length or number of the rest of sessions change (while the total rate at each link is preserved). In our study we consider two well-known scheduling policies, namely weighted fair queueing (WFQ) and FIFO, a recently proposed label-based policy S-CEDF, and two more label-based policies we introduce here for connection-oriented networks. We observe that the performance of WFQ and FIFO tends to significantly vary under changing environments, while the label-based policies tend to be more stable. In particular, we observe that the end-to-end delay of WFQ and FIFO decreases when the length of the sessions competing with one given increases. When the environment changes by increasing the number of sessions, the delay under WFQ tends to decrease with the divisions, while the delay under FIFO tends to increase. Further work is needed to analyze these results, and to obtain empirical and analytical isolation bounds for a variety of policies.

Article The power of a pebble: exploring and mapping directed graphs Share on Authors: Michael A. Bender Division of Engineering and Applied Sciences, Harvard University, Cambridge, MA Division of Engineering and Applied Sciences, Harvard University, Cambridge, MAView Profile , Antonio Fernández Dpto de Arquitectura y Tecnología de Computadores, Universidad Politécnica de Madrid and Laboratory for Computer Science, MIT Dpto de Arquitectura y Tecnología de Computadores, Universidad Politécnica de Madrid and Laboratory for Computer Science, MITView Profile , Dana Ron Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MA Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MAView Profile , Amit Sahai Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MA Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MAView Profile , Salil Vadhan Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MA Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MAView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 269–278https://doi.org/10.1145/276698.276759Online:23 May 1998Publication History 103citation603DownloadsMetricsTotal Citations103Total Downloads603Last 12 Months10Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support read-time traffic such as voice and video. The most critical performance parameter to bound is the delay experienced by a packet as it travels from its source to its destination. We study dynamic routing in a connection-oriented packet-switching network. We consider a network with arbitrary topology on which a set of sessions is defined. For each session i, packets are injected at a rate r/sub i/ to follow a predetermined path of length d/sub i/. Due to limited bandwidth, only one packet at a time may advance on an edge. Session paths may overlap subject to the constraint that the total rate of sessions using any particular edge is less than 1. We address the problem of scheduling the sessions at each switch, so as to minimize worst-case packet delay and queue buildup at the switches. We show the existence of an asymptotically-optimal schedule that achieves a delay bound of O(1/r/sub i/+d/sub i/) with only constant-size queues at the switches. We also present a simple distributed algorithm that, with high probability, delivers every session-i packet to its destination within O(1/r/sub i/+d/sub i/ log(m/r/sub min/)) steps of its injection, where r/sub min/ is the minimum session rate, and m is the number of edges in the network. Our results can be generalized to (leaky-bucket constrained) bursty traffic, where session i tolerates a burst size of b/sub i/. In this case, our delay bounds become O(b/sub i//r/sub i/+d/sub i/) and O(b/sub i//r/sub i/+d/sub i/ log(m/r/sub min/)), respectively.

In this paper, we develop generalized methods to layout homogeneous product networks with any number of dimensions, and analyze their VLSI complexity by deriving upper and lower bounds on the area and maximum wire length. In the literature, lower bounds are generally obtained by computing lower bounds on the bisection width or the crossing number of the network being laid out. In this paper, we define a new measure that we call "maximal congestion", that can be used to obtain both the bisection width and the crossing number, thereby unifying the two approaches. Upper bounds are traditionally obtained by constructing layouts based on separators or bifurcators. Both methods have the basic limitation that they are applicable only for graphs with bounded vertex degree. The separators approach generally yields good layouts when good separators can be found, but it is difficult to find a good separator for an arbitrary graph. The bifurcators approach is easier to apply, but it generally yields larger area and wire lengths. We show how to obtain "strong separators" as well as bifurcators for any homogeneous product network, as long as the factor graph has bounded vertex degree. We illustrate application of both methods to layout a number of interesting product networks. Furthermore, we introduce a new layout method for product networks based on the combination of collinear layouts. This method is more powerful than the two methods above because it is applicable even when the factor graph has unbounded vertex degree. It also yields smaller area than the earlier methods. In fact, our method has led to the optimal area for all of the homogeneous product networks we considered in this paper with one exception, which is very close to optimal. In regards to wire lengths, the results obtained by our method turned out to be the best of the three methods for all the examples we considered, again subject to one (and the same) exception. We give an extensive variety of such examples.

We generalize the well-known odd-even merge sorting algorithm, originally due to Batcher (1968), and show how this generalized algorithm can be applied to sorting on product networks. If G is an arbitrary factor graph with N nodes, its r-dimensional product contains N/sup r/ nodes. Our algorithm sorts N/sup r/ keys stored in the r-dimensional product of G in O(r/sup r/F(N)) time, where F(N) depends on G. We show that, for any factor graph G, F(N) is, at most, O(N), establishing an upper bound of O(r/sup 2/ N) for the time complexity of sorting N/sup r/ keys on any product network. For product networks with bounded r(e.g. for grids), this leads to the asymptotic complexity of O(N) to sort N/sup r/ keys, which is optimal for several instances of product networks. There are factor graphs for which F(N)=O(log/sup 2/ N), which leads to the asymptotic running time of O(log/sup 2/ N) to sort N/sup r/ keys. For networks with bounded N (e.g. in the hypercube N=2, fixed), the asymptotic complexity becomes O(r/sup 2/). We show how to apply the algorithm to several cases of well-known product networks, as well as others introduced recently. We compare the performance of our algorithm to well-known algorithms developed specifically for these networks, as well as others. The result of these comparisons led us to conjecture that the proposed algorithm is probably the best deterministic algorithm that can be found in terms of the low asymptotic complexity with a small constant.

In this paper we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic adversarial model of packet generation and path determination for which the time-averaged injection rate of packets requiring the use of any edge is limited to be less than 1. A crucial issue that arises in such a setting is that of stability-will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly-used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n-node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size. Our results resolve several questions posed by Borodin et al. and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

The grid and the mesh of trees (or MOT) are among the best-known parallel architectures in the literature. Both of them enjoy efficient VLSI layouts, simplicity of topology, and a large number of parallel algorithms that can efficiently execute on them. One drawback of these architectures is that algorithms that perform best on one of them do not perform very well on the other. Thus there is a gap between the algorithmic capabilities of these two architectures. We propose a new class of parallel architectures, called the mesh-connected trees (or MCT) that can execute grid algorithms as efficiently as the grid, and MOT algorithms as efficiently as the MOT, up to a constant amount of slowdown. In particular, the MCT topology contains the MOT as a subgraph and emulates the grid via embedding with dilation 3 and congestion two. This significant amount of computational versatility offered by the MCT comes at no additional VLSI area cost over these earlier networks. Many topological, routing, and embedding properties analyzed here suggest that the MCT architecture is also a serious competitor for the hypercube. In fact, while the MCT is much simpler and cheaper than the hypercube, for all the algorithms we developed, the running time complexity on the MCT matches those of well known hypercube algorithms. We also present an interesting variant of the MCT architecture that admits both the MOT and the torus as its subgraphs. While most of the discussion in this paper is focused on the MCT architecture itself, these analyses can be easily extended to the variant of the MCT presented here.

Analyzes some general properties of product networks that are pertinent to parallel architectures and then focuses on three case studies. These are products of complete binary trees, shuffle-exchange and de Bruijn networks. It is shown that all of these are powerful architectures for parallel computation, as evidenced by their ability to efficiently emulate numerous other architectures. In particular, r-dimensional grids and r-dimensional meshes of trees can be embedded efficiently in products of these graphs, i.e. either as a subgraph or with small constant dilation and congestion. In addition, the shuffle-exchange network can be embedded in an r-dimensional product of shuffle-exchange networks with dilation cost 2r and congestion cost 2. Similarly, the de Bruijn network can be embedded in an r-dimensional product of de Bruijn networks with dilation cost r and congestion cost 4. Moreover, it is well known that shuffle-exchange and de Bruijn graphs can emulate the hypercube with a small constant slowdown for "normal" algorithms. This means that their product versions can also emulate these hypercube algorithms with constant slowdown. Conclusions include a discussion of many open research areas.>

Recently, the mesh connected trees (MCT) network has been proposed as a possible architecture for parallel computers. MCT networks are obtained by combining complete binary trees using the cross product operation. This paper focuses on structural, embedding, routing, and layout properties of the MCT networks. We show that MCT networks are computationally more powerful than grids and complete binary trees, and at least as powerful as meshes of trees (MOT). Analysis of VLSI complexity shows thai the additional power is obtained without asymptotically increasing the layout area with respect to the grid of at least 3 dimensions or to the MOT of any number of dimensions. A variation of the basic architecture with same maximum vertex degree and same asymptotic area complexity is also investigated. This variation contains the torus as a subgraph as well as the MOT, further increasing the computational power of the basic architecture. These results suggest that the basic MCT network and its variant are suitable architectures for a large class of massively parallel computations.