BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Amitabh Trehan

Amitabh Trehan contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster ComputingData Structures and AlgorithmsNetworking and Internet ArchitectureComputer Science and Game Theorycs.CYDiscrete Mathematics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2020arXiv

Terminating cases of flooding

Basic synchronous flooding proceeds in rounds. Given a finite undirected (network) graph $G$, a set of sources $I \subseteq G$ initiate flooding in the first round by every node in $I$ sending the same message to all of its neighbours. In each subsequent round, nodes send the message to all of their neighbours from which they did not receive the message in the previous round. Flooding terminates when no node in $G$ sends a message in a round. The question of termination has not been settled - rather, non-termination is implicitly assumed to be possible. We show that flooding terminates on every finite graph. In the case of a single source $g_0$, flooding terminates in $e$ rounds if $G$ is bipartite and $j$ rounds with $e < j \leq e+d+1$ otherwise, where $e$ and $d$ are the eccentricity of $g_0$ and diameter of $G$ respectively. For communication/broadcast to all nodes, this is asymptotically time optimal and obviates the need for construction and maintenance of spanning structures. We extend to dynamic flooding initiated in multiple rounds with possibly multiple messages. The cases where a node only sends a message to neighbours from which it did not receive {\it any} message in the previous round, and where a node sends some highest ranked message to all neighbours from which it did not receive {\it that} message in the previous round, both terminate. All these cases also hold if the network graph loses edges over time. Non-terminating cases include asynchronous flooding, flooding where messages have fixed delays at edges, cases of multiple-message flooding and cases where the network graph acquires edges over time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Algorithms for Self-Healing Networks

Many modern networks are \emph{reconfigurable}, in the sense that the topology of the network can be changed by the nodes in the network. For example, peer-to-peer, wireless and ad-hoc networks are reconfigurable. More generally, many social networks, such as a company&#39;s organizational chart; infrastructure networks, such as an airline&#39;s transportation network; and biological networks, such as the human brain, are also reconfigurable. Modern reconfigurable networks have a complexity unprecedented in the history of engineering, resembling more a dynamic and evolving living animal rather than a structure of steel designed from a blueprint. Unfortunately, our mathematical and algorithmic tools have not yet developed enough to handle this complexity and fully exploit the flexibility of these networks. We believe that it is no longer possible to build networks that are scalable and never have node failures. Instead, these networks should be able to admit small, and maybe, periodic failures and still recover like skin heals from a cut. This process, where the network can recover itself by maintaining key invariants in response to attack by a powerful adversary is what we call \emph{self-healing}. Here, we present several fast and provably good distributed algorithms for self-healing in reconfigurable dynamic networks. Each of these algorithms have different properties, a different set of gaurantees and limitations. We also discuss future directions and theoretical questions we would like to answer. %in the final dissertation that this document is proposed to lead to.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Composition Games for Distributed Systems: the EU Grant games

We analyze ways by which people decompose into groups in distributed systems. We are interested in systems in which an agent can increase its utility by connecting to other agents, but must also pay a cost that increases with the size of the sys- tem. The right balance is achieved by the right size group of agents. We formulate and analyze three intuitive and realistic games and show how simple changes in the protocol can dras- tically improve the price of anarchy of these games. In partic- ular, we identify two important properties for a low price of anarchy: agreement in joining the system, and the possibil- ity of appealing a rejection from a system. We show that the latter property is especially important if there are some pre- existing constraints regarding who may collaborate (or com- municate) with whom.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

DEX: Self-healing Expanders

We present a fully-distributed self-healing algorithm DEX, that maintains a constant degree expander network in a dynamic setting. To the best of our knowledge, our algorithm provides the first efficient distributed construction of expanders --- whose expansion properties hold {\em deterministically} --- that works even under an all-powerful adaptive adversary that controls the dynamic changes to the network (the adversary has unlimited computational power and knowledge of the entire network state, can decide which nodes join and leave and at what time, and knows the past random choices made by the algorithm). Previous distributed expander constructions typically provide only {\em probabilistic} guarantees on the network expansion which {\em rapidly degrade} in a dynamic setting; in particular, the expansion properties can degrade even more rapidly under {\em adversarial} insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only $O(\log n)$ rounds and $O(\log n)$ messages are needed with high probability ($n$ is the number of nodes currently in the network). The algorithm requires only a constant number of topology changes. Moreover, our algorithm allows for an efficient implementation and maintenance of a distributed hash table (DHT) on top of DEX, with only a constant additional overhead. Our results are a step towards implementing efficient self-healing networks that have \emph{guaranteed} properties (constant bounded degree and expansion) despite dynamic changes.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Sublinear Bounds for Randomized Leader Election

This paper concerns {\em randomized} leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete $n$-node networks that runs in O(1) rounds and (with high probability) uses only $O(\sqrt{n}\log^{3/2} n)$ messages to elect a unique leader (with high probability). When considering the &#34;explicit&#34; variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite $n$-node graph $G$ in $O(τ(G))$ time and $O(τ(G)\sqrt{n}\log^{3/2} n)$ messages, where $τ(G)$ is the mixing time of a random walk on $G$. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient {\em deterministic} leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that $Ω(\sqrt n)$ messages are needed for any leader election algorithm that succeeds with probability at least $1/e + \eps$, for any small constant $\eps > 0$. We view our results as a step towards understanding the randomized complexity ofleader election in distributed networks.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Dense Subgraphs on Dynamic Networks

