Message routing protocol is a key factor in delivering messages efficiently in Delay/Disruption-tolerant networks (DTNs). Messages sent by a mobile node are transferred in a Store-Carry-Forward manner among mobile nodes in a DTN. Existing protocols take into account mobile nodes’ behavior, history information, and movement model to optimize their mechanisms for exchanging messages while encountering one another. However, none of them consider the construction of the underlying environment, such as road network construction. We propose CD-PRoPHET, a variant of PRoPHET, to tune the delivery probability by considering the road network density. Our simulation results show that CD-PRoPHET significantly reduces the overhead ratio at the cost of the delivery ratio.

Oblivious RAM (ORAM) enhances secure data storage by obscuring memory access patterns, which is essential for many secure applications. However, the expenses related to existing ORAM techniques are often excessively high for practical application. This occurs because obtaining a single data block necessitates retrieving many redundant blocks during server communication. While many optimizations concentrate on data locality and access patterns, there has been inadequate attention to caching and prefetching. Our previous research indicated that caching significantly reduces ORAM latency. We provide the architecture of an ORAM implementation that integrates caching and prefetching techniques for practical use.

Random walks play an important role in computer science, spreading a wide range of topics in theory and practice, including networking, distributed systems, and optimization. Levy walk is a family of random walks whose distance of a walk is chosen from the power law distribution. There are lots of works of Lévy walk in the context of target detection in swarm robotics, analyzing human walk patterns, and modeling the behavior of animal foraging in recent years. According to these results, it is known as an efficient method to search in a two-dimensional plane. However, most of the works assume a continuous plane. In this paper, our simulation results indicate that Lévy walk on unit disk graphs is more efficient than other random walks on the resource exploration problem. This result means that Lévy walk can detect illegal data in large-scale delay tolerant sensor networks in realistic time.

Random walks play an important role in computer science, spreading a wide range of topics in theory and practice, including networking, distributed systems, and optimization. Levy flight is a family of random walks whose the distance of a walk is chosen from the power law distribution. There are lots of works of Levy flight in the context of target detection in swarm robotics, analyzing human walk patterns, and modeling the behavior of animal foraging in recent years. According to these results, it is known as an efficient method to search in a two-dimensional plane. However, all these works assume a continuous plane, so far. In this paper, we propose an algorithm for Levy flight and analyze the behavior of the algorithm on unit disk graphs. We also show the comparison of Levy flight with other random walks on the message dissemination problem. Our simulation results indicate that the proposed algorithm is significantly efficient to diffuse messages compared to the other random walks on unit disk graphs.

In peer-to-peer networks, each node directly connects to other nodes without access points. This type of network system is useful for information sharing by using mobile devices (e.g., smart phones). On message delivery over the network, it is very difficult to assume the static routing if each node is assumed to move. In this paper, we suppose to use gossip-style epidemic message dissemination and show the performance evaluation of several gossip algorithms in terms of network topology. Specifically, we focus on the distribution of links in the network. Our results clarified the characteristics of those algorithms on the topologies that are biased the degree distribution locally.

In a wireless sensor and actuator network (WSAN), a group of sensor nodes, actuators, and actuation devices are geographically distributed and linked by wireless networks. Sensor nodes gather information for an event occurring in the physical world and send them to actuators. Actuators perform appropriate actions on actuation devices by making a decision on receipt of sensed values from sensor nodes. Sensor nodes are low cost, low powered devices with limited energy, computation, and wireless communication capabilities. Messages may be lost due to collision and noise and sensor nodes may be faulty. Here, nodes are required to reliably communicate with each other in realtime manner. In order to achieve the reliability, we discuss the multi-actuator/multi-sensor (MAMS) model where each sensor node sends sensed values to multiple actuators and each actuator receives sensed values from multiple sensor nodes in an event area. Even if messages are lost and sensor nodes are faulty, actuators can surely receive sensed values. An actuator makes a decision on what actions to be performed in what order. We discuss a semi-passive coordination (SPC) protocol for multiple actuators to communicate with multiple sensor nodes and perform actions. We evaluate the SPC protocol in terms of the number of messages exchanged among actuators

