Published: 17th October 2013
DOI: 10.4204/EPTCS.132
ISSN: 2075-2180

EPTCS 132

Proceedings Ninth International Workshop on
Foundations of Mobile Computing
Jerusalem, Israel, October 17-18, 2013

Edited by: Keren Censor-Hillel and Valerie King

Preface
Invited Presentation: Dealing with Uncertainty in Wireless Communication
Fabian Kuhn
Invited Presentation: Reusable Teamwork for Multi-Robot Teams
Gal Kaminka
Distributed Queuing in Dynamic Networks
Gokarna Sharma and Costas Busch
1
Talk Announcement: Relative Throughput - Measuring the Impact of Adversarial Errors on Packet Scheduling Strategies
Antonio Fernández Anta, Chryssis Georgiou, Dariusz R. Kowalski, Joerg Widmer and Elli Zavou
20
Message and time efficient multi-broadcast schemes
Liron Levin, Dariusz R. Kowalski and Michael Segal
21
Robust Leader Election in a Fast-Changing World
John Augustine, Tejas Kulkarni, Paresh Nakhe and Peter Robinson
38
Talk Announcement: Jamming-Resistant Learning in Wireless Networks
Johannes Dams, Martin Hoefer and Thomas Kesselheim
50

Preface

FOMC is the International Workshop on Foundations of Mobile Computing, dedicated to all aspects that cover contributions both in the design and analysis of discrete/distributed algorithms, and in the system modeling of mobile, wireless and similarly dynamic networks. It aims to bring together the practitioners and theoreticians of the field to foster cooperation between research in mobile computing and algorithms. This volume contains the contributions presented at FOMC 2013, which was held during October 18 in Jerusalem, Israel.

This year, the workshop consisted of five contributed talks. Three were full papers and two were talks about results that have been published elsewhere or not yet completed.

In addition to the five contributed talks, the workshop featured two invited talks. The first was given by Fabian Kuhn from the University of Freiburg and was titled "Dealing with Uncertainty in Wireless Communication". The second was given by Gal Kaminka from Bar-Ilan University and was titled "Reusable Teamwork for Multi-Robot Teams".
October 2013 Keren Censor-Hillel
Valerie King


Dealing with Uncertainty in Wireless Communication

Fabian Kuhn (University of Freiburg)

Over the last 25 years, a variety of abstract models to deal with the characteristic properties of wireless communication have been proposed and many algorithms for wireless networks have been developed. The models range from simple graph-based characterizations of interference to more accurate so-called signal-to-noise-and-interference (SINR) models. As different as the considered models may be, most of them have one thing in common. Whether a node can successfully receive (and decode) a message is determined using some fixed, deterministic rule that depends on the structure of the network and some additional model parameters. Often correctness and performance guarantees of algorithms critically depend on such rigid rules and sometimes even on the fact that each node exactly knows certain model parameters or some other information about the network. In my talk, I will argue that such assumptions can be problematic and I will discuss some existing results and future directions to deal with inherent uncertainties in systems based on wireless communication.


Reusable Teamwork for Multi-Robot Teams

Gal Kaminka (Bar Ilan University)

For many years, multi-robot researchers have focused on specific application-inspired basic tasks (e.g., coverage, moving in formation, foraging, patrolling) as a way of studying cooperation between robots. But users want to see increasingly complex missions being tackled, which challenge this methodology: first, some missions cannot be easily decomposed into the familiar basic tasks, making previous knowledge non-reusable; second, the target operating environments challenge the typically sterile settings assumed in many previous works (such challenges include adversaries, multiple concurrent goals, human operators and users, and more).

In this talk, I will argue that the reusable components in complex missions are often found not in the tasks, but in the interactions between robots, i.e., that while taskwork varies significantly, teamwork is largely generic. And while many multi-robot researchers have begun exploring generic task-allocation methods, I will report on my group's work over the last decade, identifying and developing other general mechanisms for teamwork, and integrating them at the architecture level to facilitate development of robust teams at reduced programming effort. I will sample some of our results in developing robots for missions ranging from robust formation maintenance, through patrolling, to soccer and urban search-and-rescue.


Relative Throughput - Measuring the Impact of Adversarial Errors on Packet Scheduling Strategies

Antonio Fernández Anta (Institute IMDEA Networks)
Chryssis Georgiou (University of Cyprus)
Dariusz R. Kowalski (University of Liverpool)
Joerg Widmer (Institute IMDEA Networks)
Elli Zavou (Institute IMDEA Networks)

In this talk we will explore the problem of achieving efficient packet transmission over unreliable wireless links with worst case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric for measuring the efficiency of scheduling strategies in such a setting. To this end, we propose a relative throughput metric which corresponds to the long term competitive ratio of the algorithm with respect to the optimal. Then, we will explore the impact of the error detection mechanism and feedback delay on our measure. We will compare instantaneous error feedback with deferred error feedback, that requires a faulty packet to be fully received in order to detect the error. We will also propose algorithms for worst-case adversarial and stochastic packet arrival models, and formally analyze their performance. The relative throughput achieved by these algorithms is then shown to be close to optimal by deriving lower bounds on the relative throughput of the algorithms and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of wireless communication systems in adverse environments.


Jamming-Resistant Learning in Wireless Networks

Johannes Dams
Martin Hoefer
Thomas Kesselheim

We consider capacity maximization in wireless networks under adversarial interference conditions. There are $n$ links, each consisting of a sender and a receiver, which repeatedly try to perform a successful transmission. In each time step, the success of attempted transmissions depends on interference conditions, which are captured by an interference model (e.g. the SINR model). Additionally, an adversarial jammer can render a $(1-\delta)$-fraction of time steps unsuccessful. For this scenario, we analyze a framework for distributed learning algorithms to maximize the number of successful transmissions. Our main result is an algorithm based on no-regret learning converging to an $O\left(1/\delta\right)$-approximation. It provides even a constant-factor approximation when the jammer exactly blocks a $(1-\delta)$-fraction of time steps. In addition, we consider a stochastic jammer, for which we obtain a constant-factor approximation after a polynomial number of time steps. We also consider more general settings, in which links arrive and depart dynamically. Our algorithms perform favorably in simulations.

A full version of the paper can be found online at http://arxiv.org/abs/1307.5290.