fbas_analyzer/analysis/
front_end.rs

1use super::*;
2
3use std::cell::RefCell;
4
5/// Front end for many interesting FBAS analyses. Among other things, it does ID space shrinking
6/// (which improves memory and performance when using bit sets) and caches the results of
7/// long-running computations.
8#[derive(Debug)]
9pub struct Analysis {
10    fbas_original: Fbas,
11    fbas_shrunken: RefCell<Fbas>,
12    shrink_manager: RefCell<ShrinkManager>,
13    hqi_cache: RefCell<Option<bool>>,
14    mq_shrunken_cache: RefCell<Option<Vec<NodeIdSet>>>,
15    mbs_shrunken_cache: RefCell<Option<Vec<NodeIdSet>>>,
16    mss_shrunken_cache: RefCell<Option<Vec<NodeIdSet>>>,
17}
18impl Analysis {
19    /// Start a new `Analysis`
20    pub fn new(fbas: &Fbas) -> Self {
21        debug!(
22            "Shrinking FBAS of size {} to set of satisfiable nodes (for performance)...",
23            fbas.number_of_nodes()
24        );
25        let (fbas_shrunken, shrink_manager) = Fbas::shrunken(fbas, fbas.satisfiable_nodes());
26        debug!(
27            "Shrank to an FBAS of size {}.",
28            fbas_shrunken.number_of_nodes()
29        );
30        Analysis {
31            fbas_original: fbas.clone(),
32            fbas_shrunken: RefCell::new(fbas_shrunken),
33            shrink_manager: RefCell::new(shrink_manager),
34            hqi_cache: RefCell::new(None),
35            mq_shrunken_cache: RefCell::new(None),
36            mbs_shrunken_cache: RefCell::new(None),
37            mss_shrunken_cache: RefCell::new(None),
38        }
39    }
40    /// Shrink the FBAS to its core nodes, i.e., to the union of all quorum-containing strongly
41    /// connected components. Future splitting sets returned by this object will miss any splitting
42    /// sets that do not consist entirely of core nodes and don't cause at least one pair of core
43    /// nodes to end up in non-intersecting quorums.
44    pub fn shrink_to_core_nodes(&mut self) {
45        debug!("Shrinking FBAS to core nodes...",);
46        let core_nodes_original = self.fbas_original.core_nodes();
47        let (new_fbas_shrunken, new_shrink_manager) =
48            Fbas::shrunken(&self.fbas_original, core_nodes_original);
49        debug!(
50            "Shrank to an FBAS of size {} (from size {}).",
51            new_fbas_shrunken.number_of_nodes(),
52            self.fbas_shrunken.borrow().number_of_nodes(),
53        );
54        debug!("Fixing previously cached values...");
55        self.reshrink_cached_results(&new_shrink_manager);
56        self.fbas_shrunken.replace(new_fbas_shrunken);
57        self.shrink_manager.replace(new_shrink_manager);
58    }
59    /// Nodes in the analyzed FBAS - not filtered by relevance.
60    pub fn all_nodes(&self) -> NodeIdSetResult {
61        self.make_unshrunken_set_result(self.fbas_original.all_nodes())
62    }
63    /// Nodes in the analyzed FBAS that can be satisfied given their quorum sets and the nodes
64    /// existing in the FBAS.
65    pub fn satisfiable_nodes(&self) -> NodeIdSetResult {
66        self.make_unshrunken_set_result(self.fbas_original.satisfiable_nodes())
67    }
68    /// Nodes in the analyzed FBAS that can never be satisfied given their quorum sets and the
69    /// nodes existing in the FBAS.
70    pub fn unsatisfiable_nodes(&self) -> NodeIdSetResult {
71        self.make_unshrunken_set_result(self.fbas_original.unsatisfiable_nodes())
72    }
73    /// Regular quorum intersection check via finding all minimal quorums (algorithm inspired by
74    /// [Lachowski 2019](https://arxiv.org/abs/1902.06493)).
75    pub fn has_quorum_intersection(&self) -> bool {
76        self.has_quorum_intersection_from_shrunken()
77    }
78    /// Quorum intersection check that works without enumerating all minimal quorums.
79    pub fn has_quorum_intersection_via_alternative_check(
80        &self,
81    ) -> (bool, Option<NodeIdSetVecResult>) {
82        if let Some(quorums) = find_nonintersecting_quorums(&self.fbas_shrunken.borrow()) {
83            assert!(quorums[0].is_disjoint(&quorums[1]));
84            (
85                false,
86                Some(self.make_shrunken_set_vec_result(quorums.to_vec())),
87            )
88        } else {
89            (true, None)
90        }
91    }
92    /// Minimal quorums - no proper subset of any of these node sets is a quorum.
93    pub fn minimal_quorums(&self) -> NodeIdSetVecResult {
94        self.make_shrunken_set_vec_result(self.minimal_quorums_shrunken())
95    }
96    /// Minimal blocking sets - minimal indispensable sets for global liveness.
97    pub fn minimal_blocking_sets(&self) -> NodeIdSetVecResult {
98        self.make_shrunken_set_vec_result(self.minimal_blocking_sets_shrunken())
99    }
100    /// Minimal splitting sets - minimal indispensable sets for safety.
101    pub fn minimal_splitting_sets(&self) -> NodeIdSetVecResult {
102        self.make_shrunken_set_vec_result(self.minimal_splitting_sets_shrunken())
103    }
104    /// For each minimal splitting set, returns two or more quorums that it's splitting, i.e.,
105    /// quorums that lack quorum intersection after the splitting sets are deleted from the FBAS.
106    pub fn minimal_splitting_sets_with_affected_quorums(
107        &self,
108    ) -> Vec<(NodeIdSetResult, NodeIdSetVecResult)> {
109        self.minimal_splitting_sets_with_affected_quorums_shrunken()
110            .into_iter()
111            .map(|(splitting_set, split_quorums)| {
112                let key = self.make_shrunken_set_result(splitting_set);
113                let result = self.make_shrunken_set_vec_result(split_quorums);
114                (key, result)
115            })
116            .collect()
117    }
118    /// Top tier - the set of nodes exclusively relevant when determining minimal quorums and
119    /// minimal blocking sets.
120    pub fn top_tier(&self) -> NodeIdSetResult {
121        self.make_shrunken_set_result(self.top_tier_shrunken())
122    }
123    /// If the top tier is symmetric, i.e., each two top-tier nodes have the same quorum set,
124    /// return the top tier's common quorum set. Else return `None`.
125    pub fn symmetric_top_tier(&self) -> Option<QuorumSet> {
126        find_symmetric_top_tier(&self.fbas_original)
127    }
128    /// Symmetric clusters - sets of nodes in which each two nodes have the same quorum set.
129    /// Here, each found symmetric cluster is represented by its common quorum set.
130    pub fn symmetric_clusters(&self) -> Vec<QuorumSet> {
131        find_symmetric_clusters(&self.fbas_original)
132    }
133
134    #[rustfmt::skip]
135    fn reshrink_cached_results(&mut self, new_shrink_manager: &ShrinkManager) {
136        let mq_shrunken_cache = self.mq_shrunken_cache.borrow().clone().map(|mq_shrunken| {
137            new_shrink_manager.reshrink_sets(&mq_shrunken, &self.shrink_manager.borrow())
138        });
139        let mbs_shrunken_cache = self.mbs_shrunken_cache.borrow().clone().map(|mbs_shrunken| {
140            new_shrink_manager.reshrink_sets(&mbs_shrunken, &self.shrink_manager.borrow())
141        });
142        self.mq_shrunken_cache.replace(mq_shrunken_cache);
143        self.mbs_shrunken_cache.replace(mbs_shrunken_cache);
144        self.mss_shrunken_cache.replace(None);
145    }
146    fn has_quorum_intersection_from_shrunken(&self) -> bool {
147        self.cached_computation(
148            &self.hqi_cache,
149            || {
150                let quorums = self.minimal_quorums_shrunken();
151                !quorums.is_empty() && all_intersect(&quorums)
152            },
153            "has quorum intersection",
154        )
155    }
156    fn minimal_quorums_shrunken(&self) -> Vec<NodeIdSet> {
157        self.cached_computation_from_fbas_shrunken(
158            &self.mq_shrunken_cache,
159            find_minimal_quorums,
160            "minimal quorums",
161        )
162    }
163    fn minimal_blocking_sets_shrunken(&self) -> Vec<NodeIdSet> {
164        self.cached_computation_from_fbas_shrunken(
165            &self.mbs_shrunken_cache,
166            find_minimal_blocking_sets,
167            "minimal blocking sets",
168        )
169    }
170    fn minimal_splitting_sets_shrunken(&self) -> Vec<NodeIdSet> {
171        self.cached_computation_from_fbas_shrunken(
172            &self.mss_shrunken_cache,
173            find_minimal_splitting_sets,
174            "minimal splitting sets",
175        )
176    }
177    fn minimal_splitting_sets_with_affected_quorums_shrunken(
178        &self,
179    ) -> Vec<(NodeIdSet, Vec<NodeIdSet>)> {
180        let minimal_splitting_sets = self.minimal_splitting_sets_shrunken();
181        minimal_splitting_sets
182            .into_iter()
183            .map(|splitting_set| {
184                let mut fbas = self.fbas_shrunken.borrow().clone();
185                fbas.assume_split_faulty(&splitting_set);
186                let split_quorums = find_nonintersecting_quorums(&fbas).unwrap();
187                (splitting_set, split_quorums)
188            })
189            .collect()
190    }
191    fn top_tier_shrunken(&self) -> NodeIdSet {
192        // The top tier is defined as either the union of all minimal quorums but can also be found
193        // by forming the union of all minimal blocking sets.
194        if self.mq_shrunken_cache.borrow().is_some() || self.mbs_shrunken_cache.borrow().is_none() {
195            involved_nodes(&self.minimal_quorums_shrunken())
196        } else {
197            involved_nodes(&self.minimal_blocking_sets_shrunken())
198        }
199    }
200
201    fn cached_computation_from_fbas_shrunken<R, F>(
202        &self,
203        cache: &RefCell<Option<R>>,
204        computation: F,
205        log_name: &str,
206    ) -> R
207    where
208        R: Clone,
209        F: Fn(&Fbas) -> R,
210    {
211        self.cached_computation(
212            cache,
213            || computation(&self.fbas_shrunken.borrow()),
214            log_name,
215        )
216    }
217    fn cached_computation<R, F>(
218        &self,
219        cache: &RefCell<Option<R>>,
220        computation: F,
221        log_name: &str,
222    ) -> R
223    where
224        R: Clone,
225        F: Fn() -> R,
226    {
227        let cache_is_empty = cache.borrow().is_none();
228        if cache_is_empty {
229            info!("Computing {}...", log_name);
230            let result = computation();
231            cache.replace(Some(result));
232        } else {
233            info!("Using cached {}.", log_name);
234        }
235        cache.borrow().clone().unwrap()
236    }
237
238    fn make_unshrunken_set_result(&self, payload: NodeIdSet) -> NodeIdSetResult {
239        NodeIdSetResult::new(payload, None)
240    }
241    fn make_shrunken_set_result(&self, payload: NodeIdSet) -> NodeIdSetResult {
242        NodeIdSetResult::new(payload, Some(&self.shrink_manager.borrow()))
243    }
244    fn make_shrunken_set_vec_result(&self, payload: Vec<NodeIdSet>) -> NodeIdSetVecResult {
245        NodeIdSetVecResult::new(payload, Some(&self.shrink_manager.borrow()))
246    }
247}
fbas_analyzer/analysis/front_end.rs

fbas_analyzer/analysis/
front_end.rs
