Search Results

Documents authored by Tseng, Lewis

Document
DOI: 10.4230/LIPIcs.DISC.2024.39
The Power of Abstract MAC Layer: A Fault-Tolerance Perspective

Authors: Qinzi Zhang and Lewis Tseng

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
This paper studies the power of the "abstract MAC layer" model in a single-hop asynchronous network. The model captures primitive properties of modern wireless MAC protocols. In this model, Newport [PODC '14] proves that it is impossible to achieve deterministic consensus when nodes may crash. Subsequently, Newport and Robinson [DISC '18] present randomized consensus algorithms that terminate with O(n³ log n) expected broadcasts in a system of n nodes. We are not aware of any results on other fault-tolerant distributed tasks in this model. We first study the computability aspect of the abstract MAC layer. We present a wait-free algorithm that implements an atomic register. Furthermore, we show that in general, k-set consensus is impossible. Second, we aim to minimize storage complexity. Existing algorithms require Ω(n log n) bits. We propose two wait-free approximate consensus and two wait-free randomized binary consensus algorithms that only need constant storage complexity (except for the phase index). One randomized algorithm terminates with O(n log n) expected broadcasts. All our algorithms are anonymous, meaning that at the algorithm level, nodes do not need to have a unique identifier.
Cite as

Qinzi Zhang and Lewis Tseng. The Power of Abstract MAC Layer: A Fault-Tolerance Perspective. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 39:1-39:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.DISC.2024.39,
  author =	{Zhang, Qinzi and Tseng, Lewis},
  title =	{{The Power of Abstract MAC Layer: A Fault-Tolerance Perspective}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{39:1--39:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.39},
  URN =		{urn:nbn:de:0030-drops-212677},
  doi =		{10.4230/LIPIcs.DISC.2024.39},
  annote =	{Keywords: Abstract MAC Layer, Computation Power, Consensus}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.9
Byzantine Consensus in Abstract MAC Layer

Authors: Lewis Tseng and Callie Sardina

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
This paper studies the design of Byzantine consensus algorithms in an asynchronous single-hop network equipped with the "abstract MAC layer" [DISC09], which captures core properties of modern wireless MAC protocols. Newport [PODC14], Newport and Robinson [DISC18], and Tseng and Zhang [PODC22] study crash-tolerant consensus in the model. In our setting, a Byzantine faulty node may behave arbitrarily, but it cannot break the guarantees provided by the underlying abstract MAC layer. To our knowledge, we are the first to study Byzantine faults in this model. We harness the power of the abstract MAC layer to develop a Byzantine approximate consensus algorithm and a Byzantine randomized binary consensus algorithm. Both of our algorithms require only the knowledge of the upper bound on the number of faulty nodes f, and do not require the knowledge of the number of nodes n. This demonstrates the "power" of the abstract MAC layer, as consensus algorithms in traditional message-passing models require the knowledge of both n and f. Additionally, we show that it is necessary to know f in order to reach consensus. Hence, from this perspective, our algorithms require the minimal knowledge. The lack of knowledge of n brings the challenge of identifying a quorum explicitly, which is a common technique in traditional message-passing algorithms. A key technical novelty of our algorithms is to identify "implicit quorums" which have the necessary information for reaching consensus. The quorums are implicit because nodes do not know the identity of the quorums - such notion is only used in the analysis.
Cite as

Lewis Tseng and Callie Sardina. Byzantine Consensus in Abstract MAC Layer. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{tseng_et_al:LIPIcs.OPODIS.2023.9,
  author =	{Tseng, Lewis and Sardina, Callie},
  title =	{{Byzantine Consensus in Abstract MAC Layer}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.9},
  URN =		{urn:nbn:de:0030-drops-194992},
  doi =		{10.4230/LIPIcs.OPODIS.2023.9},
  annote =	{Keywords: Byzantine, Randomized Consensus, Approximate Consensus, Abstract MAC}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.50
Brief Announcement: Asymmetric Mutual Exclusion for RDMA

Authors: Jacob Nelson-Slivon, Lewis Tseng, and Roberto Palmieri

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
In this brief announcement, we define operation asymmetry, which captures how processes may interact with an object differently, and discuss its implications in the context of a popular network communication technology, remote direct memory access (RDMA). Then, we present a novel approach to mutual exclusion for RDMA-based distributed synchronization under operation asymmetry. Our approach avoids RDMA loopback for local processes and guarantees starvation-freedom and fairness.
Cite as

Jacob Nelson-Slivon, Lewis Tseng, and Roberto Palmieri. Brief Announcement: Asymmetric Mutual Exclusion for RDMA. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 50:1-50:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nelsonslivon_et_al:LIPIcs.DISC.2022.50,
  author =	{Nelson-Slivon, Jacob and Tseng, Lewis and Palmieri, Roberto},
  title =	{{Brief Announcement: Asymmetric Mutual Exclusion for RDMA}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{50:1--50:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.50},
  URN =		{urn:nbn:de:0030-drops-172417},
  doi =		{10.4230/LIPIcs.DISC.2022.50},
  annote =	{Keywords: Mutual exclusion, Synchronization, Remote direct memory access (RDMA)}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.7
Echo-CGC: A Communication-Efficient Byzantine-Tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network

Authors: Qinzi Zhang and Lewis Tseng

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
In the past few years, many Byzantine-tolerant distributed machine learning (DML) algorithms have been proposed in the point-to-point communication model. In this paper, we focus on a popular DML framework - the parameter server computation paradigm and iterative learning algorithms that proceed in rounds, e.g., [Gupta and Vaidya, 2020; El-Mhamdi et al., 2020; Chen et al., 2017]. One limitation of prior algorithms in this domain is the high communication complexity. All the Byzantine-tolerant DML algorithms that we are aware of need to send n d-dimensional vectors from worker nodes to the parameter server in each round, where n is the number of workers and d is the number of dimensions of the feature space (which may be in the order of millions). In a wireless network, power consumption is proportional to the number of bits transmitted. Consequently, it is extremely difficult, if not impossible, to deploy these algorithms in power-limited wireless devices. Motivated by this observation, we aim to reduce the communication complexity of Byzantine-tolerant DML algorithms in the single-hop radio network [Alistarh et al., 2010; Bhandari and Vaidya, 2005; Koo, 2004]. Inspired by the CGC filter developed by Gupta and Vaidya, PODC 2020 [Gupta and Vaidya, 2020], we propose a gradient descent-based algorithm, Echo-CGC. Our main novelty is a mechanism to utilize the broadcast properties of the radio network to avoid transmitting the raw gradients (full d-dimensional vectors). In the radio network, each worker is able to overhear previous gradients that were transmitted to the parameter server. Roughly speaking, in Echo-CGC, if a worker "agrees" with a combination of prior gradients, it will broadcast the "echo message" instead of the its raw local gradient. The echo message contains a vector of coefficients (of size at most n) and the ratio of the magnitude between two gradients (a float). In comparison, the traditional approaches need to send n local gradients in each round, where each gradient is typically a vector in a ultra-high dimensional space (d ≫ n). The improvement on communication complexity of our algorithm depends on multiple factors, including number of nodes, number of faulty workers in an execution, and the cost function. We numerically analyze the improvement, and show that with a large number of nodes, Echo-CGC reduces 80% of the communication under standard assumptions.
Cite as

Qinzi Zhang and Lewis Tseng. Echo-CGC: A Communication-Efficient Byzantine-Tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.OPODIS.2020.7,
  author =	{Zhang, Qinzi and Tseng, Lewis},
  title =	{{Echo-CGC: A Communication-Efficient Byzantine-Tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.7},
  URN =		{urn:nbn:de:0030-drops-134927},
  doi =		{10.4230/LIPIcs.OPODIS.2020.7},
  annote =	{Keywords: Distributed Machine Learning, Single-hop Radio Network, Byzantine Fault, Communication Complexity, Wireless Communication, Parameter Server}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.53
Brief Announcement: Reaching Approximate Consensus When Everyone May Crash

Authors: Lewis Tseng, Qinzi Zhang, and Yifan Zhang

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Fault-tolerant consensus is of great importance in distributed systems. This paper studies the asynchronous approximate consensus problem in the crash-recovery model with fair-loss links. In our model, up to f nodes may crash forever, while the rest may crash intermittently. Each node is equipped with a limited-size persistent storage that does not lose data when crashed. We present an algorithm that only stores three values in persistent storage - state, phase index, and a counter.
Cite as

Lewis Tseng, Qinzi Zhang, and Yifan Zhang. Brief Announcement: Reaching Approximate Consensus When Everyone May Crash. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 53:1-53:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{tseng_et_al:LIPIcs.DISC.2020.53,
  author =	{Tseng, Lewis and Zhang, Qinzi and Zhang, Yifan},
  title =	{{Brief Announcement: Reaching Approximate Consensus When Everyone May Crash}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{53:1--53:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.53},
  URN =		{urn:nbn:de:0030-drops-131319},
  doi =		{10.4230/LIPIcs.DISC.2020.53},
  annote =	{Keywords: Approximate Consensus, Fair-loss Channel, Crash-recovery}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.30
Exact Byzantine Consensus on Arbitrary Directed Graphs Under Local Broadcast Model

Authors: Muhammad Samir Khan, Lewis Tseng, and Nitin H. Vaidya

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
We consider Byzantine consensus in a synchronous system where nodes are connected by a network modeled as a directed graph, i.e., communication links between neighboring nodes are not necessarily bi-directional. The directed graph model is motivated by wireless networks wherein asymmetric communication links can occur. In the classical point-to-point communication model, a message sent on a communication link is private between the two nodes on the link. This allows a Byzantine faulty node to equivocate, i.e., send inconsistent information to its neighbors. This paper considers the local broadcast model of communication, wherein transmission by a node is received identically by all of its outgoing neighbors, effectively depriving the faulty nodes of the ability to equivocate. Prior work has obtained sufficient and necessary conditions on undirected graphs to be able to achieve Byzantine consensus under the local broadcast model. In this paper, we obtain tight conditions on directed graphs to be able to achieve Byzantine consensus with binary inputs under the local broadcast model. The results obtained in the paper provide insights into the trade-off between directionality of communication links and the ability to achieve consensus.
Cite as

Muhammad Samir Khan, Lewis Tseng, and Nitin H. Vaidya. Exact Byzantine Consensus on Arbitrary Directed Graphs Under Local Broadcast Model. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.OPODIS.2019.30,
  author =	{Khan, Muhammad Samir and Tseng, Lewis and Vaidya, Nitin H.},
  title =	{{Exact Byzantine Consensus on Arbitrary Directed Graphs Under Local Broadcast Model}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.30},
  URN =		{urn:nbn:de:0030-drops-118161},
  doi =		{10.4230/LIPIcs.OPODIS.2019.30},
  annote =	{Keywords: complexity and impossibility results for distributed computing, fault-tolerance, reliability}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.14
Effects of Topology Knowledge and Relay Depth on Asynchronous Appoximate Consensus

Authors: Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
Consider a point-to-point message-passing network. We are interested in the asynchronous crash-tolerant consensus problem in incomplete networks. We study the feasibility and efficiency of approximate consensus under different restrictions on topology knowledge and the relay depth, i.e., the maximum number of hops any message can be relayed. These two constraints are common in large-scale networks, and are used to avoid memory overload and network congestion respectively. Specifically, for positive integer values k and k', we consider that each node knows all its neighbors of at most k-hop distance (k-hop topology knowledge), and the relay depth is k'. We consider both directed and undirected graphs. More concretely, we answer the following question in asynchronous systems: "What is a tight condition on the underlying communication graphs for achieving approximate consensus if each node has only a k-hop topology knowledge and relay depth k'?" To prove that the necessary conditions presented in the paper are also sufficient, we have developed algorithms that achieve consensus in graphs satisfying those conditions: - The first class of algorithms requires k-hop topology knowledge and relay depth k. Unlike prior algorithms, these algorithms do not flood the network, and each node does not need the full topology knowledge. We show how the convergence time and the message complexity of those algorithms is affected by k, providing the respective upper bounds. - The second set of algorithms requires only one-hop neighborhood knowledge, i.e., immediate incoming and outgoing neighbors, but needs to flood the network (i.e., relay depth is n, where n is the number of nodes). One result that may be of independent interest is a topology discovery mechanism to learn and "estimate" the topology in asynchronous directed networks with crash faults.
Cite as

Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya. Effects of Topology Knowledge and Relay Depth on Asynchronous Appoximate Consensus. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{sakavalas_et_al:LIPIcs.OPODIS.2018.14,
  author =	{Sakavalas, Dimitris and Tseng, Lewis and Vaidya, Nitin H.},
  title =	{{Effects of Topology Knowledge and Relay Depth on Asynchronous Appoximate Consensus}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.14},
  URN =		{urn:nbn:de:0030-drops-100744},
  doi =		{10.4230/LIPIcs.OPODIS.2018.14},
  annote =	{Keywords: Asynchrony, crash, consensus, incomplete graphs, topology knowledge}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2018.51
Brief Announcement: Effects of Topology Knowledge and Relay Depth on Asynchronous Consensus

Authors: Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Consider an asynchronous incomplete directed network. We study the feasibility and efficiency of approximate crash-tolerant consensus under different restrictions on topology knowledge and relay depth, i.e., the maximum number of hops any message can be relayed.
Cite as

Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya. Brief Announcement: Effects of Topology Knowledge and Relay Depth on Asynchronous Consensus. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 51:1-51:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sakavalas_et_al:LIPIcs.DISC.2018.51,
  author =	{Sakavalas, Dimitris and Tseng, Lewis and Vaidya, Nitin H.},
  title =	{{Brief Announcement: Effects of Topology Knowledge and Relay Depth on Asynchronous Consensus}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{51:1--51:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.51},
  URN =		{urn:nbn:de:0030-drops-98405},
  doi =		{10.4230/LIPIcs.DISC.2018.51},
  annote =	{Keywords: Asynchrony, crash fault, consensus, topology knowledge, relay}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact