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.

• This work provides the first self-stabilizing solution for the problem of constructing atomic snapshot objects, which can recover after the last occurrence of a transient fault (as well as node failures). • Our contribution is obtained via code transformation of earlier crash-tolerant algorithms for asynchronous message-passing systems prone to node failures. • This journal version extends our earlier conference papers by presenting the complete proofs for the proposed algorithms, and a completely new upper-bound on the operation completion time. A snapshot object simulates the behavior of an array of single-writer/multi-reader shared registers that can be read atomically. In 2018, Delporte-Gallet et al. proposed two fault-tolerant algorithms for snapshot objects in asynchronous crash-prone message-passing systems. Their first algorithm is non-blocking ; it allows snapshot operations to complete once all write operations have ceased. Their second algorithm allows snapshot operations to always terminate independently of write operations. The fault model of Delporte-Gallet et al. considers node failures (crashes). We aim at the design of even more robust snapshot objects. We do so through the lenses of self-stabilization —a very strong notion of fault-tolerance. In addition to Delporte-Gallet et al. ’s fault model, our self-stabilizing algorithms can recover after the occurrence of transient faults ; these faults represent arbitrary violations of the assumptions according to which the system was designed to operate (as long as the code stays intact). In particular, in this work, we propose self-stabilizing variations of Delporte-Gallet et al. ’s non-blocking algorithm and always-terminating algorithm. Our algorithms have similar communication costs to the ones by Delporte-Gallet et al. yet they eventually recover from the last occurrence of a transient fault. The main differences are that our proposal considers repeated gossiping of O ( ν ) bit messages, ν being the number of bits for encoding the object, and deals with bounded space (which is a prerequisite for self-stabilization). This facilitates recovery of the registers and sequence numbers after the occurrence of the last transient fault by guaranteeing consistency. We use Lamport’s happened-before relation to bound, when possible, the completion time of write and snapshot operations.

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.

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.

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.

ARES is a modular framework, designed to implement dynamic, reconfigurable, fault-tolerant, read/write and strongly consistent distributed shared memory objects. Recent enhancements of the framework have realized the efficient implementation of large objects, by introducing versioning and data striping techniques. In this work, we identify performance bottlenecks of the ARES's variants by utilizing distributed tracing, a popular technique for monitoring and profiling distributed systems. We then propose optimizations across all versions of Ares,aiming in overcoming the identified flaws, while preserving correctness. We refer to the optimized version of Aresas AresIi, which now features a piggyback mechanism, a garbage collection mechanism, and a batching reconfiguration technique for improving the performance and storage efficiency of the original Ares.We rigorously prove the correctness of AresIi, and we demonstrate the performance improvements by an experimental comparison (via distributed tracing) of the AresIi variants with their original counterparts.

The limitations of the networks of Internet of Things (IoTs) and Wireless Sensor Networks (WSNs) in terms of computational power, memory and connectivity give rise to several issues that need to be tackled, mostly dynamically, to achieve their tasks. Definitively, a critical factor for the proper operation of these networks is to maintain the connectivity between the nodes, especially in a wireless mesh setting, where communication is performed in hop-by-hop fashion. A method that gains significant research interest for tackling the aforementioned issues is the employment of mobile nodes or as they are frequently called, mobile elements. In this work, we propose a scheme that utilizes carriers to transport mobile nodes to the required points in the network. We provide both a high level description of the concept and also a detailed algorithmic solution. The proposed solution is evaluated through a case study, where hot-spots are created due to congestion in the network and mobile elements are being used to resolve the problem. The experimental results demonstrate that the proposed algorithm can effectively restore the network operation. We believe that our proposed approach can be used to solve similar types of problems.

Data availability is one of the most important features in distributed storage systems, made possible by data replication. Nowadays data are generated rapidly and developing efficient, scalable and reliable storage systems has become one of the major challenges for high performance computing. In this work, we develop and prove correct a dynamic, robust and strongly consistent distributed shared memory suitable for handling large objects (such as files) and utilizing erasure coding. We do so by integrating an Adaptive, Reconfigurable, Atomic memory framework, called Ares, with the CoBFS framework, which relies on a block fragmentation technique to handle large objects. With the addition of Ares, we also enable the use of an erasure-coded algorithm to further split the data and to potentially improve storage efficiency at the replica servers and operation latency. Our development is complemented with an in-depth experimental evaluation on the Emulab and AWS EC2 testbeds, illustrating the benefits of our approach, as well as interesting tradeoffs.

