אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Granular synchrony assigns a timing type to each communication link, and existing solvability results prove both safety and liveness under the promise that the synchronous subgraph satisfies a graph-theoretic reachability condition. That condition is global and hard to verify, and a protocol that silently relies on it can violate agreement when it fails. We ask instead whether agreement and validity can be made to hold on every timing graph, with the graph condition confined to termination — a guarantee we call condition-independent safety.

We show that the answer depends sharply on topology knowledge and fault type. For crash faults with f >= n/2, no graph-agnostic protocol can be safe on every timing graph while terminating on every graph meeting the CFT condition, but knowing only the identities of one's synchronous neighbors is enough to break this impossibility. For Byzantine faults with 2f + 1 <= n <= 3f − 2, even local knowledge fails: faulty processes can hide the topology that distinguishes a good graph from a bad one.

We then give deterministic and randomized locally graph-aware CFT protocols with condition-independent safety. Both replace quorum intersection with a specialized collection primitive. A process disseminates its safety-relevant state to its synchronous neighbors before participating, so intersecting collections share not merely an identity but the value it contributed.