Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userwChain: A Fast Fault-Tolerant Blockchain Protocol for Multihop Wireless Networks
170
0
0.0
(
0
)
Added by
Minghui Xu
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper presents $mathit{wChain}$, a blockchain protocol specifically designed for multihop wireless networks that deeply integrates wireless communication properties and blockchain technologies under the realistic SINR model. We adopt a hierarchical spanner as the communication backbone to address medium contention and achieve fast data aggregation within $O(log NlogGamma)$ slots where $N$ is the network size and $Gamma$ refers to the ratio of the maximum distance to the minimum distance between any two nodes. Besides, $mathit{wChain}$ employs data aggregation and reaggregation, and node recovery mechanisms to ensure efficiency, fault tolerance, persistence, and liveness. The worst-case runtime of $mathit{wChain}$ is upper bounded by $O(flog NlogGamma)$, where $f=lfloor frac{N}{2} rfloor$ is the upper bound of the number of faulty nodes. To validate our design, we conduct both theoretical analysis and simulation studies, and the results only demonstrate the nice properties of $mathit{wChain}$, but also point to a vast new space for the exploration of blockchain protocols in wireless networks.
rate research
Read More
Todays datacenter applications are underpinned by datastores that are responsible for providing availability, consistency, and performance. For high availability in the presence of failures, these datastores replicate data across several nodes. This is accomplished with the help of a reliable replication protocol that is responsible for maintaining the replicas strongly-consistent even when faults occur. Strong consistency is preferred to weaker consistency models that cannot guarantee an intuitive behavior for the clients. Furthermore, to accommodate high demand at real-time latencies, datastores must deliver high throughput and low latency. This work introduces Hermes, a broadcast-based reliable replication protocol for in-memory datastores that provides both high throughput and low latency by enabling local reads and fully-concurrent fast writes at all replicas. Hermes couples logical timestamps with cache-coherence-inspired invalidations to guarantee linearizability, avoid write serialization at a centralized ordering point, resolve write conflicts locally at each replica (hence ensuring that writes never abort) and provide fault-tolerance via replayable writes. Our implementation of Hermes over an RDMA-enabled reliable datastore with five replicas shows that Hermes consistently achieves higher throughput than state-of-the-art RDMA-based reliable protocols (ZAB and CRAQ) across all write ratios while also significantly reducing tail latency. At 5% writes, the tail latency of Hermes is 3.6X lower than that of CRAQ and ZAB.
In sensor networks communication by broadcast methods involves many hazards, especially collision. Several MAC layer protocols have been proposed to resolve the problem of collision namely ARBP, where the best achieved success rate is 90%. We hereby propose a MAC protocol which achieves a greater success rate (Success rate is defined as the percentage of delivered packets at the source reaching the destination successfully) by reducing the number of collisions, but by trading off the average propagation delay of transmission. Our proposed protocols are also shown to be more energy efficient in terms of energy dissipation per message delivery, compared to the currently existing protocol.
Known as a distributed ledger technology (DLT), blockchain has attracted much attention due to its properties such as decentralization, security, immutability and transparency, and its potential of servicing as an infrastructure for various applications. Blockchain can empower wireless networks with identity management, data integrity, access control, and high-level security. However, previous studies on blockchain-enabled wireless networks mostly focus on proposing architectures or building systems with popular blockchain protocols. Nevertheless, such existing protocols have obvious shortcomings when adopted in wireless networks where nodes have limited physical resources, fall short of well-established reliable channels, variable bandwidths impacted by environments or jamming attacks. In this paper, we propose a novel consensus protocol named Proof-of-Channel (PoC) leveraging the natural properties of wireless communications, and a BLOWN protocol (BLOckchain protocol for Wireless Networks) for wireless networks under an adversarial SINR model. We formalize BLOWN with the universal composition framework and prove its security properties, namely persistence and liveness, as well as its strengths in countering against adversarial jamming, double-spending, and Sybil attacks, which are also demonstrated by extensive simulation studies.
To save energy and alleviate interferences in a wireless sensor network, the usage of virtual backbone was proposed. Because of accidental damages or energy depletion, it is desirable to construct a fault tolerant virtual backbone, which can be modeled as a $k$-connected $m$-fold dominating set (abbreviated as $(k,m)$-CDS) in a graph. A node set $Csubseteq V(G)$ is a $(k,m)$-CDS of graph $G$ if every node in $V(G)backslash C$ is adjacent with at least $m$ nodes in $C$ and the subgraph of $G$ induced by $C$ is $k$-connected. In this paper, we present an approximation algorithm for the minimum $(3,m)$-CDS problem with $mgeq3$. The performance ratio is at most $gamma$, where $gamma=alpha+8+2ln(2alpha-6)$ for $alphageq4$ and $gamma=3alpha+2ln2$ for $alpha<4$, and $alpha$ is the performance ratio for the minimum $(2,m)$-CDS problem. Using currently best known value of $alpha$, the performance ratio is $lndelta+o(lndelta)$, where $delta$ is the maximum degree of the graph, which is asymptotically best possible in view of the non-approximability of the problem. This is the first performance-guaranteed algorithm for the minimum $(3,m)$-CDS problem on a general graph. Furthermore, applying our algorithm on a unit disk graph which models a homogeneous wireless sensor network, the performance ratio is less than 27, improving previous ratio 62.3 by a large amount for the $(3,m)$-CDS problem on a unit disk graph.
FP-Growth algorithm is a Frequent Pattern Min- ing (FPM) algorithm that has been extensively used to study correlations and patterns in large scale datasets. While several researchers have designed distributed memory FP-Growth algorithms, it is pivotal to consider fault tolerant FP-Growth, which can address the increasing fault rates in large scale systems. In this work, we propose a novel parallel, algorithm-level fault-tolerant FP-Growth algorithm. We leverage algorithmic properties and MPI advanced features to guarantee an O(1) space complexity, achieved by using the dataset memory space itself for checkpointing. We also propose a recovery algorithm that can use in-memory and disk-based checkpointing, though in many cases the recovery can be completed without any disk access, and incurring no memory overhead for checkpointing. We evaluate our FT algorithm on a large scale InfiniBand cluster with several large datasets using up to 2K cores. Our evaluation demonstrates excellent efficiency for checkpointing and recovery in comparison to the disk-based approach. We have also observed 20x average speed-up in comparison to Spark, establishing that a well designed algorithm can easily outperform a solution based on a general fault-tolerant programming model.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