As Wireless Sensor Networks (WSNs) and Internet of Things (IoTs) applications evolve, the need for robust protocols, capable to guarantee extended lifetime and high throughput, increases. Mobility of devices either in terms of mobile nodes or mobile sinks is a promising solution that can assist, for example, topology control and congestion mitigation. Such factors significantly contribute to the extension of the lifetime and the throughput of wireless ad-hoc networks. In this work we review and classify algorithms that introduce the characteristic of mobility in WSNs. We consider WSNs to be both a subset and a predecessor to IoT, and thus, consider that existing mobility solutions can be adapted for use in IoT. Finally, open problems and future directions are discussed that include wireless power transfer, network fault detection, and real-world/testbed evaluation of algorithms.

The operation of Internet of Things (IoT) networks and Wireless Sensor Networks (WSN) is often disrupted by a number of problems, such as path disconnections, network segmentations, node faults, security attacks, etc. A method that gains momentum in resolving some of those issues is the use of mobile nodes or nodes deployed by mobile robots. The use of mobile elements essentially increases the resources and the capacity of the network. In this work, we propose a scheme that utilizes mobile nodes for the creation of alternative paths from source to sink by also accounting the energy levels of the nodes as a contributing factor regarding the creation of alternative paths. We offer both a high level description of the concept and also a detailed algorithmic solution. The evaluation of the solution was performed in a case study of resolving congestion in the network. Results have shown that the proposed algorithm can significantly contribute to the alleviation of the problem of congestion in IoT and WSNs and can easily be used for other types of network problems.

Congestion control and avoidance in Wireless Sensor Networks (WSNs) is a subject that has attracted a lot of research attention in the last decade. Besides rate and resource control, the utilization of mobile nodes has also been suggested as a way to control congestion. In this work, we present a Mobile Congestion Control (MobileCC) algorithm with two variations, to assist existing congestion control algorithms in facing congestion in WSNs. The first variation employs mobile nodes that create locally-significant alternative paths leading to the sink. The second variation employs mobile nodes that create completely individual (disjoint) paths to the sink. Simulation results show that both variations can significantly contribute to the alleviation of congestion in WSNs.

A snapshot object simulates the behavior of an array of single-writer/multi-reader shared registers that can be read atomically. Delporte-Gallet et al. proposed two fault-tolerant algorithms for snapshot objects in asynchronous crash-prone message-passing systems. Their first algorithm is non-blocking; it allows snapshot operations to terminate once all write operations had ceased. It uses O(n) messages of O(n v) bits, where n is the number of nodes and v is the number of bits it takes to represent the object. Their second algorithm allows snapshot operations to always terminate independently of write operations. It incurs O(n^2) messages. The fault model of Delporte-Gallet et al. considers node failures (crashes). We aim at the design of even more robust snapshot objects. We do so through the lenses of self-stabilization---a very strong notion of fault-tolerance. In addition to Delporte-Gallet et al.'s fault model, a self-stabilizing algorithm can recover after the occurrence of transient faults; these faults represent arbitrary violations of the assumptions according to which the system was designed to operate (as long as the code stays intact). In particular, in this work, we propose self-stabilizing variations of Delporte-Gallet et al.'s non-blocking algorithm and always-terminating algorithm. Our algorithms have similar communication costs to the ones by Delporte-Gallet et al. and O(1) recovery time (in terms of asynchronous cycles) from transient faults. The main differences are that our proposal considers repeated gossiping of O(v) bits messages and deals with bounded space, which is a prerequisite for self-stabilization.

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.

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.

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.

