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

Hayes, Thomas P.; Saia, Jared; Trehan, Amitabh

doi:10.1007/s00446-012-0160-1

All Outputs (6)

Self-healing using virtual structures (2012)
Journal Article
Trehan, A. (2012). Self-healing using virtual structures

Dense Subgraphs on Dynamic Networks (2012)
Book Chapter
Das Sarma, A., Lall, A., Nanongkai, D., & Trehan, A. (2012). Dense Subgraphs on Dynamic Networks. In M. Aguilera (Ed.), Distributed Computing (151-165). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-33651-5_11

Edge-preserving self-healing: keeping network backbones densely connected (2012)
Presentation / Conference Contribution
Das Sarma, A., & Trehan, A. (2012, December). Edge-preserving self-healing: keeping network backbones densely connected. Presented at Workshop on Network Science for Communication Networks (NetSciCom 2012), IEEE InfoComm

Brief announcement: maintaining large dense subgraphs on dynamic networks (2012)
Presentation / Conference Contribution
Das Sarma, A., Lall, A., Nanongkai, D., & Trehan, A. (2012, December). Brief announcement: maintaining large dense subgraphs on dynamic networks. Presented at ACM Symposium on Principles of Distributed Computing, PODC '12, July 16-18, 2012, Funchal, Madeira, Portugal

Composition Games for Distributed Systems: the EU Grant games (Abstract) (2012)
Presentation / Conference Contribution
Kutten, S., Lavi, R., & Trehan, A. (2012, December). Composition Games for Distributed Systems: the EU Grant games (Abstract). Presented at Workshop on the Economics of Networks, Systems and Computation (NetEcon 2012), IEEE InfoComm

The Forgiving Graph: a distributed data structure for low stretch under adversarial attack (2012)
Journal Article
Hayes, T. P., Saia, J., & Trehan, A. (2012). The Forgiving Graph: a distributed data structure for low stretch under adversarial attack. Distributed Computing, 25, 261–278. https://doi.org/10.1007/s00446-012-0160-1

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 arbitra... Read More about The Forgiving Graph: a distributed data structure for low stretch under adversarial attack.