Subproject A1

Capabilities and limitations of local strategies in dynamic networks

This sub-project started in 2011 with the objective to explore the capabilities and limits of local methods for control and optimization of big dynamic networks. Our focus lies on overlay networks, which allow the interaction between actors of the OTF market (the clients) and service providers to support services and provide infrastructure. "Local" in this context means that the control and optimization is not performed by a central instance but distributed by the actors, based on their local information. In the first funding period, we focused our research on developing and analyzing algorithms, which e.g. allow the efficient search for services, the distributed organization of actors in groups, or to adapt the positioning of resources in an overlay to better serve the requirements of the clients.

In the second phase, we expand the focus of our research in two directions: Firstly, we deal with the dynamics of applications. For example, these dynamics manifests themselves as the fact that cooperation partner of an actor changes or the provided resources change. Supporting such dynamic interaction requirements needs a continuous adaptation of the overlay. Our focus lies on how we can answer changes of requirements with small modifications of the overlay. Secondly, we deal with external dynamics. Such dynamics are beyond the control of our algorithms. This could be faulty conditions or network load caused by foreign applications.

Specifically, the subproject is organized in the following working areas.

Complex Distributed Search

A 2-dimensional range query with tree overlay network embedded by a 2-dimensional Hilbertcurve

The functional and non-functional properties of a service can be modeled as a multidimensional feature vector. As the core task of the OTF market is to find appropriate services in a decentralized marked, we develop peer-to-peer systems that can deal with multidimensional queries on multidimensional feature vectors. This in particular includes range queries, objective function search and top-k queries. As different types of services may have different properties, the dimensionality of a newly added feature vector is arbitrary and unpredictable. To handle this in an efficient way is a new challenge for peer-to-peer systems. Our task here is to develop efficient solutions and to analyze their trade-offs concerning the messages complexity (the messages send in total to serve a query) and the response time (the number of hops of the longest path to serve a query) for various node degrees.

Dynamic Adaptation of Networks to Applications and User Behavior

In this area we want to develop methods that respond to dynamically changing user requirements by constantly adapting the overlay network so that the overlay better meets the user requirements. On the one hand, we research variants of network creation games, in which we model the user requirements in terms of a friendship graph, i.e., which users want to minimize the overlay network distance to each other. After focusing on static friendship graphs in the first period, we now want to shift our focus on dynamic friendship graphs, i.e., methods to react on changes in the friendship graph by (small) changes of the overlay. On the other hand, we consider self stabilizing methods for overlays. After providing an important result in the first period, which shows how one can efficiently construct a self stabilizing clique network, we want to look at more flexible and adaptive methods for self stabilizing networks, in particular self stabilizing publish-subscribe systems. Furthermore, we also consider dynamic adaptation problems for resource allocation questions, specifically by introducing the flexibility of leasing services for certain periods of time or changing the network topologies.

Study on the Impact of External Dynamics

In this area, network dynamics are beyond the control of the protocols we design. They are caused by external sources that can create faulty network states or a high network load. Specifically, we look at the influence of adversarial behaving (external) network dynamics on the complexity of basic problems, i.e., dynamics that try to prevent an efficient execution of algorithms. This rather pessimistic view on network dynamics allows us to develop robust algorithms that are guaranteed to provide accurate results even in critical situations.

Advancement of the OTF Market Infrastructure

Supplementing the theoretical analysis, we study the efficiency of our methods and the feasibility of the OTF market under realistic scenarios.

While our former focus was on feasibility, in the current phase we implement our newly developed methods to compare them with existing standard methods that are currently used. Here, a special attention is given to self-organizing methods for the search for services and publish-subscribe systems. To this end, the efficiency of our methods is benchmarked by using a simulator, which can simulate large markets of more than 10,000 participants allowing to evaluate the scalability of our approaches. Our goal is to draw conclusions from the behavior of our methods in the experimental evaluations and, if necessary, adapt them to the characteristics of the market. Important goals are to ensure the scalability, adaptivity and robustness of our methods.