With the end of Moore's Law in sight, parallelism became the main means for speeding up computationally intensive applications, especially in the cases where large collections of tasks need to be performed. Network supercomputing -- taking advantage of very large numbers of computers in a distributed environment is an effective approach to massive parallelism that harnesses the processing power inherent in large networked settings. In such settings, processor failures are no longer an exception, but the norm. Any algorithm designed for realistic settings must be able to deal with failures. This paper presents a new message-passing algorithm for distributed cooperative work in synchronous settings where processors may crash, and where any broadcasts performed by crashing processors are unreliable. We specify the algorithm, prove that it is correct, and perform extensive simulations that show that its performance is close to similar algorithms that use reliable broadcast, and that its work compares favorably to the relevant lower bounds.

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.

TIOA is a formal language for modeling distributed, concurrent, and timed/untimed systems as collections of interacting state machines, called Timed Input/Output Automata. TIOA provide natural mathematical notations for describing systems, their intended properties, and the relationships between their descriptions at varying levels of abstraction. The Tempo toolkit is an implementation of the TIOA language and a suite of tools that supports a range of validation methods for description of systems and their properties, including static analysis, simulation, and machine-checked proofs. The tools are implemented as Eclipse plugins. In this paper we introduce a new plugin of the toolkit, the Tempo-to-Java compiler, which automatically translates high level Tempo specification into executable Java code for various distributed platforms. The translation process is verified to preserve the formal properties of the source specification, hence leading to generated code which is correct by construction.

We revisit the problem of gathering autonomous robots in the plane. In particular, we consider non-transparent unit-disc robots (i.e., fat) in an asynchronous setting with vision as the only means of coordination and robots only make local decisions. We use a state-machine representation to formulate the gathering problem and develop a distributed algorithm that solves the problem for any number of fat robots. The main idea behind the algorithm is to enforce the robots to reach a configuration in which all the following hold:

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.

We study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. We show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. The algorithmic techniques proposed in this article can be used for improving the message complexity of distributed algorithms that rely on an all-to-all message exchange paradigm and are designed for an asynchronous environment. As an example, we show how to improve the message complexity of asynchronous randomized consensus.

In this work we conduct an experimental performance evaluation of four MWMR atomic register implementations: SFW from [8], APRX-SFW and CWFR from [11], and SIMPLE (the generalization of [5] in the MWMR environment). We implement the algorithms on NS2, a single processor simulator, and on PlanetLab, a planetary-scale real-time network platform. Due to its simplistic nature, SIMPLE requires two communication round-trips per read or write operation, but almost no local computation. The rest of the algorithms are (to this writing) the only to allow single round read and write operations but require non-trivial computational demands. We compare these algorithms with SIMPLE and amongst each other to study the trade-offs between communication delay and local computation. Our results shed new light on the practicality of atomic MWMR register implementations.

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.

Epidemic gossip has proven a reliable and efficient technique for sharing information in a distributed network. Much of the reliability and efficiency derives from processes collaborating, sharing the work of distributing information. As a result of this collaboration, processes may receive information that was not originally intended for them. For example, a process may act as an intermediary, aggregating and forwarding messages from some set of sources to some set of destinations. But what if rumors are confidential? In that case, only processes that were originally intended to receive a rumor should be allowed to learn the rumor. This blatantly contradicts the basic premise of epidemic gossip, which assumes that processes can collaborate. In fact, if only processes in a rumor's "destination set" participate in gossiping that rumor, we show that high message complexity is unavoidable. We propose a scheme in which each rumor is broken into multiple fragments using a simple coding scheme: any given fragment provides no information about the rumor, while together, they allow the original rumor to be reassembled. The processes collaborate in disseminating the rumor fragments while ensuring that no process receives all the fragments of a rumor unless it is in that rumor's destination set. Our solution operates in an environment where rumors are dynamically and continuously injected into the system and processes are subject to crashes and restarts. In addition, the scheme presented can tolerate a moderate amount of collusion among curious processes without too large an increase in cost.

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.

