10550438
Deterministic /spl delta/-connected overlay for peer-to-peer networks
The network connectivity is a basic requirement while implementing fundamental communication and storage abstractions in P2P networks, featuring scalability and fault-tolerance. The quality of services of abstractions like for example multicast, publish/subscribe, group membership or persistent storage is strongly related to the connectivity degree of the underlying overlay. Intuitively, a higher overlay connectivity ensures a reinforced reliability and consequently, the deployment of distributed applications with real-time constraints on top of these overlays becomes feasible even in environments characterized by a high dynamicity, i.e., nodes arriving and departing at a high rate. Our paper proposes a novel delta-connected DHT-free P2P overlay. Our overlay offers strong connectivity guarantees despite the system dynamicity. The construction and the maintenance of our overlay is completely decentralized and handled strictly locally, through deterministic algorithms whose correctness is rigorously proved
11950525
Anonymous publish/subscribe in P2P networks
One of the most important issues to deal with in peer-to-peer networks is how to disseminate information. In this paper, we use a completely new approach to solving the information dissemination problem. Our approach uses the publish/subscribe paradigm. The publish/subscribe method is the most inclusive strategy to establish communication between the information providers (publishers) and the information consumers (subscribers). We give a formal definition of publish/subscribe systems. We then use the publish/subscribe communication paradigm to design deterministic protocols (topic and content-based) for peer-to-peer networks. Our protocols are designed on top of an innovative information dissemination scheme, and can cope with the anonymity and mobility of both publishers and subscribers, weak-connectivity, and polarization, which are some of the characteristics of peer-to-peer networks. Moreover, in our solutions, every node could play a role of both publisher and subscriber The algorithms are designed completely independent of the underlying routing substrates. The key advantage of our protocols is that they are scalable without additional re-organization cost. To the best of our knowledge, this is the first time the content-based subscription has been addressed in peer-to-peer networks.
205481178
Stabilizing mobile philosophers
We present a self-stabilizing solution to a new version of the dining philosophers problem. We call this problem mobile philosophers problem because the philosophers can move around a logical ring formed out of a dynamic network.
9624059
Publish/subscribe scheme for mobile networks
The information dissemination in mobile networks is an important but complex and challenging problem. Designing suitable communication primitives for these systems is critical. One of these primitives is the publish/subscribe paradigm. The publish/subscribe is a strategy to establish communication between the information providers (publishers) and information consumers (subscribers) in a distributed system. Our work focuses on an appropriate distributed infrastructure suitable for a scalable implementation of a publish/subscribe system. We present a formal model which is adapted for the peer-based particular subscription criteria of publish/subscribe systems. Moreover, we propose a general deterministic information diffusion scheme for mobile systems. The three main features of our communication scheme are the following: First, our scheme is well-adapted to scalable systems without compromising any subscription criteria or network reorganization. Second, we maintain the anonymity of the distributed system --- in order to maintain the network structure, we need only local information. Third, our solution is fully decentralized and modular, thus making it appropriate for practical implementations.
60197858
Self-Stabilizing Wormhole Routing on Ring Networks
Wormhole routing is most commonly used in parallel architectures in which messages are sent in small fragments, called flits. It is a lightweight and efficient method of routing messages between parallel processors. Self-stabilization is a technique that guarantees tolerance to transient faults (e.g., memory corruption or communication hazards) for a given protocol. Self-stabilization guarantees that the network recovers to a correct behavior in a finite amount of time, without the need for human intervention. Self-stabilization also guarantees the safety property, meaning that once the network is in a legitimate state, it will remain there until another fault occurs.
This paper presents the first self-stabilizing network algorithm in the wormhole routing model, using the unidirectional ring topology. Our solution benefits from wormhole routing by providing high throughput and low latency, and from self-stabilization by ensuring automatic resilience to all possible transient failures.
122665755
External control in Markovian genetic regulatory networks
Probabilistic Boolean networks (PBN's) have been recently introduced as a rule-based paradigm for modeling gene regulatory networks. Such networks, which form a subclass of Markovian genetic regulatory networks, provide a convenient tool for studying interactions between different genes while allowing for uncertainty in the knowledge of these relationships. This paper deals with the issue of control in probabilistic Boolean networks. More precisely, given a general Markovian genetic regulatory network whose state transition probabilities depend on an external (control) variable, the paper develops a procedure by which one can choose the sequence of control actions that minimize a given performance index over a finite number of steps. The procedure is based on the theory of controlled Markov chains and makes use of the classical technique of dynamic programming. The choice of the finite horizon performance index is motivated by cancer treatment applications where one would ideally like to intervene only over a finite time horizon, then suspend treatment and observe the effects over some additional time before deciding if further intervention is necessary. The undiscounted finite horizon cost minimization problem considered here is the simplest one to formulate and solve, and is selected mainly for clarity of exposition, although more complicated costs could be used, provided appropriate technical conditions are satisfied.
11020739
Jigsaw Texture Synthesis
Texture synthesis aims to seamlessly extend a sample texture. This can be achieved by reproducing the texture's recognisable patterns along with minimising the occurrences of undesirable image characteristics such as disjoint image features. Presently, patch-based methods have consistently produced the most impressive results. These methods involve aligning and stitching texture patches together. However, image inconsistencies exist when image features are misaligned; they are either fused together or abruptly cut off. Our method minimises the occurrences of these anomalies by using image edges to align patches and redefine their boundaries to preserve texture features. This implementation requires little to no user-defined variables or iterations and can be practically scalable given some pre-computation.
14845392
Internet-Scale Storage Systems under Churn -- A Study of the Steady-State using Markov Models
Content storage in a distributed collaborative environment uses redundancy for better resilience and thus provides good availability and durability. In a peer-to-peer environment, where peers continuously leave and rejoin the network, various lazy strategies can be employed to maintain a minimal redundancy of stored content in the system. Existing static resilience analyses fail to capture in detail the system's behavior over time, particularly the probability mass function of the actual available redundancy, since it ignores the crucial interplay between churn and maintenance operations, and looks only at the average system property. We perform a Markovian time-evolution analysis of the system specified by probability mass function of each possible system state, and establish that given a fixed rate of churn and a specific maintenance strategy, the system operates in a corresponding steady-state (dynamic equilibrium). Understanding the behavior of the system under such a dynamic equilibrium is a fundamental ingredient to precisely evaluate analytically the system's performance and availability as well as to determine the required operational maintenance cost. We also propose a new randomized variant of a lazy-maintenance scheme which has significant performance benefits in comparison to the existing deterministic procrastination based maintenance. We demonstrate the use of our analysis methodology in comparing performance of maintenance schemes using the examples of the new maintenance scheme we propose and the erstwhile best known existing lazy maintenance scheme. The comparative study shows that our randomized lazy maintenance strategy has substantially better resilience at same maintenance cost
805959
Providing Real-Time Response, State Recency and Temporal Consistency in Databases for Rapidly Changing Environments
Abstract Databases have been proposed as the chosen platform to develop automated control systems for environments where the state of the system changes rapidly, and actions need to be taken with timing constraints, such as stock trading, air traffic control, network management and process control. The workload in such systems consists primarily of two types: (a) updates , which report the state of the environment to the database and arrive very frequently, and (b) transactions which arrive with deadlines. In this paper we develop algorithms to install these updates rapidly enough to ensure “state recency” while allocating sufficient resources to transactions to minimize tardiness. We also require that these transactions read temporally consistent data. In summary, this paper contributes in the following three interrelated issues: 1. 1. First and foremost, we look at some interesting problems regarding amalgamating temporal and real-time databases. 2. 2. We look at simultaneous satisfaction of state recency and temporal consistency which are central issues in the class of systems considered in this paper, i.e., rapidly changing systems. 3. 3. We design algorithms that attempt to achieve equilibrium with regard to the conjoint processing of frequently arriving state updates and time constrained transactions. © 1997 Published by Elsevier Science Ltd
16977816
Handling Sensor Data in Rapidly Changing Environments to Support Soft Real-Time Requirements
Databases have been mandated as the chosen platform to develop automated control systems for environments where the state of the system changes rapidly and actions need to be taken with timing constraints, for example, stock trading, air traffic control, network management, and process control to name a few. Input data in such systems come from sensors distributed throughout the physical environment being monitored. As the system state changes rapidly, the sensors report information fast and with high volumes. Control decisions in such systems are highly dependent on the accuracy and timeliness of such recorded sensor-reported data. In this paper we suggest ways to algorithmically maintain the accuracy and timeliness of sensor data by enforcing two properties termedrecency andtemporal consistency. Simultaneously, our algorithms also attempt to satisfyquality of service requirements on response times of queries submitted in such systems. The performance of these algorithms is validated through an extensive simulation.