Machinations

[The following blog report on SSS’13 was written by my student George Saad – Ed]

15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2013) was held at the mid of this month in Osaka, Japan. This conference discusses the design and development of distributed systems with fault-tolerance and self-* properties. SSS 2013 had five sessions: self-stabilization; fault-tolerance and dependability; formal methods and distributed systems; ad-hoc, sensors, mobile agents and robot networks; and P2P, social, self-organizing, autonomic and opportunistic networks.

We presented our paper, Self-Healing of Byzantine Faults, in the self-stabilization session. Our main result is a self-healing algorithm, for communication networks, to detect message corruptions made by Byzantine nodes and to segregate such nodes so that eventually they can no longer corrupt messages. Our self-healing algorithm reduces communication cost significantly compared to non-self-healing algorithms.

In the same self-stabilization session, the safe-convergence property was discussed. Due to transient faults, a system may be placed in some arbitrary configuration. A distributed algorithm is self-stabilizing if the system will recover to a legitimate configuration, without external intervention, in finite time. Safely-converging self-stabilization is an extension of self-stabilization, where after the system is recovered to a legitimate configuration, then the system converges to an optimal legitimate configuration. Sayaka Kamei, from Hiroshima University in Japan, gave a talk about: An Asynchronous Self-Stabilizing 6-Approximation for the Minimum Connected Dominating Set with Safe Convergence, in which she provided the first asynchronous self-stabilizing (6+e)-approximation algorithm with safe convergence for the minimum connected dominating set (MCDS). Her algorithm has a self-stabilization phase of one round, and a safe-convergence phase of O(n) rounds.

In the session on ad-hoc, sensor, and mobile networks, there was an interesting talk about counting and naming nodes in anonymous unknown dynamic networks. A network is anonymous when initially, all nodes don’t have ids.   The network is unknown if the nodes have no priori knowledge of the network in terms of network topology and network size. In the counting problem, the objective is to determine the network size. In naming, a unique identifier is assigned to each node. Othon Michail, from Computer Technology Institute in Greece, considered dynamic networks with broadcast. He showed interesting impossibility results on the problems of counting and naming. In particular, he showed that counting is impossible without a leader, and that naming is impossible to solve even with a leader, and even if the network size is known to all nodes.

Two other interesting problems were discussed in the workshop: the exploration problem and the estimation of average network degree. In the exploration problem, a set of robots is required to explore a finite space. The space to explore is partitioned into a finite number of locations represented by a graph. The nodes represent the locations, and the edges represent the possible movements of robots between the nodes. In the estimation of average network degree, the objective is to estimate the average degree of nodes in a given network.

Anissa Lamani, from Universite de Picardie Jules Verne Amiens in France, discussed the terminating exploration problem in her paper, Ring Exploration by Oblivious Robots having Vision Limited to 2 or 3. The terminating exploration problem requires the following: 1) each node is occupied by at most one robot in the initial configuration, and 2) every node eventually has to be visited by at least one robot; and then all robots must stop moving. She assumed that the robots are oblivious (memoryless) and all robots follow the same algorithm. Further, there is no communication among the robots; however, each robot has an electronic eye-sensor to see the other robots located on the nodes. She assumed that every robot is myopic in the sense that it has a limited visibility in terms of the path length from its location to any other location. In other words, if the limited visibility, ϕ = 1, then each robot can see the robots on its location and on its neighbors; and if ϕ = 2, then the visibility of each robot is extended to the neighbors of its neighbors. She studied this problem on ring networks. She presented two algorithms to solve this problem, one algorithm for ϕ = 2 and the other one for ϕ = 3. Moreover, she argued that there is no deterministic algorithm solving this problem if the robots are not initially close enough.

For the estimation of the average network degree, Hironobu Kanzaki, from Nagoya Institute of Technology in Japan, discussed estimating the average degree of a network particularly for dynamic networks. Naïvely, each node sends a message containing its degree to a centralized party, which calculates the average network degree. This has a message cost of O(n). Kanzaki discussed developing an approximation algorithm based on the concept of property testing, which reduces communication cost to o(n). In particular, his algorithm makes use of the Goldreich and Ron algorithm in the setting of distributed computing.

Beside these scientific contents, I have a few comments about Osaka city. Osaka is a beautiful city in Japan, where it has many skyscrapers that have ~40 floors. It is fascinating to see the view of this city from Osaka-sky building. A few pictures are attached here to show the beauty of Osaka and a near city, Kyoto.

Osaka – Japan, in the evening, from Osaka-Sky building:

Kyoto – Japan, Golden Pavilion, afternoon: