skip to main content


Search for: All records

Creators/Authors contains: "Zhang, Qinzi"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. This paper studies the feasibility of reaching consensus in an anonymous dynamic network. In our model, n anonymous nodes proceed in synchronous rounds. We adopt a hybrid fault model in which up to f nodes may suffer crash or Byzantine faults, and the dynamic message adversary chooses a communication graph for each round. We introduce a stability property of the dynamic network – (T,D)-dynaDegree for T ≥ 1 and n−1 ≥ D ≥ 1 – which requires that for every T consecutive rounds, any fault-free node must have incoming directed links from at least D distinct neighbors. These links might occur in different rounds during a T -round interval. (1, n−1)-dynaDegree means that the graph is a complete graph in every round. (1, 1)-dynaDegree means that each node has at least one incoming neighbor in every round, but the set of incoming neighbor(s) at each node may change arbitrarily between rounds. We show that exact consensus is impossible even with (1, n − 2)-dynaDegree. For an arbitrary T , we show that for crash-tolerant approximate consensus, (T , ⌊n/2⌋)-dynaDegree and n > 2f are together necessary and sufficient, whereas for Byzantine approximate consensus, (T , ⌊(n + 3f )/2⌋)- dynaDegree and n > 5f are together necessary and sufficient. 
    more » « less
    Free, publicly-accessible full text available July 29, 2025
  2. Free, publicly-accessible full text available July 21, 2025
  3. Free, publicly-accessible full text available May 7, 2025