This work explores implementations of multiwriter/multi-reader (MWMR) atomic registers in asynchronous, crash-prone, message-passing systems with the focus on low latency and computational feasibility. The efficiency of atomic read/write register implementations is traditionally measured in terms of the latency of read and write operations. To reduce operation latency researchers focused on the communication costs, expressed as the number of communication round-trips (or rounds), often ignoring the computation costs. In this paper we consider efficiency of a register implementation in terms of both communication and computation costs. As of this writing, algorithm SFW is the sole known MWMR algorithm that allows single round read and write operations. The algorithm uses collections of intersecting sets (quorums), and to enable single round operations, SFW relies on the evaluation of certain predicates. We formulate a new combinatorial problem that captures the computational burden of evaluating the predicates in algorithm SFW and we show that it is NP-Complete. To make the evaluation of the predicates feasible, we present a polynomial log-approximation algorithm for this problem and we show how to use it with algorithm SFW. Then we present a new algorithm, called CWFR, that allows fast operations independently of the underlying quorum system construction. The algorithm implements two-round writes and allows reads to complete in a single round. We conclude with experimental evaluations of our algorithms obtained from simulations in NS2.

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.

In this paper, we introduce the problem of Continuous Gossip in which rumors are continually and dynamically injected throughout the network. Each rumor has a deadline, and the goal of a continuous gossip protocol is to ensure good "Quality of Delivery," i.e., to deliver every rumor to every process before the deadline expires. Thus, a trivial solution to the problem of Continuous Gossip is simply for every process to broadcast every rumor as soon as it is injected. Unfortunately, this solution has a high per-round message complexity. Complicating matters, we focus our attention on a highly dynamic network in which processes may continually crash and recover. In order to achieve good per-round message complexity in a dynamic network, processes need to continually form and re-form coalitions that cooperate to spread their rumors throughout the network. The key challenge for a Continuous Gossip protocol is the ongoing adaptation to the ever-changing set of active rumors and non-crashed process. In this work we show how to address this challenge; we develop randomized and deterministic protocols for Continuous Gossip and prove lower bounds on the per-round message-complexity, indicating that our protocols are close to optimal.

This paper presents a new algorithm for a reconfigurable distributed domain-oriented atomic object service, called DO-RAMBO, which stands for Domain-Oriented Reconfigurable Atomic Memory for Basic Objects. This service is suitable for inclusion as a middleware system service for distributed applications requiring atomic read/write data. The implementation substantially extends and refines the abstract RAMBO algorithm of Lynch and Shvartsman that supports individual atomic objects. In this paper, domains are introduced to allow the users to group related atomic objects. The new implementation manages configurations on the basis of domains, significantly improving the utility and the performance of the resulting service. DO-RAMBO guarantees consistency under asynchrony, message loss, node crashes, new node arrivals, and node departures. We present the formal algorithm development for DO-RAMBO and give analytical and empirical results that illustrate the benefit of the new approach.

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.

In this paper we consider the frameworks of Process Algebra and I/O Automata and we apply both towards the verification of a distributed leader-election protocol. Based on the two experiences we evaluate the approaches and draw initial conclusions with respect to their relative capabilities, strengths and usability.To the best of our knowledge, this is the first hands-on evaluation of the two models, and we view it as the cornerstone for a wider investigation of the strengths and weaknesses of the two methodologies in specifying and verifying (distributed) protocols.

Abstract models and specifications can be used in the design of distributed applications to formally reason about their safety properties. However, the benefits of using formal methods are often negated by the ad hoc process of mapping the semantics of an abstract specification to algorithms designed to be executed on target distributed platforms. The challenge of formally specifying communication channels and correctly implementing them as algorithms that use realistic distributed system services is the focus of this paper. This work provides an original formal specification of an abstract asynchronous communication channel with support for dynamic creation and tear down of links between participating network nodes, and its implementation as an algorithm using Java sockets. The specification and the algorithm are expressed using the Input/Output Automata formalism, and it is proved that the algorithm correctly implements the specification, viz. that any externally observable behavior (trace) of the algorithm has a corresponding behavior of the specification. The approach presented here can be used to implement algorithms for dynamic systems, where communicating nodes may join, leave, and experience delays. The result is also of direct benefit to automated code generation, such as that implemented within the Input/Output Automata Toolkit at MIT.

