 |
 FCT 2009
17th International Symposium on
Fundamentals of Computation Theory
September 2-4, 2009, Wrocław, Poland
August 31, building C-11, room P01
-
1700-1800
Stefan Schmid, Universität Paderborn,
Bad Vibes in Open Airwaves
Abstract.
In this talk I report on our recent research on jamming-resistant MAC protocols. I will present a very simple randomized algorithm called "AntiJam" that allows nodes to adapt their sending probabilities quickly. AntiJam avoids collisions due to interference, and achieves a high throughput despite a powerful, adaptive adversary jamming a large fraction of all time steps.
We first study the performance of AntiJam on completely connected graphs, and then present a variation of the protocol that is suitable for multi-hop networks modelled as Unit Disk graphs.
September 1, building C-11, room P01
-
1600-1700
Stefan Schmid, Universität Paderborn,
How to design robust networks? Connect to the seniors!
Abstract.
This talk shows how to build and maintain a distributed
heap which we call SHELL. In contrast to standard heaps, our heap
is oblivious in the sense that its structure only depends on the nodes
currently in the network but not on the past. This allows for fast join
and leave operations which is desirable in open distributed systems with
high levels of churn and frequent faults. In fact, a node fault or departure
can be fixed in SHELL in a constant number of communication
rounds, which significantly improves the best previous bound for distributed
heaps. SHELL has interesting applications. First, we describe a
robust distributed information system which is resilient to Sybil attacks
of arbitrary scale. Second, we show how to organize heterogeneous nodes
of arbitrary non-uniform capabilities in an overlay network such that the
paths between any two nodes do not include nodes of lower capacities.
This property is useful, e.g., for streaming. All these features can be
achieved without sacrificing scalability: our heap has a de Bruijn like
topology with node degree O(log^2 n) and network diameter O(log n), n
being the total number of nodes in the system.
September 2, building D-1, room 215
-
1230-1315
Stefan Schmid, Universität Paderborn,
A Solution for the Past Insider Problem
Abstract.
In this talk we consider the problem of designing an information system that is resilient to a denial of service attack. Our system evolves over time, in such a way that even a fired system administrator (a past insider) is not able to block specific contents anymore. Although the adversary can block a constant fraction of the machines, our solution requires a polylogarithmic redundancy only to achieve robustness.
|