Global Robustness and Correctness in Massively Distributed Network Systems

06/26/2006
Speaker(s) : Dan RUBENSTEIN from Columbia University
Abstract Emerging networking systems, such as wireless ad-hoc and sensor networks, peer-to-peer and content distribution networks, and grid computing networks, are expected to be so large in scale that algorithms and protocols that operate in these systems must be fully distributed. This distribution makes it much harder to meet global system objectives, and makes it more difficult to protect the network from misbehaving or misconfigured nodes that may thwart correctness or performance of the protocol.
Our recent work has focused on fully distributed methods to meet global objective goals and to identify erratic system behavior. First, I will describe a self-configuring distributed algorithm designed for massively distributed settings that "spreads" replicated resources or tasks among nodes within a network.
Next, I will present our development of a theory that can be used to detect "misconfigured" nodes that improperly implement the desired distributed protocol. We show how this theory can be used to detect misconfigurations whenever they are detectable, and show some preliminary results in applying the theory to distance-vector and path-vector routing protocols.