Related Experiment Video
Updated: Oct 14, 2025
05:30
Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
Published on: September 8, 2023
733
Redundancy in distributed proofs
Laurent Feuilloley1, Pierre Fraigniaud2, Juho Hirvonen3
1Universidad de Chile, Santiago, Chile.
Distributed Computing
|November 1, 2021
Summary
Distributed proofs use certificates and verifiers for network checks. Researchers found high redundancy allows perfect tradeoffs between certificate size and verification rounds.
Area of Science:
- Computer Science
- Distributed Computing
- Network Science
Background:
- Distributed proofs verify network properties using node-assigned certificates and verification algorithms.
- Existing mechanisms involve a prover assigning certificates and a verifier checking them.
Purpose of the Study:
- To analyze the redundancy in distributed proofs for network predicates.
- To establish tradeoffs between certificate size and verification rounds.
Main Methods:
- Investigated well-known distributed proof mechanisms.
- Analyzed the redundancy inherent in distributed proofs for various network predicates.
- Developed a framework to demonstrate tradeoffs between certificate size and verification rounds.
Main Results:
- Demonstrated that many network predicates possess distributed proofs with significant redundancy.
- Established perfect tradeoffs between the size of node-stored certificates and the number of verification rounds.
- Quantified the relationship between proof redundancy and protocol efficiency.
Conclusions:
- The high redundancy in distributed proofs is a key property that enables efficient verification.
- Optimal tradeoffs can be achieved between certificate storage and communication complexity in distributed verification protocols.
Related Concept Videos
01:21Distributed Loads: Problem Solving
818
Beams are structural elements commonly employed in engineering applications requiring different load-carrying capacities. The first step in analyzing a beam under a distributed load is to simplify the problem by dividing the load into smaller regions, which allows one to consider each region separately and calculate the magnitude of the equivalent resultant load acting on each portion of the beam. The magnitude of the equivalent resultant load for each region can be determined by calculating...
818
01:25Distribution Reliability and Automation
179
Distribution reliability in electrical power systems is critical for ensuring an uninterrupted power supply to consumers at minimal cost. According to IEEE Standard Terms, reliability is the probability that a device will function without failure over a specified time period or amount of usage. For electric power distribution, this translates to maintaining continuous power supply and addressing customer concerns over power outages. Several indices, as defined by IEEE Standard 1366-2012, are...
179
01:19Distributed Loads
691
Distributed loads are a common type of load that engineers and scientists encounter in various practical situations. Distributed loads often refer to a type of load spread over a surface or a structure and can be modeled as continuous force per unit area.
For example, consider a bookshelf filled with books stacked vertically adjacent to each other. The weight of the books is evenly distributed over the length of the shelf. As a result, the pressure at different locations on the surface of the...
For example, consider a bookshelf filled with books stacked vertically adjacent to each other. The weight of the books is evenly distributed over the length of the shelf. As a result, the pressure at different locations on the surface of the...
691
02:37Restarting Stalled Replication Forks
6.0K
DNA replication is initiated at sites containing predefined DNA sequences known as origins of replication. DNA is unwound at these sites by the minichromosome maintenance (MCM) helicase and other factors such as Cdc45 and the associated GINS complex.The unwound single strands are protected by replication protein A (RPA) until DNA polymerase starts synthesizing DNA at the 5’ end of the strand in the same direction as the replication fork. To prevent the replication fork from falling apart,...
6.0K
00:59Propagation of Uncertainty from Random Error
1.3K
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
1.3K
01:16Second Uniqueness Theorem
1.2K
Consider a region consisting of several individual conductors with a definite charge density in the region between these conductors. The second uniqueness theorem states that if the total charge on each conductor and the charge density in the in-between region are known, then the electric field can be uniquely determined.
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
1.2K