Information Gathering using Levy Flight on Sensor Networks

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. 


Platform for 3D Object Sharing

Many pictures and videos have been shared on the Web. Those are possible to easily find what you need by using a search engine. The spread of 3D printer, 3D objects are also expected to be shared in the same manner. However, unlike pictures and videos, 3D objects have a problem that the appearance changes by rotation and zoom operations. So that, the addition of annotations considering the viewpoint position is required for shared 3D objects. We focus on those of 3D objects with the camera viewpoint in this work and implemented a prototype of the annotation sharing system of 3D objects with location-aware annotations. It can put annotations on a 3D object with location information and display them properly according to the current viewpoint of the object.

We also implemented the synchronization mechanism for 3D objects based on Publish/Subscribe model. This mechanism is realized by publishing the viewpoint position when it has been changed by rotation and zoom operations. It is scalable because it is a non-blocking operation. Moreover it is low-cost in its implementation and is light-weight in its execution because clients run on Web browsers. It is, for example, useful for teleconference in medical practice to discuss on an operative procedure using 3D objects of internal organs.

We are going to implement additional functions e.g., cooporative editing, etc., without loosing scalability and realize an integrated platform for 3D objects.


Accrual Failure Detectors

Detecting 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 is the difficulty to satisfy several application requirements simultaneously when using classical failure detectors. We proposed 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 boolean 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. We made an implementation based on the accrual failure detector model, that we call the phi failure detector (1). The particularity of the 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 phi failure detector over an intercontinental communication link during several days. Our experimental results show that our phi failure detector performs equally well as other known adaptive failure detection mechanisms, with an improved flexibility. The phi accrual failure detector is currently implemented in several services, such as Cassandra of Facebook(see here), Akka (see here), Node.js(see here), APPIA developed at Universidade de Lisboa.

Chief investigator: Naohiro HAYASHIBARA