
FCT 2009
17th International Symposium on Fundamentals of Computation Theory
September 24, 2009, Wrocław, Poland
August 31, building C11, room P01

14^{00}17^{00}
YvonneAnne Pignolet, ETH Zurich,
Game theory and networking
Abstract.
Game theory studies the interaction of multiple agents. The basic
assumption is that the agents are rational and pursue some well
defined objectives taking into account their knowledge or expectations
of the other agents' behavior. Many applications of game theory are
related to economics, but it has been applied to numerous fields
ranging from law enforcement to voting decisions.
Since the participants in a network might not always follow their
protocols and make selfish decisions, game theory offers tools to
develop analytical models of node behavior and predict the impact of
different protocols and policies on that behavior. Moreover, game
theory can help to design systems offering appropriate incentives for
the participants to behave in ways constructive to the network as a
whole.
In the first part, I'll introduce important concepts of game
theory, whereas the second part focuses on the application of game
theory to distributed and networking problems.
September 1, building C11, room P01

9^{00}12^{00}
YvonneAnne Pignolet, ETH Zurich,
Scheduling in the SINR model
Abstract.
The characteristics of wireless communication pose a few challenges
not present in wired networks.
Mutual interference impairs the quality of received signals and might
even prevent the correct reception of
messages. Efficient power control and scheduling algorithms that
coordinate when the nodes transmit are therefore essential for the
operation of wireless networks. I present the physical
signaltonoiseplusinterference model and explain scheduling
algorithms and complexity results in this model.
More precisely, I'll prove that scheduling NPhard and I propose
efficient approximation algorithms constructing a schedule for the
users. If nodes can adjust their transmission power level, there are
communication requests that can be scheduled concurrently even though
a uniform power assignment would have caused too much interference for
simultaneous transmission. I compare the capacity of networks with
uniform transmission power to networks where the power level can
differ from node to node. Subsequently, we'll study algorithms that
compute a schedule and power assignment with a proven worst case
guarantee.
September 2, building D1, room 215

11^{00}12^{30}
YvonneAnne Pignolet, ETH Zurich,
Device Discovery and DelaySensitive Aggregation in Wireless Networks
Abstract.
Efficient device discovery is a fundamental problem in wireless networks. Before a node can perform any particular task, it has to explore its vicinity for potential communication partners and resources. The duration until two devices meet is affected by deliberate and accidental interference. In this talk, we consider an adversary who disrupts the communication of our protocol in an arbitrary fashion. I present discovery algorithms with the twofold objective of allowing devices to find each other quickly in the absence of interference and degrading gracefully under adversarial jamming.
Once a number of devices has been able to establish a network, energyefficient algorithms accomplishing the network's tasks are required. The power consumption of the communication subsystem is often orders of magnitudes larger than the energy used for data processing. Hence, the easiest way to save energy is to reduce the number of transmissions. Whereas this idea leads to economical algorithms, we usually also want our algorithms to be fast and report results quickly, a goal that can only be reached with a frequent exchange of messages. In other words, we often face a tradeoff between speed and energy expenditure. In the second part of this talk, I address an aggregation problem where nodes have to forward messages to the root. I present an algorithm, that is simple enough to be implemented on sensor nodes and features optimal performance
guarantees.
