Dr Amitabh Trehan's Outputs (36)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty (2024)
Presentation / Conference Contribution
Bampis, E., Dogeas, K., Erlebach, T., Megow, N., Schlöter, J., & Trehan, A. (2024, August). Competitive Query Minimization for Stable Matching with One-Sided Uncertainty. Presented at International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024), London, UK

We study the two-sided stable matching problem with one-sided uncertainty for two sets of agents A and B, with equal cardinality. Initially, the preference lists of the agents in A are given but the preferences of the agents in B are unknown. An algo... Read More about Competitive Query Minimization for Stable Matching with One-Sided Uncertainty.

All You Need are Random Walks: Fast and Simple Distributed Conductance Testing (2024)
Presentation / Conference Contribution
Batu, T., Trehan, A., & Trehan, C. (2024, May). All You Need are Random Walks: Fast and Simple Distributed Conductance Testing. Presented at SIROCCO 2024: 31st International Colloquium On Structural Information and Communication Complexity, Vietri sul Mare, Salerno, Italy

We propose a simple and time-optimal algorithm for property testing a graph for its conductance in the CONGEST model. Our algorithm takes only O(log n) rounds of communication (which is known to be optimal), and consists of simply running multiple ra... Read More about All You Need are Random Walks: Fast and Simple Distributed Conductance Testing.

Intrusion Detection in Critical SD-IoT Ecosystem (2023)
Presentation / Conference Contribution
Algamdi, H., Aujla, G. S., Jindal, A., & Trehan, A. (2023). Intrusion Detection in Critical SD-IoT Ecosystem. In 2023 IEEE International Conference on Communications Workshops (ICC Workshops). https://doi.org/10.1109/iccworkshops57953.2023.10283685

The Internet of Things (IoT) connects physical objects with intelligent decision-making support to exchange information and enable various critical applications. The IoT enables billions of devices to connect to the Internet, thereby collecting and e... Read More about Intrusion Detection in Critical SD-IoT Ecosystem.

Termination of amnesiac flooding (2023)
Journal Article
Hussak, W., & Trehan, A. (2023). Termination of amnesiac flooding. Distributed Computing, 36(2), 193-207. https://doi.org/10.1007/s00446-023-00448-y

We consider a stateless ‘amnesiac’ variant of the stateful distributed network flooding algorithm, expanding on our conference papers [PODC’19, STACS’20]. Flooding begins with a set of source ‘initial’ nodes I seeking to broadcast a message M in roun... Read More about Termination of amnesiac flooding.

Payment scheduling in the Interval Debt Model (2023)
Presentation / Conference Contribution
Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023, January). Payment scheduling in the Interval Debt Model. Presented at 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023), Novy Smokovec, Slovakia

The networks-based study of financial systems has received considerable attention in recent years, but seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view, and we introd... Read More about Payment scheduling in the Interval Debt Model.

Fully Compact Routing in Low Memory Self-Healing Trees (2020)
Presentation / Conference Contribution
Castañeda, A., Lefévre, J., & Trehan, A. (2020). Fully Compact Routing in Low Memory Self-Healing Trees. . https://doi.org/10.1145/3369740.3369786

On the Termination of Flooding (2020)
Presentation / Conference Contribution
Hussak, W., & Trehan, A. (2020). On the Termination of Flooding. In C. Paul, & M. Bläser (Eds.), . https://doi.org/10.4230/lipics.stacs.2020.17

DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead (2020)
Presentation / Conference Contribution
Gilbert, S., Pandurangan, G., Robinson, P., & Trehan, A. (2020). DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead. . https://doi.org/10.1145/3382734.3405716

On Termination of a Flooding Process (2019)
Presentation / Conference Contribution
Hussak, W., & Trehan, A. (2019). On Termination of a Flooding Process. . https://doi.org/10.1145/3293611.3331586

On The Termination of a Flooding Process (2019)
Journal Article
Hussak, W., & Trehan, A. (2019). On The Termination of a Flooding Process

Self-healing Routing and Other Problems in Compact Memory (2018)
Journal Article
Castañeda, A., Lefèvre, J., & Trehan, A. (2018). Self-healing Routing and Other Problems in Compact Memory

Compact routing messages in self-healing trees (2018)
Journal Article
Castañeda, A., Dolev, D., & Trehan, A. (2018). Compact routing messages in self-healing trees. Theoretical Computer Science, 709, 2 - 19. https://doi.org/10.1016/j.tcs.2016.11.022

