4 Search Results for "Nawab, Faisal"

Document
DOI: 10.4230/LIPIcs.OPODIS.2024.6
DULL: A Fast Scalable Detectable Unrolled Lock-Based Linked List

Authors: Ahmed Fahmy and Wojciech Golab

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Persistent memory (PM) has emerged as a promising technology that enables data structures to preserve their consistent state after recovering from system failures. Detectable data structures have been proposed to detect the response of the last operation of a crashed process. Various lock-free detectable and recoverable concurrent data structures have been developed in the literature. However, designing detectable lock-based structures is challenging due to the need to preserve the correctness properties of the underlying locks, such as mutual exclusion and deadlock-freedom, across failures. Therefore, lock-based detectable and persistent data structures are not as common as lock-free structures. In this work, we introduce DULL: a fast, scalable and Detectable Unrolled Lock-based Linked list. This paper presents the design and implementation of DULL, along with an evaluation of its recoverability and scalability. Experimental Results show that DULL is several-fold faster than the competition in all workloads that involve updates. Moreover, as opposed to some of the previous works, our algorithm is scalable when the multiprocessor is oversubscribed. DULL is a demonstration of the feasibility of using lock-based data structures with detectability in PM environments. We believe that DULL opens up new research directions for designing and analyzing detectable lock-based data structures.
Cite as

Ahmed Fahmy and Wojciech Golab. DULL: A Fast Scalable Detectable Unrolled Lock-Based Linked List. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fahmy_et_al:LIPIcs.OPODIS.2024.6,
  author =	{Fahmy, Ahmed and Golab, Wojciech},
  title =	{{DULL: A Fast Scalable Detectable Unrolled Lock-Based Linked List}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{6:1--6:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.6},
  URN =		{urn:nbn:de:0030-drops-225429},
  doi =		{10.4230/LIPIcs.OPODIS.2024.6},
  annote =	{Keywords: detectability, lock-based, mutual exclusion, linked list, fault-tolerance, persistent memory, concurrency}
}
Document
Poster
DOI: 10.4230/OASIcs.FAB.2022.7
Analyzing Soft and Hard Partitions of Global-Scale Blockchain Systems (Poster)

Authors: Kevin Bruhwiler, Fayzah Alshammari, Farzad Habibi, Juncheng Fang, and Faisal Nawab

Published in: OASIcs, Volume 101, 5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022)

Abstract
Partitioning attacks have been a known threat since the invention of cryptocurrencies. Attackers could deliberately fork the chain by re-routing network traffic into two or more separate chains and spend money on each piece, effectively spending multiples of their money. Apostolaki et. al. [{Apostolaki and {Laurent Vanbever}, 2017] were among the first to quantify the threats of such attacks on Bitcoin. They suggest a number of ways to mitigate this risk which were combined into a tool named SABRE. Jyothi explored the possibility that a solar superstorm could damage the undersea fiber-optic cables that connect the Internets of different continents, and considered the mostly likely ramifications of the damage. She concluded that such an event would likely cause major connectivity issues across the northern hemisphere and may disconnect much of North America’s internet from the eastern hemisphere for weeks. There is also concern that undersea cables could be deliberately destroyed as acts of terrorism or war or by natural disasters such as earthquakes. In this work, we construct a simulation to properly quantify the effects of a global-scale network partition on the blockchain. We hope to provide the groundwork for preventative measures to be taken to minimize the harm that such partitions might cause in the future. We do this by modifying SimBlock [{Yusuke, 2019], a blockchain simulator created to study the effect of different network topologies, to allow initiating and recovering from partitions and also add metrics to capture their effects. To quantify the severity of partitions we use a number of metrics, including the rate of agreement improvement after a new block has been minted and the average rate of block propagation across regions. We also examine the number of forks in the blockchain that result from partitions and identify the break-points at which forks begin to appear. Finally, we quantify the duration that partitions of various sizes can persist before they begin to generate forks and measure the how long it takes for the system to recover once the partition has been resolved.
Cite as

Kevin Bruhwiler, Fayzah Alshammari, Farzad Habibi, Juncheng Fang, and Faisal Nawab. Analyzing Soft and Hard Partitions of Global-Scale Blockchain Systems (Poster). In 5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022). Open Access Series in Informatics (OASIcs), Volume 101, p. 7:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bruhwiler_et_al:OASIcs.FAB.2022.7,
  author =	{Bruhwiler, Kevin and Alshammari, Fayzah and Habibi, Farzad and Fang, Juncheng and Nawab, Faisal},
  title =	{{Analyzing Soft and Hard Partitions of Global-Scale Blockchain Systems}},
  booktitle =	{5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022)},
  pages =	{7:1--7:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-248-8},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{101},
  editor =	{Tucci-Piergiovanni, Sara and Crooks, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.FAB.2022.7},
  URN =		{urn:nbn:de:0030-drops-162741},
  doi =		{10.4230/OASIcs.FAB.2022.7},
  annote =	{Keywords: Blockchain, Partitioning, Resilience, Simulation}
}
Document
Poster
DOI: 10.4230/OASIcs.FAB.2022.9
Improving Blockchain Resilience to Network Partitioning by Sharding (Poster)

Authors: Juncheng Fang, Farzad Habibi, Kevin Bruhwiler, Fayzah Alshammari, and Faisal Nawab

Published in: OASIcs, Volume 101, 5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022)