In this paper we present FailRank, a novel framework for integrating and ranking information sources that characterize failures in a grid system. After the failing sites have been ranked, these can be eliminated from the job scheduling resource pool yielding in that way a more predictable, dependable and adaptive infrastructure. We also present the tools we developed towards evaluating the FailRank framework. In particular, we present the FailBase Repository which is a 38GB corpus of state information that characterizes the EGEE Grid for one month in 2007. Such a corpus paves the way for the community to systematically uncover new, previously unknown patterns and rules between the multitudes of parameters that can contribute to failures in a Grid environment. Additionally, we present an experimental evaluation study of the FailRank system over 30 days which shows that our framework identifies failures in 93% of the cases. We believe that our work constitutes another important step towards realizing adaptive Grid computing systems.

In this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. This latter fact implies that there exist message-efficient asynchronous (randomized) consensus protocols, in the context of an oblivious adversary.

Atomic (linearizable) read/write memory is a fundamental abstractions in distributed computing. Following a seminal implementation of atomic memory of Attiya et al. [6], a folklore belief developed that in messaging-passing atomic memory implementations "reads must write." However, work by Dutta et al. [4] established that if the number of readers R is constrained with respect to the number of replicas S and the maximum number of crash-failures t so that R < S/t - 2, then single communication round-trip reads are possible. Such an implementation given in [4] is called fast. Subsequently, Georgiou et al. [3] relaxed the constraint in [4], and proposed semifast implementations with unbounded number of readers, where under realistic conditions most reads need only a single communication round-trip to complete. Their approach groups collections of readers into virtual nodes. Semifast behavior of their algorithm is preserved as long as the number of virtual nodes V is constrained by V < S/t - 2.

Abstract models and specifications can be used in the design of distributed applications to formally reason about their safety properties. However, the benefits of using formal methods are offset by the challenging process of mapping the functionality of an abstract specification to the low-level executable code for target distributed platforms. Formal specification and practical implementation of communication channels is one such challenge. This work provides the first formal specification of an abstract asynchronous communication channel with support for dynamic creation and tear down of communication links between participating network nodes, and its implementation using Java sockets and TCP. The specifications are formulated using Input/Output Automata formalism, and it is proved that the resulting implementation preserves the safety properties of the abstract channel. The approach presented here can be used to implement algorithms for dynamic systems, where communicating nodes may join, leave, and experience arbitrary delays, and it can directly benefit automated code generation.

We study the problem of selfish routing in the presence of incomplete network information. Our model consists of a number of users who wish to route their traffic on a network of m parallel links with the objective of minimizing their latency. However, in doing so, they face the challenge of lack of precise information on the capacity of the network links. This uncertainty is modelled via a set of probability distributions over all the possibilities, one for each user. The resulting model is an amalgamation of the KP-model of (E. Koutsoupias and C. H. Papadimitriou, 1999) and the congestion games with user-specific functions of (I. Milchtaich, 1996). We embark on a study of Nash equilibria and the price of anarchy in this new model. In particular, we propose polynomial-time algorithms for computing some special cases of pure Nash equilibria and we show that negative results of (I. Milchtaich, 1996), for the non-existence of pure Nash equilibria in the case of three users, do not apply to our model. Consequently, we propose an interesting open problem in this area, that of the existence of pure Nash equilibria in the general case of our model. Furthermore, we consider appropriate notions for the social cost and the price of anarchy and obtain upper bounds for the latter. With respect to fully mixed Nash equilibria, we propose a method to compute them and show that when they exist they are unique. Finally we prove that the fully mixed Nash equilibrium maximizes the social welfare.

