Search Results

Documents authored by Garg, Vijay

Found 2 Possible Name Variants:

Garg, Vijay K.

Document
DOI: 10.4230/LIPIcs.OPODIS.2019.23
Parallel and Distributed Algorithms for the Housing Allocation Problem

Authors: Xiong Zheng and Vijay K. Garg

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

Abstract
We propose parallel and distributed algorithms for the housing allocation problem. In this problem, there is a set of agents and a set of houses. Each agent has a strict preference list for a subset of houses. We need to find a matching for agents to houses such that some criterion is optimized. One such criterion which has attracted much attention is Pareto optimality. A matching is Pareto optimal if no coalition of agents can be strictly better off by exchanging houses among themselves. We also study the housing market problem, a variant of the housing allocation problem, where each agent initially owns a house. In addition to Pareto optimality, we are also interested in finding the a matching in the core of a housing market. A matching is in the core if there is no coalition of agents that can be better off by breaking away from other agents and switching houses only among themselves in the initial allocation. In the first part of this work, we show that computing a Pareto optimal matching of a house allocation is in CC and computing a matching in the core of a housing market is CC-hard, where CC is the class of problems logspace reducible to the comparator circuit value problem. Given a matching of agents to houses, we show that verifying whether it is Pareto optimal is in NC. We also show that verifying whether it is in the core can be done in NC. We then give an algorithm to show that computing a maximum cardinality Pareto optimal matching for the housing allocation problem is in RNC² and quasi-NC². In the second part of this work, we present a distributed version of the top trading cycle algorithm for finding a matching in the core of a housing market. To that end, we first present two algorithms for finding all the disjoint cycles in a functional graph. The first algorithm is a Las Vegas algorithm which terminates in O(log l) rounds with high probability, where l is the length of the longest cycle. The second algorithm is a deterministic algorithm which terminates in O(log* n log l) rounds, where n is the number of nodes in the graph. Both algorithms work in the synchronous distributed model and use messages of size O(log n). By applying these two algorithms for finding cycles in a functional graph, we give the distributed top trading cycle algorithm which terminates in O(n) rounds and requires O(n²) messages.
Cite as

