Search

In sensor networks, correct clocks have arbitrary starting offsets and nondeterministic fluctuating skews. We consider an adversary that aims at tampering with the clock synchronization by intercepting messages, replaying intercepted messages (after the adversary’s choice of delay), and capturing nodes (i.e., revealing their secret keys and impersonating them). We present an efficient clock sampling algorithm which tolerates attacks by this adversary, collisions, a bounded amount of losses due to ambient noise, and a bounded number of captured nodes that can jam, intercept, and send fake messages. The algorithm is self-stabilizing, so if these bounds are temporarily violated, the system can efficiently stabilize back to a correct state. Using this clock sampling algorithm, we construct the first self-stabilizing algorithm for secure clock synchronization in sensor networks that is resilient to the aforementioned adversarial attacks.

The matching problem asks for a large set of disjoint edges in a graph. It is a problem that has received considerable attention in both the sequential and the self-stabilizing literature. Previous work has resulted in self-stabilizing algorithms for computing a maximal (12-approximation) matching in a general graph, as well as computing a 23-approximation on more specific graph types. In this paper, we present the first self-stabilizing algorithm for finding a 23-approximation to the maximum matching problem in a general graph. We show that our new algorithm, when run under a distributed adversarial daemon, stabilizes after at most O(n2) rounds. However, it might still use an exponential number of time steps.