Dan Rubenstein's Distributed Replica/Tasking Research

Return to main research page

Replication of a configuration, task, or data is common in distributed network systems, especially as they grow large, making centralized solutions unscalable (and non-resilient!). Consider the following two examples of where replication occurs:

In the first example, given limited buffer space, the goal is to distribute content so that each content is reached in a short distance from an arbitrary starting point. In the second example, the goal is to keep two competing nodes that are near one another (and hence likely to interfere) assigned to different channels when possible.

We generalized this problem to a non-traditional graph coloring problem, where the goal is to assign a fixed number k of colors to nodes such that

While these optimization problems are not identical, it turns out that their goals are similar: to have a good "mix" of colors inside the network.

In [KR03], we created a distributed algorithm and associated protocol where each node chooses its own color, greedily changing its color whenever it wants to whatever best suits it locally. We prove that this process converges such that all nodes are "happy" with their own color, and prove that the resulting coloring is within a constant factor 3 from the optimal solution. This work is extended in [KR05], and is extended to a mesh network application setting in [KPMR05].



Return to main research page