[Colloq] Reminder - Colloquium **NOW** 366 WVH - Miroslaw Kutylowski

[Rachel Kalweit]

College of Computer and Information Science Colloquium

presents
Miroslaw Kutylowski
Wroclaw University of Technology, Poland

who will speak on:
Adversary Immune Communication Algorithms in Ad Hoc Networks


Friday, October 1, 2004
3:30pm
366 West Village H
Northeastern University


ABSTRACT

We consider self-organization algorithms for ad-hoc networks with a 
single, shared communication channel.  In such networks messages sent by 
different units at the same time collide and no message comes through. 
We even assume that collisions in the shared channel cannot be detected 
by the stations participating in the self-organization protocol (no-CD 
model).

Most of the algorithms constructed so far disregard the fact that faults 
can occur in the radio channel, or even worse, an adversary can send 
messages aiming to cause collisions and in this way degrade 
functionality of the network.  So we are interested in algorithms that 
work in the presence of an adversary, who knows the algorithm executed 
and may try to disturb its execution or to make it faulty.  Usually, 
parallel algorithms have certain ``hot spots'', where some crucial 
messages are exchanged.  This gives opportunities for an adversary, who 
may attack only these hot spots. So, we have to reconsider design of 
self-organization algorithms of such networks. Ideally, such algorithms 
should be homogeneous in the sense that there are no volnurable points 
in the algorithm execution.

We present an initialization algorithm which assigns consecutive numbers 
to N participating units.  Our algorithm has time complexity O(N) and 
energy cost O(sqrt(log(N)).  It succeeds with probability 
1-2^(Omega(sqrt(log(N)))) in presence of an adversary, who has energy 
cost Theta(log(N)). (Joint work with W. Rutkowski.)

Host: Rajmohan Rajaraman