In peer-to-peer (P2P) applications like computer supported cooperative work (CSCW), multiple peer processes are required to cooperate to make a global decision, e.g. fix a meeting schedule of multiple persons. We discuss how multiple peer processes make a decision to achieve some objectives in a peer-to-peer (P2P) overlay network. Here, every process is assumed to be peer and autonomous. That is, there is no centralized coordination. A domain of a process is a collection of possible values which the process can take. Each process first takes a value v in its domain and notifies the other processes of the value v. A process can change the value with another value on receipt of values from other processes. However, a process can take only some value depending on the value v. For example, a process may abort after notifying commit but cannot commit after notifying abort in the commitment control. An existentially (E)-precedent relation shows what values a process can take after taking a value. In addition, a process takes a more preferable value if the process can take one of multiple values. Thus, values are ordered in the preferentially (P)-precedent relation. Based on the E- and P- precedent relations, each process takes the most preferable one in the values which can be changed from the current value v. In this paper, we discuss how every process makes an agreement on a value while each process can change the value according to the relations. In this paper, we discuss a coordination protocol in a type of heterogeneous system where every pair of processes have different E-precedent relation and P-precedent relation on the same domain. Each process learns a part of the precedent relations of another process through exchanging values.

Servers can be fault-tolerant through replication and checkpointing technologies in the client server model. However, application programs cannot be performed and servers might block in the two-phase commitment protocol due to the client fault. In this paper, we discuss the transactional agent model to make application programs fault-tolerant by taking advantage of mobile agent technologies where a program can move from a computer to another computer in networks. Here, an application program on a faulty computer can be performed on another operational computer by moving the program. A transactional agent moves to computers where objects are locally manipulated. Objects manipulated have to be held until a transactional agent terminates. Some sibling computers which the transactional gent has visited might be faulty before the transactional agent terminates. The transactional agent has to detect faulty sibling computers and makes a decision on whether it commits/aborts or continues the computation by skipping the faulty computers depending on the commitment condition. For example, a transactional agent has to abort in the atomic commitment if a sibling computer is faulty. A transactional agent can just drop a faulty sibling computer in the at-least-one commitment. We evaluate the transactional agent model in terms of how long it takes for the transactional agent to treat faulty sibling computers .

In distributed applications like computer supported cooperative work (CSCW), multiple peer processes are required to cooperate to make a global decision, e.g. fix a date for a meeting of multiple persons. We discuss how multiple peer processes make a decision to achieve some objectives in a peer-to-peer (P2P) overlay network. Here, every process is assumed to be peer and autonomous. A domain of a process is a collection of possible values which the process can take. Each process first takes a value v in its domain and notifies the other processes of the value v. A process can change the value to another value on receipt of values from other processes. However, a process may not take every value in the domain and can take only some value depending on the value v. For example, a process may abort after notifying commit but cannot commit after abort in the commitment control. An existentially dominant relation shows what values a process can take after taking a value. In addition, values are also ordered in the preferential relation. Based on the existential and preferential relations, each process takes the most preferable value in the domain, which is dominantly preceded by the value v. In this paper, we discuss how every process makes an agreement on a tuple of values while each process can change the value according to the existential and preferential relations. In this paper, we discuss a coordination protocol in a type of heterogeneous system where every pair of processes have the same domain but may have different existential and preferential relations. Each process learns a part of the relations of another process through exchanging values

In a wireless sensor-actuator network (WSAN), sensor nodes and actuator nodes are interconnected with wireless channels. Messages sent by sensor nodes might be lost due to collision and noise if multiple sensor nodes simultaneously send the messages in a wireless channel. In sensing applications, sensed values are in nature required to be delivered to actuator nodes with some time constraints. If a message is detected to be lost by some receiver nodes, the sender node retransmits the message to the receiver nodes. It takes at least three rounds to detect and retransmit a lost message since the message is sent. The more number of messages are retransmitted, the more number of messages collide. We have to reduce the number of messages retransmitted to realize the efficient data transmission. We newly propose a redundant data transmission (RT) protocol where data in a message m1is redundantly forwarded to the destination node by another message m2sent by the receiver node of the message m1. Even if the message m1is lost, the destination node can receive the data in the message m2if the destination node receives the message m2since the message m2carries the data in the message m1. We evaluate the RT protocol compared with the CSMA protocol in terms of how much sensing data a node can receive in presence of messages loss

