The workshop is going to take place on Friday Oct 18, 8:30am-1pm, at in Begin Center, located in Jerusalem.
- 8h30 Welcome & Opening
- 8h35-9h20 Merav Parter
Title: Computing on Anonymous Dynamic Networks
Abstract : The (static) behavior of the multi-station wireless network can be represented by a reception map. In the SINR model, the resulting SINR diagram partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. Our focus is on Algorithmic SINR, a newly emerging line of research that targets algorithm analysis in the physical SINR model. Dynamic aspects may appear in a wireless communication network on several levels:
(1) time dynamics, where stations may choose to transmit or keep silent, adjust their transmission power level, or even change their location from time to time;
(2) spatial dynamics, where the network changes over space; and
(3) behavioral dynamics, where stations behave as self-interested agents (e.g., strategies are essentially possible power settings at which to transmit).
In this talk we provide a brief introduction into the basic structural characteristics of SINR diagrams. It is our belief that these diagrams are fundamental to understanding the dynamics of wireless networks, and will play a key role in the development of suitable algorithms for such networks. In addition, we illustrate how spatial dynamics might arise in scenarios where receivers can employ a recently developed coding technique, namely, interference cancellation. Finally, we will discuss some properties of game dynamics in which each station acts as a self-interested agent aiming toward maximizing its transmission frequency.
- 9h20-10h05 Sébastien Tixeuil
Title: Performance evaluation of Self-stabilizing solutions for dynamic tasks.
Abstract : Self-stabilization is a versatile technique to recover from transient faults of arbitrary nature and extent. We discuss recent advances in practical performance evaluation of self-stabilizing solutions using techniques such as simulation and probabilistic model checking.
- 10h05-10h25 Break
- 10h25-11h10 Stefan Schmid
Title: Self-stabilizing and self-optimizing distributed datastructures
Abstract : In this talk, I will give an overview of our recent work on the design of robust and self-adjusting distributed systems, and especially overlay networks. I will discuss the “lessons learned” from our research over the past 5 years, and will develop a list of “design principles” and “common themes” that may be useful for future research. Moreover, I’ll introduce new metrics to study the performance of such distributed maintenance algorithms.
The talk will be structured around specific case studies: In particular, I will sketch an algorithm to self-stabilize a linear chain, a hypercube, and a Delaunay graph topology. In order to illustrate the concept of self-optimizing networks, I will examine a most simple Distributed Binary Search Tree, and discuss how to generalize classic datastructures such as Splay trees.
The content of the talk has been developed in several papers with different authors (Chen Avin, Riko Jacob, Andrea Richa, Christian Scheideler, Hanjo Täubig, etc.). - 11h10-11h55 Roberto Baldoni
Title: Computing on Anonymous Dynamic Networks
Abstract : Computing global properties of a distributed system, such as counting the nodes belonging to the system, is of primary importance in building applications that take decisions locally at each node based on global information. For example, making a distributed near-optimal load balancing among the nodes of the system cannot be computed without knowing the network size.
Recently, dynamic distributed systems have attracted a lot of interest, due to the fact that static ones do not capture anymore the new kind of software applications that are emerging, thanks to the diffusion of mobile devices, sensors networks, etc. Additionally, privacy concerns are becoming more and more important and they could be addressed considering models where processors do not have unique IDs. Thus the talk will address the problem of counting in distributed systems and it will focus on counting the size of anonymous dynamic networks. - 12h55-12h15 Break
- 12h15-13h00 Shay Kutten
Title: The cost of storage versus the cost of communication in dynamic content location
Abstract : The famous k-server problems considered k copies of some resource that can move from one location to another. When a demand for a server arrives at a location where the server was located, the cost of the service was zero. Otherwise, one of the servers had to be moved to that location, paying a cost equal to the distance between the old location of the server and the new one.
This heavily studied problem models just one version of movable resources. In the talk, we shall mention several other kinds of movable resources, motivate them, and give some informal intuition for the reasons why their solutions should be different. We shall then survey and describe several results, both published and yet unpublished ones