Xiong Zheng and Vijay K. Garg. Parallel and Distributed Algorithms for the Housing Allocation Problem. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.OPODIS.2019.23,
  author =	{Zheng, Xiong and Garg, Vijay K.},
  title =	{{Parallel and Distributed Algorithms for the Housing Allocation Problem}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{23:1--23: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.23},
  URN =		{urn:nbn:de:0030-drops-118090},
  doi =		{10.4230/LIPIcs.OPODIS.2019.23},
  annote =	{Keywords: Parallel Algorithm, Distributed Algorithm, Housing Allocation, Housing Markets, Pareto optimality}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.29
Linearizable Replicated State Machines With Lattice Agreement

Authors: Xiong Zheng, Vijay K. Garg, and John Kaippallimalil

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

Abstract
This paper studies the lattice agreement problem in asynchronous systems and explores its application to building a linearizable replicated state machine (RSM). First, we propose an algorithm to solve the lattice agreement problem in O(log f) asynchronous rounds, where f is the number of crash failures that the system can tolerate. This is an exponential improvement over the previous best upper bound of O(f). Second, Faleiro et al have shown in [Faleiro et al. PODC, 2012] that combination of conflict-free data types and lattice agreement protocols can be applied to implement a linearizable RSM. They give a Paxos style lattice agreement protocol, which can be adapted to implement a linearizable RSM and guarantee that a command by a client can be learned in at most O(n) message delays, where n is the number of proposers. Later, Xiong et al in [Xiong et al. DISC, 2018] gave a lattice agreement protocol which improves the O(n) message delay guarantee to O(f). However, neither of the protocols is practical for building a linearizable RSM. Thus, in the second part of the paper, we first give an improved protocol based on the one proposed by Xiong et al. Then, we implement a simple linearizable RSM using our improved protocol and compare our implementation with an open source Java implementation of Paxos. Results show that better performance can be obtained by using lattice agreement based protocols to implement a linearizable RSM compared to traditional consensus based protocols.
Cite as

Xiong Zheng, Vijay K. Garg, and John Kaippallimalil. Linearizable Replicated State Machines With Lattice Agreement. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.OPODIS.2019.29,
  author =	{Zheng, Xiong and Garg, Vijay K. and Kaippallimalil, John},
  title =	{{Linearizable Replicated State Machines With Lattice Agreement}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{29:1--29: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.29},
  URN =		{urn:nbn:de:0030-drops-118158},
  doi =		{10.4230/LIPIcs.OPODIS.2019.29},
  annote =	{Keywords: Lattice Agreement, Generalized Lattice Agreement, Replicated State Machine, Consensus}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.41
Lattice Agreement in Message Passing Systems

Authors: Xiong Zheng, Changyong Hu, and Vijay K. Garg

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

Abstract
This paper studies the lattice agreement problem and the generalized lattice agreement problem in distributed message passing systems. In the lattice agreement problem, given input values from a lattice, processes have to non-trivially decide output values that lie on a chain. We consider the lattice agreement problem in both synchronous and asynchronous systems. For synchronous lattice agreement, we present two algorithms which run in log(f) and min{O(log^2 h(L)), O(log^2 f)} rounds, respectively, where h(L) denotes the height of the input sublattice L, f < n is the number of crash failures the system can tolerate, and n is the number of processes in the system. These algorithms have significant better round complexity than previously known algorithms. The algorithm by Attiya et al. [Attiya et al. DISC, 1995] takes log(n) synchronous rounds, and the algorithm by Mavronicolasa [Mavronicolasa, 2018] takes min{O(h(L)), O(sqrt(f))} rounds. For asynchronous lattice agreement, we propose an algorithm which has time complexity of 2*min{h(L), f + 1} message delays which improves on the previously known time complexity of O(n) message delays. The generalized lattice agreement problem defined by Faleiro et al in [Faleiro et al. PODC, 2012] is a generalization of the lattice agreement problem where it is applied for the replicated state machine. We propose an algorithm which guarantees liveness when a majority of the processes are correct in asynchronous systems. Our algorithm requires min{O(h(L)), O(f)} units of time in the worst case which is better than O(n) units of time required by the algorithm in [Faleiro et al. PODC, 2012].
Cite as

Xiong Zheng, Changyong Hu, and Vijay K. Garg. Lattice Agreement in Message Passing Systems. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.DISC.2018.41,
  author =	{Zheng, Xiong and Hu, Changyong and Garg, Vijay K.},
  title =	{{Lattice Agreement in Message Passing Systems}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{41:1--41:17},
  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.41},
  URN =		{urn:nbn:de:0030-drops-98301},
  doi =		{10.4230/LIPIcs.DISC.2018.41},
  annote =	{Keywords: Lattice Agreement, Replicated State Machine, Consensus}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.20
Fast Detection of Stable and Count Predicates in Parallel Computations

Authors: Himanshu Chauhan and Vijay K. Garg

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
Enumerating all consistent states of a parallel computation that satisfy a given predicate is an important problem in debugging and verification of parallel programs. We give a fast algorithm to enumerate all consistent states of a parallel computation that satisfy a stable predicate. In addi- tion, we define a new category of global predicates called count predicates and give an algorithm to enumerate all consistent states (of the computation) that satisfy it. All existing predicate detection algorithms, such as BFS, DFS and Lex algorithms, do not exploit the knowledge about the nature of the predicates, and thus may visit all global states of the computation in the worst case. In comparison, our algorithms only visit the states that satisfy the given predicate, and thus take time and space that is a polynomial function of the number of states of interest. In doing so, they provide a significant reduction — exponential in many cases — in time complexities in comparison to existing algorithms.
Cite as

Himanshu Chauhan and Vijay K. Garg. Fast Detection of Stable and Count Predicates in Parallel Computations. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chauhan_et_al:LIPIcs.OPODIS.2017.20,
  author =	{Chauhan, Himanshu and Garg, Vijay K.},
  title =	{{Fast Detection of Stable and Count Predicates in Parallel Computations}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{20:1--20:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.20},
  URN =		{urn:nbn:de:0030-drops-86496},
  doi =		{10.4230/LIPIcs.OPODIS.2017.20},
  annote =	{Keywords: Algorithms, Theory, Predicate Detection, Parallel Programs}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.52
Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem

Authors: Vijay K. Garg

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
We show that many techniques developed in the context of predicate detection are applicable to the stable marriage problem. The standard Gale-Shapley algorithm can be derived as a special case of detecting linear predicates. We also show that techniques in computation slicing can be used to represent the set of all constrained stable matchings.
Cite as

Vijay K. Garg. Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 52:1-52:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{garg:LIPIcs.DISC.2017.52,
  author =	{Garg, Vijay K.},
  title =	{{Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{52:1--52:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.52},
  URN =		{urn:nbn:de:0030-drops-79719},
  doi =		{10.4230/LIPIcs.DISC.2017.52},
  annote =	{Keywords: Stable Matching, Linear Predicates, Distributive Lattices}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.17
Predicate Detection for Parallel Computations with Locking Constraints

Authors: Yen-Jung Chang and Vijay K. Garg

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
The happened-before model (or the poset model) has been widely used for modeling the computations (execution traces) of parallel programs and detecting predicates (user-specified conditions). This model captures potential causality as well as locking constraints among the executed events of computations using Lamport's happened-before relation. The detection of a predicate in a computation is performed by checking if the predicate could become true in any reachable global state of the computation. In this paper, we argue that locking constraints are fundamentally different from potential causality. Hence, a poset is not an appropriate model for debugging purposes when the computations contain locking constraints. We present a model called Locking Poset, or a Loset, that generalizes the poset model for locking constraints. Just as a poset captures possibly an exponential number of total orders, a loset captures possibly an exponential number of posets. Therefore, detecting a predicate in a loset is equivalent to detecting the predicate in all corresponding posets. Since determining if a global state is reachable in a computation is a fundamental problem for detecting predicates, this paper first studies the reachability problem in the loset model. We show that the problem is NP-complete. Afterwards, we introduce a subset of reachable global states called lock-free feasible global states such that we can check whether a global state is lock-free feasible in polynomial time. Moreover, we show that lock-free feasible global states can act as "reset" points for reachability and be used to drastically reduce the time for determining the reachability of other global states. We also introduce strongly feasible global states that contain all reachable global states and show that the strong feasibility of a global state can be checked in polynomial time. We show that strong feasibility provides an effective approximation of reachability for many practical applications.
Cite as

Yen-Jung Chang and Vijay K. Garg. Predicate Detection for Parallel Computations with Locking Constraints. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.OPODIS.2016.17,
  author =	{Chang, Yen-Jung and Garg, Vijay K.},
  title =	{{Predicate Detection for Parallel Computations with Locking Constraints}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.17},
  URN =		{urn:nbn:de:0030-drops-70867},
  doi =		{10.4230/LIPIcs.OPODIS.2016.17},
  annote =	{Keywords: predicate detection, parallel computations, reachable global states, locking constraints, happened-before relation}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.25
QuickLex: A Fast Algorithm for Consistent Global States Enumeration of Distributed Computations

Authors: Yen-Jung Chang and Vijay K. Garg

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Verifying the correctness of executions of concurrent and distributed programs is difficult because they show nondeterministic behavior due to different process scheduling order. Predicate detection can alleviate this problem by predicting whether the user-specified condition (predicate) could have become true in any global state of the given concurrent or distributed computation. The method is predictive because it generates inferred global states from the observed execution path and then checks if those global states satisfy the predicate. An important part of the predicate detection method is global states enumeration, which generates the consistent global states, including the inferred ones, of the given computation. Cooper and Marzullo gave the first enumeration algorithm based on a breadth first strategy (BFS). Later, many algorithms have been proposed to improve the space and time complexity. Among the existing algorithms, the Tree algorithm due to Jegou et al. has the smallest time complexity and requires O(|P|) space, which is linear to the size of the computation P. In this paper, we present a fast algorithm, QuickLex, to enumerate global states in the lexical order. QuickLex requires much smaller space than O(|P|). From our experiments, the Tree algorithm requires 2-10 times more memory space than QuickLex. Moreover, QuickLex is 4 times faster than Tree even though the asymptotic time complexity of QuickLex is higher than that of Tree. The reason is that the worst case time complexity of QuickLex happens only in computations that are not common in practice. Moreover, Tree is built on linked-lists and QuickLex can be implemented using integer arrays. In comparison with the existing lexical algorithm (Lex), QuickLex is 7 times faster and uses almost the same amount of memory as Lex. Finally, we implement a parallel-and-online predicate detector for concurrent programs using QuickLex, which can detect data races and violation of invariants in the programs.
Cite as

Yen-Jung Chang and Vijay K. Garg. QuickLex: A Fast Algorithm for Consistent Global States Enumeration of Distributed Computations. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.OPODIS.2015.25,
  author =	{Chang, Yen-Jung and Garg, Vijay K.},
  title =	{{QuickLex: A Fast Algorithm for Consistent Global States Enumeration of Distributed Computations}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.25},
  URN =		{urn:nbn:de:0030-drops-66142},
  doi =		{10.4230/LIPIcs.OPODIS.2015.25},
  annote =	{Keywords: consistent global state, algorithm, computation}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.29
ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization

Authors: Wei-Lun Hung, Himanshu Chauhan, and Vijay K. Garg

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Monitor objects are used extensively for thread-safety and synchronization in shared memory parallel programs. They provide ease of use, and enable straightforward correctness analysis. However, they inhibit parallelism by enforcing serial executions of critical sections, and thus the performance of parallel programs with monitors scales poorly with number of processes. Their current design and implementation is also ill-suited for thread synchronization across multiple thread-safe objects. We present ActiveMonitor - a framework that allows multi-object synchronization without global locks, and improves parallelism by exploiting asynchronous execution of critical sections. We evaluate the performance of Java based implementation of ActiveMonitor on micro-benchmarks involving light and heavy critical sections, as well as on single-source-shortest-path problem in directed graphs. Our results show that on most of these problems, ActiveMonitor based programs outperform programs implemented using Java's reentrant-lock and condition constructs.
Cite as

Wei-Lun Hung, Himanshu Chauhan, and Vijay K. Garg. ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hung_et_al:LIPIcs.OPODIS.2015.29,
  author =	{Hung, Wei-Lun and Chauhan, Himanshu and Garg, Vijay K.},
  title =	{{ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.29},
  URN =		{urn:nbn:de:0030-drops-66188},
  doi =		{10.4230/LIPIcs.OPODIS.2015.29},
  annote =	{Keywords: concurrent/parallel programming, monitors, concurrency}
}

Garg, Vijay

Document
DOI: 10.4230/LIPIcs.OPODIS.2020.4
Byzantine Lattice Agreement in Asynchronous Systems

Authors: Xiong Zheng and Vijay Garg

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

Abstract
We study the Byzantine lattice agreement (BLA) problem in asynchronous distributed message passing systems. In the BLA problem, each process proposes a value from a join semi-lattice and needs to output a value also in the lattice such that all output values of correct processes lie on a chain despite the presence of Byzantine processes. We present an algorithm for this problem with round complexity of O(log f) which tolerates f < n/5 Byzantine failures in the asynchronous setting without digital signatures, where n is the number of processes. This is the first algorithm which has logarithmic round complexity for this problem in asynchronous setting. Before our work, Di Luna et al give an algorithm for this problem which takes O(f) rounds and tolerates f < n/3 Byzantine failures. We also show how this algorithm can be modified to work in the authenticated setting (i.e., with digital signatures) to tolerate f < n/3 Byzantine failures.
Cite as

Xiong Zheng and Vijay Garg. Byzantine Lattice Agreement in Asynchronous Systems. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.OPODIS.2020.4,
  author =	{Zheng, Xiong and Garg, Vijay},
  title =	{{Byzantine Lattice Agreement in Asynchronous Systems}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{4:1--4: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.4},
  URN =		{urn:nbn:de:0030-drops-134894},
  doi =		{10.4230/LIPIcs.OPODIS.2020.4},
  annote =	{Keywords: Byzantine Lattice Agreement, Asynchronous}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.32
Byzantine Lattice Agreement in Synchronous Message Passing Systems

Authors: Xiong Zheng and Vijay Garg

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

Abstract
We propose three algorithms for the Byzantine lattice agreement problem in synchronous systems. The first algorithm runs in min {3h(X) + 6,6√{f_a} + 6}) rounds and takes O(n² min{h(X), √{f_a}}) messages, where h(X) is the height of the input lattice X, n is the total number of processes in the system, f is the maximum number of Byzantine processes such that n ≥ 3f + 1 and f_a ≤ f is the actual number of Byzantine processes in an execution. The second algorithm takes 3log n + 3 rounds and O(n² log n) messages. The third algorithm takes 4 log f + 3 rounds and O(n² log f) messages. All algorithms can tolerate f < n/3 Byzantine failures. This is the first work for the Byzantine lattice agreement problem in synchronous systems which achieves logarithmic rounds. In our algorithms, we apply a slightly modified version of the Gradecast algorithm given by Feldman et al [Feldman and Micali, 1988] as a building block. If we use the Gradecast algorithm for authenticated setting given by Katz et al [Katz and Koo, 2006], we obtain algorithms for the Byzantine lattice agreement problem in authenticated settings and tolerate f < n/2 failures.
Cite as

Xiong Zheng and Vijay Garg. Byzantine Lattice Agreement in Synchronous Message Passing Systems. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.DISC.2020.32,
  author =	{Zheng, Xiong and Garg, Vijay},
  title =	{{Byzantine Lattice Agreement in Synchronous Message Passing Systems}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{32:1--32:16},
  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.32},
  URN =		{urn:nbn:de:0030-drops-131106},
  doi =		{10.4230/LIPIcs.DISC.2020.32},
  annote =	{Keywords: Lattice agreement, Byzantine Failure, Gradecast}
}
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