Lewis Tseng
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Lewis Tseng has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Guanfeng Liang
Facebook, Menlo Park, USA
1 shared publication - Nitin H. Vaidya
Georgetown University
1 shared publication - Qinzi Zhang
Boston University Boston USA
1 shared publication - Selman Erol1 shared publication
- Tzuo Hann Law
Unaffiliated
1 shared publication
Latest Publications
- 22 May 2024
- Published by Springer Nature in Distributed Computing
- Vol. 37 (3) , 225-246
Iterative approximate Byzantine consensus in arbitrary directed graphs
- 22 May 2024
- Published by Springer Nature in Distributed Computing
- Vol. 37 (3) , 225-246
Iterative approximate Byzantine consensus in arbitrary directed graphs
- Open Access
Fault-tolerant Consensus in Anonymous Dynamic Network
This paper studies the feasibility of reaching consensus in an anonymous dynamic network. In our model, $n$ anonymous nodes proceed in synchronous rounds. We adopt a hybrid fault model in which up to $f$ nodes may suffer crash or Byzantine faults, and the dynamic message adversary chooses a communication graph for each round. We introduce a stability property of the dynamic network -- $(T,D)$-dynaDegree for $T \geq 1$ and $n-1 \geq D \geq 1$ -- which requires that for every $T$ consecutive rounds, any fault-free node must have incoming directed links from at least $D$ distinct neighbors. These links might occur in different rounds during a $T$-round interval. $(1,n-1)$-dynaDegree means that the graph is a complete graph in every round. $(1,1)$-dynaDegree means that each node has at least one incoming neighbor in every round, but the set of incoming neighbor(s) at each node may change arbitrarily between rounds. We show that exact consensus is impossible even with $(1,n-2)$-dynaDegree. For an arbitrary $T$, we show that for crash-tolerant approximate consensus, $(T,\lfloor n/2 \rfloor)$-dynaDegree and $n > 2f$ are together necessary and sufficient, whereas for Byzantine approximate consensus, $(T,\lfloor (n+3f)/2 \rfloor)$-dynaDegree and $n > 5f$ are together necessary and sufficient.Open AccessFault-tolerant Consensus in Anonymous Dynamic Network
This paper studies the feasibility of reaching consensus in an anonymous dynamic network. In our model, $n$ anonymous nodes proceed in synchronous rounds. We adopt a hybrid fault model in which up to $f$ nodes may suffer crash or Byzantine faults, and the dynamic message adversary chooses a communication graph for each round. We introduce a stability property of the dynamic network -- $(T,D)$-dynaDegree for $T \geq 1$ and $n-1 \geq D \geq 1$ -- which requires that for every $T$ consecutive rounds, any fault-free node must have incoming directed links from at least $D$ distinct neighbors. These links might occur in different rounds during a $T$-round interval. $(1,n-1)$-dynaDegree means that the graph is a complete graph in every round. $(1,1)$-dynaDegree means that each node has at least one incoming neighbor in every round, but the set of incoming neighbor(s) at each node may change arbitrarily between rounds. We show that exact consensus is impossible even with $(1,n-2)$-dynaDegree. For an arbitrary $T$, we show that for crash-tolerant approximate consensus, $(T,\lfloor n/2 \rfloor)$-dynaDegree and $n > 2f$ are together necessary and sufficient, whereas for Byzantine approximate consensus, $(T,\lfloor (n+3f)/2 \rfloor)$-dynaDegree and $n > 5f$ are together necessary and sufficient. - Open Access
Longest-chain Attacks: Difficulty Adjustment and Timestamp Verifiability
We study an adversary who attacks a Proof-of-Work (POW) blockchain by selfishly constructing an alternative longest chain. We characterize optimal strategies employed by the adversary when a difficulty adjustment rule alà Bitcoin applies. As time (namely the times-tamp specified in each block) in most permissionless POW blockchains is somewhat subjective, we focus on two extreme scenarios: when time is completely verifiable, and when it is completely unverifiable. We conclude that an adversary who faces a difficulty adjustment rule will find a longest-chain attack very challenging when timestamps are verifiable. POW blockchains with frequent difficulty adjustments relative to time reporting flexibility will be substantially more vulnerable to longest-chain attacks. Our main fining provides guidance on the design of difficulty adjustment rules and demonstrates the importance of timestamp verifiability.
Open AccessLongest-chain Attacks: Difficulty Adjustment and Timestamp Verifiability
We study an adversary who attacks a Proof-of-Work (POW) blockchain by selfishly constructing an alternative longest chain. We characterize optimal strategies employed by the adversary when a difficulty adjustment rule alà Bitcoin applies. As time (namely the times-tamp specified in each block) in most permissionless POW blockchains is somewhat subjective, we focus on two extreme scenarios: when time is completely verifiable, and when it is completely unverifiable. We conclude that an adversary who faces a difficulty adjustment rule will find a longest-chain attack very challenging when timestamps are verifiable. POW blockchains with frequent difficulty adjustments relative to time reporting flexibility will be substantially more vulnerable to longest-chain attacks. Our main fining provides guidance on the design of difficulty adjustment rules and demonstrates the importance of timestamp verifiability.