Peer-to-peer (P2P) systems are now getting popular and are widely used in various types of applications. In this paper, we newly propose a superpeer-based two-layer P2P overlay network with the charge-based flooding (CBF) algorithm, a look-up protocol for distributed multimedia objects. The layers of normal peer and superpeer are composed of a set of normal peers and a set of superpeers, respectively. Multiple normal peers with some common properties, e.g. files, are interconnected with a superpeer. A collection of a superpeer and normal peers is referred to as a cluster. In a cluster, a normal peer tries to find a target peer without being helped by a superpeer. If the target file is not detected in the cluster, the normal peer asks the superpeer to find the target file on behalf of the normal peer. Then, the superpeer forwards the request to other superpeers by using the CBF algorithm at the superpeer layer

In a wireless sensor-actuator network (WSAN), sensors send sensed values to actuators in a wireless channel. Messages sent by nodes might be lost due to collision and noise if multiple nodes simultaneously send the messages. If a message is detected to be lost, the source node retransmits the message to the destination nodes. It takes at least three rounds to detect and retransmit a lost message since the source node sends the message. The more number of messages are retransmitted, the more number of messages collide. We have to reduce the number of messages retransmitted to realize the efficient data transmission. We newly propose a redundant data transmission (RT) protocol where a sensed value is redundantly carried to the destination node by multiple messages. Even if a message is lost, the destination node can receive data in the lost message if the destination node receives other redundant messages. In addition, we have to reduce the energy consumption of a sensor node. A sensor node mainly consumes the energy to send and receive messages. Even if an event occurs, only some number of sensor nodes sensing the event send the sensed values to reduce the total energy consumption. We discuss an energy-efficient data transmission protocol. We evaluate the RT protocol compared with the CSMA protocol in terms of how much sensing data a node can receive in presence of messages loss

Service supported by an object is modeled to be a set of methods and quality of service (QoS). In addition to finding a peer which holds a target object, it is critical to discuss what peer is allowed to manipulate the target object in what method. In this paper, we take an acquaintance approach to finding and manipulating objects in P2P overlay networks. An acquaintance peer of a peer p is a peer whose service the peer p know and with which the peer p can directly communicate. If an access request is issued, a peer has to find where a target object exists, how to obtain an access right on the target object, and how to manipulate the target object. In this paper, we discuss ways to obtain results which satisfying an access requests by the cooperation of acquaintances. Acquaintance peers of a peer p may knows different information on target peers since it takes time to propagate change information of the target peers and peers may be faulty. Here, it is critical to discuss how much a peer can trust each acquaintance. We define the trustworthiness of an acquaintance peer in terms of the acquaintance relations among the peers.

Much previous work has been done on distributed dynamic resource allocation of resources like nodes and connected links in networks. It is not easy to find ways to allocate resources and analyze the performance of the way due to the scalability and change of the network. In this paper, we discuss a novel macro-level, zone-based approach. Zone-based resource allocation mechanism (ZRAM) has not been discussed in the research literature. By zone we mean, one or more than one neighboring autonomous system (AS). A zone has a zone manager and some border routers; which can cooperate with each other by exchanging traffic information. The key challenges for zone-based resource allocation are to realize the scalability and robustness. In the ZRAM, the network traffic is considered to be routed from zones to zones, not nodes to nodes. Routes on zones are decided based on states of the zones. Three types of zone state, vacancy, available and no-vacancy are obtained from the simulation results which are described later in this paper.

It is widely recognized that distributed systems would greatly benefit from the availability of a generic failure detection service. There are however several issues that must be addressed before such a service can actually be implemented. Traditionally, failure detectors or failure detection services provide a list of processes that are currently suspected by them. Mechanisms for propagating such information are implemented mostly for such traditional failure detectors. Recently, a family of failure detectors that provide the degree of confidence that a given process has actually crashed, called suspicion level. It is called the /spl phi/ failure detector which is an implementation of the notion of accrual failure detectors. In this paper, we highlight the issue on the propagation mechanism of information on crashed/suspected processes with the /spl phi/ failure detector. Since the suspicion level is represented as a continuous value, existing mechanisms are not appropriate for this type of failure detectors. Therefore, we propose a notification system that can efficiently propagate suspicion levels. It can provide such information to proper receivers and processes in distributed applications do not need to implement a function for failure detection by using the proposed system and the /spl phi/ failure detector.

In a peer-to-peer (P2P) overlay network, a large number and various types of peers are cooperating by exchanging multimedia contents. Here, multimedia streaming is a key technology to realize multimedia applications. A multimedia content is distributed to multiple peers and these peers named contents peers can support other leaf peers with the content. Multimedia contents are required to be efficiently delivered to processes in a real-time manner. Some contents peer may not send packets at a required rate and a communication channel may not support enough quality of service (QoS). In this paper, we newly discuss a heterogeneous asynchronous multi-source streaming (HAMS) model where multiple contents peers in parallel transmit packets of a multimedia content to a requesting leaf peer to realize highly reliability and scalability.