This paper investigates time-efficient implementations of atomic read-write registers in message-passing systems where the number of readers can be unbounded. In particular we study the case of a single writer, multiple readers, and S servers, such that the writer, any subset of the readers, and up to t servers may crash. A recent result of Dutta et al. [3] shows how to obtain fast implementations in which both reads and writes complete in one communication round-trip, under the constraint that the number of readers is less than S t - 2, where t < S 2 . In that same paper the authors pose a question of whether it is possible to relax the bound on readers, and at what cost, if semifast implementations are considered, i.e., implementations that have fast reads or fast writes.This paper provides an answer to this question. It is shown that one can obtain implementations where all writes are fast, i.e., involving a single round-trip communication, and where reads complete in one to two communication rounds under the assumption that no more than t < S 2 servers crash. Simulated scenarios included in this paper indicate that only a small fraction of reads require a second communication round. Interestingly the correctness of the implementation does not depend on the number of concurrent readers in the system. The solution is obtained with the help of non-unique virtual ids assigned to each reader, where the readers sharing a virtual id form a virtual node. For the proposed definition of semifast implementations it is shown that implementations satisfying certain assumptions are semifast if and only if the number of virtual ids in the system is less than S t - 2. This result is proved to be tight in terms of the required communication. It is shown that only a single complete two-round read operation may be necessary for each write operation. It is furthermore shown that no semifast implementation exists for the multi-reader, multi-writer model.

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

This paper presents a new algorithm for a reconfigurable distributed domain-oriented atomic object service, called DO-RAMBO, which stands for domain-oriented reconfigurable atomic memory for basic objects. This service is suitable for inclusion as a middleware system service for distributed applications requiring atomic read/write data. The implementation substantially extends and refines the abstract RAMBO algorithm of Lynch and Shvartsman that supports individual atomic objects. In this paper domains are introduced to allow the users to group related atomic objects. The new implementation manages configurations on the basis of domains, significantly improving the utility and the performance of the resulting service. DO-RAMBO guarantees consistency under asynchrony, message loss, node crashes, new node arrivals, and node departures. We present the formal algorithm development for DO-RAMBO and give analytical and preliminary empirical results that illustrate the benefit of the new approach

The problem of cooperatively performing a set of t tasks in a decentralized computing environment subject to failures is one of the fundamental problems in distributed computing. The setting with partitionable networks is especially challenging, as algorithmic solutions must accommodate the possibility that groups of processors become disconnected (and, perhaps, reconnected) during the computation. The efficiency of task-performing algorithms is often assessed in terms of work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, the scenario where the processors are partitioned into g disconnected components causes any task-performing algorithm to have work $\Omega(t\cdot g)$ even if each group of processors performs no more than the optimal number of $\Theta(t)$ tasks. Given that such pessimistic lower bounds apply to any scheduling algorithm, we pursue a competitive analysis. Specifically, this paper studies a simple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. The performance of this algorithm is compared against that of an omniscient off-line algorithm with full knowledge of the future changes in the communication medium. The paper describes a notion of computation width, which associates a natural number with a history of changes in the communication medium, and shows both upper and lower bounds on work-competitiveness in terms of this quantity. Specifically, it is shown that the simple randomized algorithm obtains the competitive ratio $(1+\mathbf{cw}/e)$, where $\mathbf{cw}$ is the computation width and e is the base of the natural logarithm ($e=2.7182\ldots$); this competitive ratio is then shown to be tight.

The problem of cooperatively performing a set of t tasks in a decentralized setting where the computing medium is subject to failures is one of the fundamental problems in distributed computing. The setting with partitionable networks is especially challenging, as algorithmic solutions must accommodate the possibility that groups of processors become disconnected (and, perhaps, reconnected) during the computation. The efficiency of task-performing algorithms is often assessed in terms of their work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, an adversary that is able to partition the network into g components can cause any task-performing algorithm to have work Ω(t•g) even if each group of processors performs no more than the optimal number of Θ(t) tasks.Given such pessimistic lower bounds, and in order to understand better the practical implications of performing work in partitionable settings, we study distributed work-scheduling andpursue a competitiveanalysis. Specifically, we study asimple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. We compare the performance of the algorithm against that of an "off-line" algorithm with full knowledge of the future changes in the communication medium. We describe a notion of computation width, which associates a natural number with a history of changes in the communication medium, and show both upper and lower bounds on competitiveness in terms of this quantity. Specifically, we show that a simple randomized algorithm obtains the competitive ratio (1+cw/e), where cw is computation width; we then show that this ratio is tight.

No abstract available.