Siddhartha Visveswara Jayanti
Siddhartha Jayanti is a Research Scientist at Google Cambridge. His research spans distributed computing, algorithms, machine learning, economics, security, and formal verification. Siddhartha earned his Ph.D. in Computer Science with a minor in Machine Learning from MIT, where his thesis on Simple, Fast, Scalable, and Reliable Multiprocessor Algorithms was advised by Julian Shun. He earned his Master's in EECS from MIT, where his thesis On Computing Nash Equilibria of Borel’s Colonel Blotto Game for Multiple Players including in Arbitrary Measure Spaces was advised by Costis Daskalakis. He received his Bachelor's in CS with a certificate in Applied and Computational Mathematics from Princeton, where his undergraduate thesis was advised by Robert Tarjan and his research on mathematics in Sanskrit was advised by Manjul Bhargava.
Siddhartha's Ph.D. thesis received the ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award. His Ph.D. research was funded by a National Defense Science and Engineering Graduate (NDSEG) Fellowship from the United States Department of Defense. Siddhartha was also awarded the NSF Graduate Research Fellowship, the Barry Goldwater Scholarship, and the Channels Scholarship from NSF's Center for Science of Information. He also received the Outstanding Computer Science Senior Thesis Prize from the Princeton CS department, the Calvin Dodd Maccracken Senior Thesis Award from Princeton's School of Engineering and Applied Sciences, and was Runner-Up for CRA's Outstanding Undergraduate Research Award.
Siddhartha's Ph.D. thesis received the ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award. His Ph.D. research was funded by a National Defense Science and Engineering Graduate (NDSEG) Fellowship from the United States Department of Defense. Siddhartha was also awarded the NSF Graduate Research Fellowship, the Barry Goldwater Scholarship, and the Channels Scholarship from NSF's Center for Science of Information. He also received the Outstanding Computer Science Senior Thesis Prize from the Princeton CS department, the Calvin Dodd Maccracken Senior Thesis Award from Princeton's School of Engineering and Applied Sciences, and was Runner-Up for CRA's Outstanding Undergraduate Research Award.
Authored Publications
Google Publications
Other Publications
Sort By
Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining
Prasad Jayanti
Sucharita Jayanti
International Symposium on Distributed Computing (2023)
Preview abstract
We present durable implementations for two well known universal primitives---CAS (compare-and-swap), and its ABA-free counter-part LLSC (load-linked, store-conditional). Our implementations satisfy method-based recoverable linearizability (MRL) and method-based detectability (M-detectability)---novel correctness conditions that require only a simple usage pattern to guarantee resilience to individual process crashes (and system-wide crashes), including in implementations with nesting. Additionally, our implementations are: writable, meaning they support a Write() operation; have constant time complexity per operation; allow for dynamic joining, meaning newly created processes (a.k.a. threads) of arbitrary names can join a protocol and access our implementations; and have adaptive space complexity, meaning the space use scales in the number of processes $n$ that actually use the objects, as opposed to previous protocols whose space complexity depends on $N$, the maximum number of processes that the protocol is designed for. Our durable Writable-CAS implementation, DuraCAS, requires $O(m + n)$ space to support $m$ objects that get accessed by $n$ processes, improving on the state-of-the-art $O(m + N^2)$. By definition, LLSC objects must store ``contexts'' in addition to object values. Our Writable-LLSC implementation, DuraLL, requires $O(m + n + C)$ space, where $C$ is the number of ``contexts'' stored across all the objects. While LLSC has an advantage over CAS due to being ABA-free, the object definition seems to require additional space usage. To address this trade-off, we define an External Context (EC) variant of LLSC. Our EC Writable-LLSC implementation is ABA-free and has a space complexity of just $O(m + n)$.
To our knowledge, our algorithms are the first durable CAS algorithms that allow for dynamic joining, and are the first to exhibit adaptive space complexity. To our knowledge, we are the first to implement any type of durable LLSC objects.
View details
Constant RMR System-wide Failure Resilient Durable Locks with Dynamic Joining
Anup Joshi
Prasad Jayanti
ACM Symposium on Parallelism in Algorithms and Architectures (2023)
Preview abstract
We design a Recoverable Mutual Exclusion (RME) algorithm for the system-wide failure model. Our algorithm requires only O(1) space per process, and achieves O(1) worst-case RMR complexity in both the CC and DSM models. Furthermore, in contrast to existing RME algorithms which can only support a pre-declared set of n threads with names from 1 to n, our algorithm can be accessed by arbitrarily many dynamically allocated threads of arbitrary names.
View details
Nash Equilibria of The Multiplayer Colonel Blotto Game on the Interval and Arbitrary Measure Spaces
Web And Internet Economics (WINE 2023) (2023) (to appear)
Preview abstract
The Colonel Blotto Problem proposed by Borel in 1921 has served as a widely applicable model of budget-constrained simultaneous winner-take-all competitions in the social sciences. Applications include elections, advertising, R&D and more. However, the classic Blotto problem and variants limit the study to competitions over a finite set of discrete battlefields. In this paper, we extend the classical theory to study multiplayer Blotto games over arbitrary measurable battlegrounds, provide an algorithm to efficiently sample equilibria of symmetric "equipartionable" Generalized Blotto games, and characterize the symmetric fair equilibria of the Blotto game over the unit interval.
View details
Brief Announcement: Efficient Recoverable Writable-CAS
Prasad Jayanti
Sucharita Jayanti
Submitting to Principles of Distributed Computing (PODC) (2023)
Preview abstract
We present DuraCAS, a durable, i.e., recoverably linearizable and detectable implementation of the CAS (compare-and-swap) primitive. DuraCAS is writable, meaning it supports a Write() operation along with CAS() and Read(); has constant time complexity per operation; allows for dynamic joining, meaning newly created processes (a.k.a. threads) of arbitrary names can join the protocol and access our implementation; and has adaptive space complexity, meaning the space use scales in the number of processes n that actually use the objects, as opposed to previous protocols whose space complexity depends on N, the maximum number of processes that the protocol is designed for. Furthermore, DuraCAS, requires only O(m + n) space to support m objects that get accessed by n processes, improving on the state-of-the-art O(m + N2). To our knowledge, DuraCAS is the first durable CAS algorithm that allows for dynamic joining, and is the first to exhibit adaptive space complexity.
View details
No Results Found
