We study Byzantine agreement in dynamic networks where topology can change from round to and nodes also experience heavy churn (i.e., join leave the network continuously over time). Our main contributions are randomized distributed algorithms that achieve almost-everywhere with high probability even under a large number of adaptively chosen continuous adversarial rounds is polylogarithmic n (where stable size). show our essentially optimal (up factors) respect amount rate they tolerate by...

Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms fundamental agreement problem. P2P networks are that experience heavy node churn (i.e., nodes join leave network continuously over time). Our goal is to design (running a small number of rounds) guarantee, despite high rate, almost all reach stable agreement. main contributions randomized guarantee almost-everywhere with probability even under adversarial...

We introduce a new problem in the domain of mobile robots, which we term dispersion. In this problem, n robots are placed an node graph arbitrarily and must coordinate with each other to reach final configuration such that exactly one robot is at node. study through lenses minimizing memory required by number rounds achieve

We consider the problem of selecting threshold times to transition a device low-power sleep states during an idle period. The two-state case in which there is single active and state continuous version ski-rental problem. generalized more than one state, each with its own power consumption rate costs. give algorithm that, given system, produces deterministic strategy whose competitive ratio arbitrarily close optimal. also produce optimal online system probability distribution that generates...

We consider the problem of selecting threshold times to transition a device low-power sleep states during an idle period. The two-state case, in which there is single active and state, continuous version ski-rental problem. generalized more than one each with its own power-consumption rate costs. give algorithm that, given system, produces deterministic strategy whose competitive ratio arbitrarily close optimal. also produce optimal online system probability distribution that generates...

We study robust and efficient distributed algorithms for searching, storing, maintaining data in dynamic Peer-to-Peer (P2P) networks. P2P networks are highly that experience heavy node churn (i.e., nodes join leave the network continuously over time). Our goal is to guarantee, despite high rate, a large number of can store, retrieve, maintain items. main contributions fast randomized guarantee above with probability even under adversarial churn. In particular, we present following results:

Previous chapter Next Full AccessProceedings Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Towards Robust and Efficient Computation in Dynamic Peer-to-Peer NetworksJohn Augustine, Gopal Pandurangan, Peter Robinson, Eli UpfalJohn Upfalpp.551 - 569Chapter DOI:https://doi.org/10.1137/1.9781611973099.47PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Motivated by need for robust fast distributed computation highly...

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 constructing maintaining network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy churn (i.e., Nodes joining leaving continuously over time). We assume that controlled an adversary has complete knowledge control of what nodes join leave...

In this work, we study the problem of dispersion mobile robots on dynamic rings. The n an node graph, introduced by Augustine and Moses Jr. [2], requires to coordinate with each other reach a configuration where exactly one robot is present node. This has real world applications applies whenever want minimize total cost agents sharing resources, located at various places, subject constraint that agent moving different resource comparatively much smaller than multiple (e.g. smart electric...

In this paper, we study distributed graph algorithms in networks which the nodes have a limited communication capacity. Many systems are built on top of an underlying networking infrastructure, for example by using virtual topology known as overlay network. Although network might allow each node to directly communicate with large number other nodes, amount that can perform fixed time is typically much more limited. We introduce Node-Capacitated Clique model abstract model, allows us effect...

research-article Share on Distributed Algorithmic Foundations of Dynamic Networks Authors: John Augustine IIT Madras, Chennai, India IndiaView Profile , Gopal Pandurangan University Houston, TX TXView Peter Robinson Royal Holloway, London, UK UKView Authors Info & Claims ACM SIGACT NewsVolume 47Issue 1March 2016 pp 69–98https://doi.org/10.1145/2902945.2902959Published:10 March 2016Publication History 15citation327DownloadsMetricsTotal Citations15Total Downloads327Last 12 Months20Last 6...

In this paper, we demonstrate that disproportionate gains are possible through a simple devise for injecting inexactness or approximation into the hardware architecture of computing system with general purpose template including complete memory hierarchy. The focus study is on energy savings approach in context large and challenging applications. We choose two such from different ends spectrum---the IGCM model weather climate modeling which embodies significant features high-performance...

An important task in the analysis of multiagent systems is to understand how groups selfish players can form coalitions, i.e., work together teams. In this paper, we study dynamics coalition formation under bounded rationality. We consider settings whereby each team's profit given by a submodular function and propose three profit-sharing schemes, which based on concept marginal utility. The agents are assumed be myopic, they keep changing teams as long increase their payoff doing so....

A Peer-to-Peer (P2P) network is a dynamic collection of nodes that connect with each other via virtual overlay links built upon an underlying (usually, the Internet). Typical P2P networks are highly and can experience very heavy churn, i.e., large number join/leave every time step. We present framework called Sparse Robust Addressable Network (Spartan) tolerate adversarial churn. show Spartan be efficiently in fully distributed manner within O(log n) rounds. Furthermore, structure...

In this paper, we address the problem of probe station selection. Probe nodes are that instrumented with functionality sending probes and analyzing results. The placement stations affects diagnosis capability sent by stations. also involves overhead instrumentation. Thus it is important to minimize required number without compromising on probes. selection detect failures in network. We present an algorithm for using a reduction Minimum Hitting Set problem. several issues involved while...

A dynamic path network is an undirected with evacuees situated at each vertex. To evacuate the path, travel towards a designated sink (doorway) to exit. Each edge has capacity, number of that can enter in unit time. Congestion occurs if evacuee wait vertex for other leave first. The basic problem place k sinks on line, associated evacuation strategy, so as minimize total time needed everyone. minmax-regret version introduces uncertainty into input, vertices only being specified within range....

We study robust and efficient distributed algorithms for building maintaining data structures in dynamic Peer-to-Peer (P2P) networks. P2P networks are characterized by a high level of dynamicity with abrupt heavy node \emph{churn} (nodes that join leave the network continuously over time). present novel algorithm builds maintains probability skip list $poly(n)$ rounds despite $\mathcal{O}(n/\log n)$ churn \emph{per round} ($n$ is stable size). assume controlled an oblivious adversary (that...