Coalescing-branching random walks, or cobra walks for short, are a natural variant of random walks on graphs that can model the spread of disease through contacts or the spread of information in networks. In a k-cobra walk, at each time step a subset of the vertices are active; each active vertex chooses k random neighbors (sampled independently and uniformly with replacement) that become active at the next step, and these are the only active vertices at the next step. A natural quantity to study for cobra walks is the cover time, which corresponds to the expected time when all nodes have become infected or received the disseminated information.

Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy churn (i.e., Nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a constant degree graph with high expansion even under continuous high adversarial churn. Our protocol can tolerate a churn rate of up to O(n/polylog(n)) per round (where n is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only O(polylog(n)) overhead for topology maintenance: only polylogarithmic(in n) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.

Summary The Area of a schedule Σ for a directed acyclic graph (DAG) is a quality metric that measures the rate at which Σ renders 's nodes eligible for execution. Specifically, AREA(Σ) is the average number of nodes of that are eligible for execution as Σ executes node by node. Extensive simulations suggest that, for many distributions of processor availability and power, DAG‐schedules having larger Areas execute DAGs faster on platforms that are dynamically heterogeneous: the platform's processors change power and availability status in unpredictable ways and at unpredictable times. (Clouds and desktop grids exemplify such platforms.) While Area‐maximal schedules can provably be found for everyDAG, efficient generators of such schedules are known only for families of well‐structured DAGs. Our first result shows that the problem of crafting Area‐maximal schedules for general DAGs is NP‐complete, hence likely computationally intractable. We also provide an efficient algorithm that approximates optimal Area to within a factor of , where n is the number of tasks in the DAG—a factor that is likely interesting only for small DAGs. The lack of efficient Area‐maximizing schedulers for general DAGs has instigated the development of several heuristics for producing DAG‐schedules that have large Areas. We propose a novel polynomial‐time heuristic that produces schedules having quite large Areas; the heuristic is based on the Sidney decomposition of a DAG. (1) Simulations on DAGs having random structure yield the following results. The SIDNEY heuristic produces schedules whose Areas: (a) are at least 85% of maximal; and (b) are at least 1.25 times greater than previously known heuristics. (2) Simulations on DAGs having the structure of random LEGO®;DAGs (as formulated in earlier studies) indicate that the schedules produced by the SIDNEY heuristic have Areas that are at least 1.5 times greater than previously known heuristics. The ‘85%’ result is obtained from formulating the Area‐maximization problem as a linear program (LP); the Areas of DAG‐schedules produced by the SIDNEY heuristic are at least 85% of the Area value produced by the (unrounded) LP. (3) The reported results on random DAGs are essentially matched by a second heuristic, which produces DAG‐schedules by rounding the results of the LP formulation. Copyright © 2015 John Wiley & Sons, Ltd.

We study a distributed randomized information propagation mechanism in networks we call the coalescing-branching random walk (cobra walk, for short). A cobra walk is a generalization of the well-studied "standard" random walk, and is useful in modeling and understanding the Susceptible-Infected Susceptible (SIS)-type of epidemic processes in networks. It can also be helpful in performing light-weight information dissemination in resource-constrained networks. A cobra walk is parameterized by a branching factor k. The process starts from an arbitrary node, which is labeled active for step 1. (For instance, this could be a node that has a piece of data, rumor, or a virus.) In each step of a cobra walk, each active node chooses k random neighbors to become active for the next step ("branching"). A node is active for step t + 1 only if it is chosen by an active node in step t ("coalescing"). This results in a stochastic process in the underlying network with properties that are quite different from both the standard random walk (which is equivalent to the cobra walk with branching factor 1) as well as other gossip-based rumor spreading mechanisms.