John Augustine 0001

SODA Conference 2025 Conference Paper

Fully-Distributed Byzantine Agreement in Sparse Networks

• John Augustine 0001
• Fabien Dufoulon
• Gopal Pandurangan

Byzantine agreement is a fundamental problem in fault-tolerant distributed networks that has been studied intensively for the last four decades. Most of these works designed protocols for complete networks. A key goal in Byzantine protocols is to tolerate as many Byzantine nodes as possible. The work of Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] was the first to address the Byzantine agreement problem in sparse, bounded degree networks and presented a protocol that achieved almost-everywhere agreement among honest nodes. In such networks, all known Byzantine agreement protocols (e. g. , Dwork, Peleg, Pippenger, and Upfal, STOC 1986; Upfal, PODC 1992; King, Saia, Sanwalani, and Vee, FOCS 2006) that tolerated a large number of Byzantine nodes had a major drawback that they were not fully-distributed — in those protocols, nodes are required to have initial knowledge of the entire network topology. This drawback makes such protocols inapplicable to real-world communication networks such as peer-to-peer (P2P) networks, which are typically sparse and bounded degree and where nodes initially have only local knowledge of themselves and their neighbors. Indeed, a fundamental open question raised by the above works is whether one can design Byzantine protocols that tolerate a large number of Byzantine nodes in sparse networks that work with only local knowledge, i. e. , fully-distributed protocols. The work of Augustine, Pandurangan, and Robinson [PODC 2013] presented the first fully-distributed Byzantine agreement protocol that works in sparse networks, but it tolerated only up to Byzantine nodes (where n is the total network size). We present fully-distributed Byzantine agreement protocols for sparse, bounded degree networks that tolerate significantly more Byzantine nodes, answering the earlier open question. Our protocols work under the powerful full information model where the Byzantine nodes can behave arbitrarily and maliciously, have knowledge about the entire state of the network at every round, including random choices made by the nodes up to (and including) the current round, have unlimited computational power, and may collude among themselves. We first present a protocol that tolerates up to Byzantine nodes and with high probability 1, solves almost-everywhere agreement where all except o ( n ) honest nodes reach agreement. The protocol runs in Õ ( n 2 ) rounds. We then present a faster protocol that runs in nearly linear (i. e. , Õ ( n )) rounds and tolerates up to Byzantine nodes. Both protocols are communication-efficient in the sense that honest nodes send only polylog n bits per edge per round. 1 Throughout, “with high probability (whp)” means with probability at least, where c ≥ 1 is a fixed constant.

SODA Conference 2020 Conference Paper

Shortest Paths in a Hybrid Network Model

• John Augustine 0001
• Kristian Hinnenthal
• Fabian Kuhn
• Christian Scheideler
• Philipp Schneider

We introduce a communication model for hybrid networks, where nodes have access to two different communication modes: a local mode where (like in traditional networks) communication is only possible between specific pairs of nodes, and a global mode where (like in overlay networks) communication between any pair of nodes is possible. Typically, communication over short-range connections is cheaper and can be done at a much higher rate than communication via the overlay network. Therefore, we are focusing on the LOCAL model for the local connections where nodes can exchange an unbounded amount of information per round. For the global communication we assume the so-called nodecapacitated clique model, where in each round every node can exchange O (log n )-bit messages with O (log n ) arbitrary nodes. We explore the impact of hybrid communication on the complexity of distributed algorithms by studying the problem of computing shortest paths in the graph given by the local connections. We present the following results. For the all-pairs shortest paths problem, we show that an exact solution can be computed in time Õ ( n 2/3 ), and that approximate solutions can be computed in time but not faster. For the single-source shortest paths problem an exact solution can be computed in time, where SPD denotes the shortest path diameter. Furthermore, a (l + o (1))-approximate solution can be computed in time. Finally, we show that for every constant ε > 0, it is possible to compute an O (1)-approximate solution in time.

SODA Conference 2016 Conference Paper

Balanced Allocation: Patience is not a Virtue

• John Augustine 0001
• William K. Moses Jr.
• Amanda Redlich
• Eli Upfal

FOCS Conference 2015 Conference Paper

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

• John Augustine 0001
• Gopal Pandurangan
• Peter Robinson 0002
• Scott T. Roche
• Eli Upfal

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 for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy churn (i. e. , Nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a constant degree graph with high expansion even under continuous high adversarial churn. Our protocol can tolerate a churn rate of up to O(n/polylog(n)) per round (where n is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only O(polylog(n)) overhead for topology maintenance: only polylogarithmic(in n) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.

SODA Conference 2012 Conference Paper

Towards robust and efficient computation in dynamic peer-to-peer networks

• John Augustine 0001
• Gopal Pandurangan
• Peter Robinson 0002
• Eli Upfal

Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node churn (i. e. , nodes join and leave the network continuously over time). Our goal is to design fast algorithms (running in a small number of rounds) that guarantee, despite high node churn rate, that almost all nodes reach a stable agreement. Our main contributions are randomized distributed algorithms that guarantee stable almost-everywhere agreement with high probability even under high adversarial churn in a polylogarithmic number of rounds. In particular, we present the following results: 1. An O (log n )-round ( n is the stable network size) randomized algorithm that achieves almost-everywhere agreement with high probability under up to linear churn per round (i. e. , ε n, for some small constant ε > 0), assuming that the churn is controlled by an oblivious adversary (that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm). 2. An O (log m log 3 n )-round randomized algorithm that achieves almost-everywhere agreement with high probability under up to ε√ n churn per round (for some small ε > 0), where m is the size of the input value domain, that works even under an adaptive adversary (that also knows the past random choices made by the algorithm). Our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings (i. e. , high churn rates per step). Furthermore, they are localized (i. e. , do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in dynamic P2P networks.

FOCS Conference 2004 Conference Paper

Optimal Power-Down Strategies

• John Augustine 0001
• Sandy Irani
• Chaitanya Swamy

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