In distributed networks, it is often useful for the nodes to be aware of dense subgraphs, e.g., such a dense subgraph could reveal dense subtructures in otherwise sparse graphs (e.g. the World Wide Web or social networks); these might reveal community clusters or dense regions for possibly maintaining good communication infrastructure. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs that the member nodes are aware of. The only knowledge that the nodes need is that of the dynamic diameter $D$, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that ($2 + ε$)-approximate the densest subgraph and ($3 + ε$)-approximate the at-least-$k$-densest subgraph (for a given parameter $k$). Our algorithms work for a wide range of parameter values and run in $O(D\log_{1+ε} n)$ time. Further, a special case of our results also gives the first fully decentralized approximation algorithms for densest and at-least-$k$-densest subgraph problems for static distributed graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Self-healing systems and virtual structures

Modern networks are large, highly complex and dynamic. Add to that the mobility of the agents comprising many of these networks. It is difficult or even impossible for such systems to be managed centrally in an efficient manner. It is imperative for such systems to attain a degree of self-management. Self-healing i.e. the capability of a system in a good state to recover to another good state in face of an attack, is desirable for such systems. In this paper, we discuss the self-healing model for dynamic reconfigurable systems. In this model, an omniscient adversary inserts or deletes nodes from a network and the algorithm responds by adding a limited number of edges in order to maintain invariants of the network. We look at some of the results in this model and argue for their applicability and further extensions of the results and the model. We also look at some of the techniques we have used in our earlier work, in particular, we look at the idea of maintaining virtual graphs mapped over the existing network and assert that this may be a useful technique to use in many problem domains.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Edge-preserving self-healing: keeping network backbones densely connected

Healing algorithms play a crucial part in distributed P2P networks where failures occur continuously and frequently. Several self-healing algorithms have been suggested recently [IPDPS&#39;08, PODC&#39;08, PODC&#39;09, PODC&#39;11] in a line of work that has yielded gradual improvements in the properties ensured on the graph. This work motivates a strong general phenomenon of edge-preserving healing that aims at obtaining self-healing algorithms with the constraint that all original edges in the graph (not deleted by the adversary), be retained in every intermediate graph. The previous algorithms, in their nascent form, are not explicitly edge preserving. In this paper, we show they can be suitably modified (We introduce Xheal+, an edge-preserving version of Xheal[PODC&#39;11]). Towards this end, we present a general self-healing model that unifies the previous models. The main contribution of this paper is not in the technical complexity, rather in the simplicity with which the edge-preserving property can be ensured and the message that this is a crucial property with several benefits. In particular, we highlight this by showing that, almost as an immediate corollary, subgraph densities are preserved or increased. Maintaining density is a notion motivated by the fact that in certain distributed networks, certain nodes may require and initially have a larger number of inter-connections. It is vital that a healing algorithm, even amidst failures, respect these requirements. Our suggested modifications yield such subgraph density preservation as a by product. In addition, edge preservation helps maintain any subgraph induced property that is monotonic. Also, algorithms that are edge-preserving require minimal alteration of edges which can be an expensive cost in healing - something that has not been modeled in any of the past work.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Xheal: Localized Self-healing using Expanders

We consider the problem of self-healing in reconfigurable networks (e.g. peer-to-peer and wireless mesh networks) that are under repeated attack by an omniscient adversary and propose a fully distributed algorithm, Xheal that maintains good expansion and spectral properties of the network, also keeping the network connected. Moreover, Xheal does this while allowing only low stretch and degree increase per node. Thus, the algorithm heals global properties while only doing local changes and using only local information. Our work improves over the self-healing algorithms &#39;Forgiving tree&#39;[PODC 2008] and &#39;Forgiving graph&#39;[PODC 2009] (using a similar model) in that we are able to give guarantees on degree and stretch, while at the same time preserving the expansion and spectral properties of the network. These repairs preserve the invariants in the following sense. At any point in the algorithm, the expansion of the graph will be either `better&#39; than the expansion of the graph formed by considering only the adversarial insertions (not the adversarial deletions) or the expansion will be, at least, a constant. Also, the stretch i.e. the distance between any pair of nodes in the healed graph is no more than a $O(\log n)$ factor. Similarly, at any point, a node $v$ whose degree would have been $d$ in the graph with adversarial insertions only, will have degree at most $O(κd)$ in the actual graph, for a small parameter $κ$. We also provide bounds on the second smallest eigenvalue of the Laplacian which captures key properties such as mixing time, conductance, congestion in routing etc. Our distributed data structure has low amortized latency and bandwidth requirements.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

The Forgiving Graph: A distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick &#34;repairs,&#34; which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions, without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes $v$ and $w$ whose distance would have been $\ell$ in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most $\ell \log n$ in the actual graph, where $n$ is the total number of vertices seen so far. Similarly, at any point, a node $v$ whose degree would have been $d$ in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our algorithm is completely distributed and has low latency and bandwidth requirements.

0 citations0 reviewsNo code linkedOpen access