In a wireless sensor and actor network (WSAN), a group of sensors and actors are geographically distributed and linked by wireless networks. Sensors gather information sensed for an event in the physical world and send them to actors. Actors perform appropriate actions on actuation devices by making a decision on receipt of sensed information from sensors. Sensors are low cost, low powered devices with limited energy, computation, and wireless communication capabilities. Sensors may not only stop by fault but also suffer from arbitrary faults. Furthermore, wireless communication is less reliable due to noise and shortage of power of sensors. Reliable real time communication among sensors, actors, and actuation devices, is required in WSAN applications. We newly propose a multi-actor/multi-sensor (MAMS) model. In addition, multiple actors may perform actions on receipt of sensed information. Multiple redundant execution of an action on each device has to be prevented and conflicting actions on each device from multiple actors have to be serialized. In this paper, we discuss how to make WSAN reliable and available and how to reliably and non-redundantly perform actions with realtime constraints.

A transactional agent is a mobile agent to manipulate objects distributed on computers with some commitment condition like atomic commitment. Computers may stop by fault. In the client-server model, servers can be fault-tolerant according to replication and checkpointing technologies. However, an application program cannot be performed if a client computer is faulty. A transactional agent can move to another operational computer if some destination computer to which the agent to move is faulty. In this paper, we discuss how a program reliably manipulating objects can be realized in a mobile agent in presence of computer faults.

An object is a unit of resource distributed in a peer-to-peer (P2P) overlay network. Service supported by an object is modeled to be a set of methods. It is critical to discuss which peer can manipulate an object in which method, i.e. only a peer granted an access right (permission) can manipulate an object. First, an application has to find target peers which can manipulate a target object. In this paper, we take an acquaintance approach to finding and manipulating objects. Here, it is critical to discuss how much a peer trusts each acquaintance peer. We define the trustworthiness of each acquaintance peer in terms of how satisfiable a response from the peer is for each access request.

Multimedia contents are distributed to peers in various ways in peer-to-peer (P2P) overlay networks. A peer which holds a content, even a part of a content can provide other peers with the content. Multimedia streaming is more significant in multimedia applications than downloading ways in Internet applications. We discuss how to support peers with multimedia streaming service by using multiple contents peers. In our distributed multi-source streaming model, a collection of multiple contents peers in parallel transmit packets of a multimedia content to a requesting leaf peer to realize the reliability and scalability without any centralized controller. Even if some peer stops by fault and is degraded in performance and packets are lost and delayed in networks, a requesting leaf peer receives every data of a content at the required rate. We discuss a pair of flooding-based protocols, distributed and tree-based coordination protocols DCoP and TCoP, to synchronize multiple contents peers to reliably and efficiently deliver packets to a requesting peer. A peer can be redundantly selected by multiple peers in DCoP but it taken by at most one peer in TCoP. We evaluate the protocols in terms of how long it takes and how many messages are transmitted to synchronize multiple contents peers

In a wireless sensor and actor network (WSAN), a group of sensors, actors, and actuation devices are geographically distributed and linked by wireless networks. Sensors gather information for an event occurring in the physical world and send them to actors. Actors can perform appropriate actions on actuation devices by making a decision on receipt of sensed information from sensors. Sensors are low cost, low powered devices with limited energy, computation, and wireless communication capabilities. Sensors may not only stop by fault but also suffer from arbitrary faults. Furthermore, wireless communication is less reliable due to noise and shortage of power of sensors. Reliable realtime communication among sensors, actors, and actuation devices is required in WSAN applications. In order to realize the reliability and realtimeness, we newly propose a multi-actor/multi-sensor (MAMS) model where each sensor sends sensed information to multiple actors and each actor receives sensed information from multiple sensors in an event area. Actors are required to causally/totally order events from multiple sensors and actions on actuation devices. In addition, multiple actors may perform actions on receipt of sensed information. Multiple redundant executions of an action on each device have to be prevented and conflicting actions on each device from multiple actors have to be serialized. In this paper, we discuss how to realize reliable, ordered delivery of sensed information to actors from sensors on the basis of global time and how to reliably and non-redundantly perform actions with realtime constraints

