Dr Amitabh Trehan's Outputs (37)

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.

DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead (2020)
Presentation / Conference Contribution
Gilbert, S., Pandurangan, G., Robinson, P., & Trehan, A. (2020, December). DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead. Presented at Proceedings of the 39th Symposium on Principles of Distributed Computing, New York, NY, USA

Fully Compact Routing in Low Memory Self-Healing Trees (2020)
Presentation / Conference Contribution
Castañeda, A., Lefévre, J., & Trehan, A. (2020, December). Fully Compact Routing in Low Memory Self-Healing Trees. Presented at Proceedings of the 21st International Conference on Distributed Computing and Networking, New York, NY, USA

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

Payment Scheduling in the Interval Debt Model (2024)
Journal Article
Stewart, I., Kutner, D., Friedetzky, T., Trehan, A., & Mertzios, G. (2025). Payment Scheduling in the Interval Debt Model. Theoretical Computer Science, 1028, Article 115028. https://doi.org/10.1016/j.tcs.2024.115028

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

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, May). Intrusion Detection in Critical SD-IoT Ecosystem. Presented at 2023 IEEE International Conference on Communications Workshops (ICC Workshops), Rome, Italy

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.

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.

On the Termination of Flooding (2020)
Presentation / Conference Contribution
Hussak, W., & Trehan, A. (2020, December). On the Termination of Flooding. Presented at 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Dagstuhl, Germany

On Termination of a Flooding Process (2019)
Presentation / Conference Contribution
Hussak, W., & Trehan, A. (2019, December). On Termination of a Flooding Process. Presented at Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., Totronto, ON, Canada

On The Termination of a Flooding Process (2019)
Preprint / Working Paper
Hussak, W., & Trehan, A. (2019). On The Termination of a Flooding Process

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

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

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

Towards Self-healing SDN (2014)
Presentation / Conference Contribution
Chockler, G., & Trehan, A. (2014, December). Towards Self-healing SDN. Presented at Distributed Software Defined Net- works (DSDN) workshop, Principles of Distributed Computing (PODC) 2014

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

DEX: Self-Healing Expanders (2014)
Presentation / Conference Contribution
Pandurangan, G., Robinson, P., & Trehan, A. (2014, December). DEX: Self-Healing Expanders. Presented at Proceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium, Washington, DC, USA

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