Abstract
Blockchain plays a significant role in cryptocurrencies and growing applications like smart contracts. However, prior blockchain algorithms did not consider large-scale network partitioning a considerable concern while relying heavily on a reliable global network. Previous works have shown a possibility of a massive disruption on the Internet. The author in [Jyothi, 2021] discusses the case of Internet disorder due to solar superstorms, which can disconnect different geographical regions from each other for months. Partitioning attacks are also notable concerns that should be considered, in which their goal is to cut connections between a set of nodes and the rest of the network. In the case of network partitioning, the main chain will fork into branches, and miners in different disconnected regions will create multiple blocks in parallel. The longest chain rule in current blockchain systems accepts only one of the branches after the network is recovered, and because of that, all blocks in other branches will be pruned. Losing a considerable number of mined blocks is not tolerable and significantly impacts the reliability of the ledger and miners' benefit. In this work, we aim to improve blockchain resilience by designing a partition-tolerance blockchain system that: (1) split into branches when network partition happens. (2) merge existing branches into one when the network goes back to normal. (3) ensure the safety and integrity of the blockchain. Newly mined blocks will be collectively signed by a group of miners with a BFT protocol similar to ByzCoin[Kogias et al., 2016], where the consensus group is formed by the miners of the previous w blocks. When a network partition happens, only part of the consensus group can be reached; thus the number of signers w_b of the new block will be less than w. If a block with w_b signers is published, every node in the partition learns that they are now in a branch with around w_b/w of the total hashing power, and it can be identified by the signature of the block. After the network recovers, miners will receive multiple branches, and they mine on a merging block which points to the last block of each branch as the parent blocks. The consensus group will be selected from each branch according to the branch size. Transactions in each partition are preserved after merging.
Cite as

Juncheng Fang, Farzad Habibi, Kevin Bruhwiler, Fayzah Alshammari, and Faisal Nawab. Improving Blockchain Resilience to Network Partitioning by Sharding (Poster). In 5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022). Open Access Series in Informatics (OASIcs), Volume 101, p. 9:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fang_et_al:OASIcs.FAB.2022.9,
  author =	{Fang, Juncheng and Habibi, Farzad and Bruhwiler, Kevin and Alshammari, Fayzah and Nawab, Faisal},
  title =	{{Improving Blockchain Resilience to Network Partitioning by Sharding}},
  booktitle =	{5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022)},
  pages =	{9:1--9:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-248-8},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{101},
  editor =	{Tucci-Piergiovanni, Sara and Crooks, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.FAB.2022.9},
  URN =		{urn:nbn:de:0030-drops-162762},
  doi =		{10.4230/OASIcs.FAB.2022.9},
  annote =	{Keywords: resilience, partitioning, blockchain, collective signing}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.37
Dalí: A Periodically Persistent Hash Map

Authors: Faisal Nawab, Joseph Izraelevitz, Terence Kelly, Charles B. Morrey III, Dhruva R. Chakrabarti, and Michael L. Scott

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

Abstract
Technology trends suggest that byte-addressable nonvolatile memory (NVM) will supplant many uses of DRAM over the coming decade, raising the prospect of inexpensive recovery from power failures and similar faults. Ensuring the consistency of persistent state remains nontrivial, however, in the presence of volatile caches; cached values can "leak" back to persistent memory in arbitrary order. To ensure consistency, existing persistent memory algorithms use expensive, explicit write-back instructions to force each value back to memory before performing a dependent write, thereby incurring significant run-time overhead. To reduce this overhead, we present a new design paradigm that we call periodic persistence. In a periodically persistent data structure, updates are made "in place," but can safely leak back to memory in any order, because only those updates that are known to be valid will be heeded during recovery. To guarantee forward progress, we periodically force a write-back of all dirty data in the cache, ensuring that all "sufficiently old" updates have indeed become persistent, at which point they become semantically visible to the recovery process. As an example of periodic persistence, we present a transactional hash map, Dalí, together with an informal proof of safety (buffered durable linearizability). Experiments with a prototype implementation suggest that periodic persistence can offer substantially better performance than either file-based or incrementally persistent (per-access write-back) alternatives.
Cite as

Faisal Nawab, Joseph Izraelevitz, Terence Kelly, Charles B. Morrey III, Dhruva R. Chakrabarti, and Michael L. Scott. Dalí: A Periodically Persistent Hash Map. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nawab_et_al:LIPIcs.DISC.2017.37,
  author =	{Nawab, Faisal and Izraelevitz, Joseph and Kelly, Terence and Morrey III, Charles B. and Chakrabarti, Dhruva R. and Scott, Michael L.},
  title =	{{Dal{\'\i}: A Periodically Persistent Hash Map}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{37:1--37:16},
  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.37},
  URN =		{urn:nbn:de:0030-drops-80148},
  doi =		{10.4230/LIPIcs.DISC.2017.37},
  annote =	{Keywords: data structure, nonvolatile memory, durable linearizability}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 2 2022
  • 1 2017

  • Refine by Author
  • 3 Nawab, Faisal
  • 2 Alshammari, Fayzah
  • 2 Bruhwiler, Kevin
  • 2 Fang, Juncheng
  • 2 Habibi, Farzad
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 3 Computer systems organization → Reliability
  • 1 Computer systems organization → Peer-to-peer architectures
  • 1 Software and its engineering → Mutual exclusion
  • 1 Theory of computation → Shared memory algorithms

  • Refine by Keyword
  • 1 Blockchain
  • 1 Partitioning
  • 1 Resilience
  • 1 Simulation
  • 1 blockchain
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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