A transactional agent is a mobile agent to manipulate objects distributed on computers with some type of commitment condition. For example, a transactional agent commits only if at least one object could be successfully manipulated in the at-least-one commitment condition. Computers may stop by fault while networks are assumed to be reliable. In the client-server model, servers can be fault-tolerant according to traditional replication and checkpointing technologies. However, an application program cannot be performed if a client computer is faulty. An application program can be performed on another operational computer even if a computer is faulty in the transactional agent model. For example, a transactional agent can move to another operational computer if some destination computer where the agent to move is faulty. There are kinds of faulty computers for a transactional agent, current, destination, and sibling computers where a transactional agent now exist, will move, and has visited, respectively. We discuss how the transactional agent can be tolerant of the types of faults. We show how a program reliably manipulating objects can be realized in a mobile agent in presence of computer faults

For many years, people have been advocating the development of failure detection as a basic service, but, unfortunately, without meeting much success so far. We believe that this comes from the fact that important system engineering issues have not yet been addressed adequately, thus preventing the definition of a truly generic service. Ultimately, our goal is to define a service that is both simple and expressive, yet powerful enough to support the requirements of many distributed applications. To this end, we consider an alternative interaction model between the service and the applications, called accrual failure detectors. Roughly, an accrual failure detector associates to each process a real value representing a suspicion level, instead of the traditional binary information (i.e., trust vs. suspect). In this paper, we provide a rigorous definition for accrual failure detectors, demonstrate that changing the interaction model leads to no loss in computational power, discuss quality of service issues, and present several possible implementations.

In a peer-to-peer (P2P) overlay network, a large number and various types of peer processes are cooperating by using multimedia contents like movies. Multimedia streaming is a key technology to realize multimedia applications. Here, multimedia contents are required to be reliable and continuously delivered to processes in a realtime manner. In this paper, we newly discuss a heterogeneous asynchronous multi-source streaming (HAMS) model where multiple contents peers transmit packets of a multimedia content to a requesting leaf peer to increase the throughput, reliability, and scalability in P2P overlay networks.

The detection of failures is a fundamental issue for fault-tolerance in distributed systems. Recently, many people have come to realize that failure detection ought to be provided as some form of generic service, similar to IP address lookup or time synchronization. However, this has not been successful so far; one of the reasons being the fact that classical failure detectors were not designed to satisfy several application requirements simultaneously. We present a novel abstraction, called accrual failure detectors, that emphasizes flexibility and expressiveness and can serve as a basic building block to implementing failure detectors in distributed systems. Instead of providing information of a binary nature (trust vs. suspect), accrual failure detectors output a suspicion level on a continuous scale. The principal merit of this approach is that it favors a nearly complete decoupling between application requirements and the monitoring of the environment. In this paper, we describe an implementation of such an accrual failure detector, that we call the /spl phi/ failure detector. The particularity of the /spl phi/ failure detector is that it dynamically adjusts to current network conditions the scale on which the suspicion level is expressed. We analyzed the behavior of our /spl phi/ failure detector over an intercontinental communication link over a week. Our experimental results show that if performs equally well as other known adaptive failure detection mechanisms, with an improved flexibility.

Protocols that solve agreement problems are essential building blocks for fault tolerant distributed systems. While many protocols have been published, little has been done to analyze their performance, especially the performance of their fault tolerance mechanisms. In this paper, we compare two well-known asynchronous consensus algorithms. In both algorithms, a leader process tries to impose a decision, and another leader retries if the leader fails doing so. The algorithms elect leaders differently: the Chandra-Toueg algorithm has a rotating leader, whereas processes in the Paxos algorithm elect leaders directly. We investigate the performance implications of this difference. In the system under study, processes send atomic broadcasts to each other. Consensus is used to decide the delivery order of messages. We evaluate the steady state latency in (1) runs with neither crashes nor suspicions, (2) runs with crashes and (3) runs with no crashes in which correct processes are wrongly suspected to have crashed, as well as the transient latency after (4) one crash and (5) multiple correlated crashes. The results show that the Paxos algorithm tolerates frequent wrong suspicions (3) and correlated crashes (5) better, while the performance is comparable in all other scenarios.

This paper discusses the problem of implementing a scalable failure detection service for grid systems. More specifically, traditional implementations of failure detectors are often tuned for running over local networks and fail to address important problems found in wide-area distributed systems, such as grid systems. We identify some of the most important problems raised in the context of grids. We then survey recent propositions that can help in solving some of these problems.