DEX: self-healing expanders (2016)
Journal Article
Pandurangan, G., Robinson, P., & Trehan, A. (2016). DEX: self-healing expanders. Distributed Computing, 29(3), 163-185. https://doi.org/10.1007/s00446-015-0258-3

On the Complexity of Universal Leader Election (2015)
Journal Article
Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., & Trehan, A. (2015). On the Complexity of Universal Leader Election. Journal of the ACM, 62(1), 7:1-7:27

Sublinear bounds for randomized leader election (2015)
Journal Article
Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., & Trehan, A. (2015). Sublinear bounds for randomized leader election. Theoretical Computer Science, 561, 134 - 143. https://doi.org/10.1016/j.tcs.2014.02.009

Xheal: a localized self-healing algorithm using expanders (2014)
Journal Article
Pandurangan, G., & Trehan, A. (2014). Xheal: a localized self-healing algorithm using expanders. Distributed Computing, 27(1), 39-54. https://doi.org/10.1007/s00446-013-0192-1

Towards Self-healing SDN (2014)
Presentation / Conference Contribution
Chockler, G., & Trehan, A. (2014). Towards Self-healing SDN.

DEX: Self-Healing Expanders (2014)
Presentation / Conference Contribution
Pandurangan, G., Robinson, P., & Trehan, A. (2014). DEX: Self-Healing Expanders. . https://doi.org/10.1109/ipdps.2014.78

On the Complexity of Universal Leader Election (2013)
Presentation / Conference Contribution
Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., & Trehan, A. (2013). On the Complexity of Universal Leader Election.

Sublinear Bounds for Randomized Leader Election (2013)
Presentation / Conference Contribution
Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., & Trehan, A. (2013). Sublinear Bounds for Randomized Leader Election.

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

Edge-preserving self-healing: keeping network backbones densely connected (2012)
Presentation / Conference Contribution
Das Sarma, A., & Trehan, A. (2012). Edge-preserving self-healing: keeping network backbones densely connected.

Brief announcement: maintaining large dense subgraphs on dynamic networks (2012)
Presentation / Conference Contribution
Das Sarma, A., Lall, A., Nanongkai, D., & Trehan, A. (2012). Brief announcement: maintaining large dense subgraphs on dynamic networks.

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

Composition Games for Distributed Systems: the EU Grant games (Abstract) (2012)
Presentation / Conference Contribution
Kutten, S., Lavi, R., & Trehan, A. (2012). Composition Games for Distributed Systems: the EU Grant games (Abstract).

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.

Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information (2011)
Presentation / Conference Contribution
King, V., Lonargan, S., Saia, J., & Trehan, A. (2011). Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information.

Xheal: localized self-healing using expanders (2011)
Presentation / Conference Contribution
Pandurangan, G., & Trehan, A. (2011). Xheal: localized self-healing using expanders.

Brief Announcement: Composition Games for Distributed Systems: The EU Grants Games (2011)
Presentation / Conference Contribution
Kutten, S., Lavi, R., & Trehan, A. (2011). Brief Announcement: Composition Games for Distributed Systems: The EU Grants Games.

Composition Games for Distributed Systems: the EU Grant games (2011)
Other
Kutten, S., Lavi, R., & Trehan, A. (2011). Composition Games for Distributed Systems: the EU Grant games

Composition Games for Distributed Systems: The EU Grants Games (2011)
Presentation / Conference Contribution
Kutten, S., Lavi, R., & Trehan, A. (2011, September). Composition Games for Distributed Systems: The EU Grants Games. Presented at Distributed algorithms

Algorithms for self-healing networks (2010)
Thesis
Trehan, A. (2010). Algorithms for self-healing networks. (Thesis). University of New Mexico. Retrieved from https://durham-repository.worktribe.com/output/1617890

The forgiving graph: a distributed data structure for low stretch under adversarial attack (2009)
Presentation / Conference Contribution
Hayes, T. P., Saia, J., & Trehan, A. (2009). The forgiving graph: a distributed data structure for low stretch under adversarial attack.

The forgiving tree: a self-healing distributed data structure (2008)
Presentation / Conference Contribution
Hayes, T., Rustagi, N., Saia, J., & Trehan, A. (2008). The forgiving tree: a self-healing distributed data structure.

Picking up the Pieces: Self-Healing in reconfigurable networks (2008)
Presentation / Conference Contribution
Saia, J., & Trehan, A. (2008). Picking up the Pieces: Self-Healing in reconfigurable networks.

Sublinear bounds for randomized leader election
Journal Article
Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., & Trehan, A. (online). Sublinear bounds for randomized leader election. Theoretical Computer Science, -