Author name cluster

Ulrich Schmid

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

TCS Journal 2018 Journal Article

Gracefully degrading consensus and k -set agreement in directed dynamic networks

Martin Biely
Peter Robinson
Ulrich Schmid
Manfred Schwarz
Kyrill Winkler

We study distributed agreement in synchronous directed dynamic networks, where an omniscient message adversary controls the presence/absence of communication links. We prove that consensus is impossible under a message adversary that guarantees weak connectivity only, and introduce eventually vertex-stable source components (VSSCs) as a means for circumventing this impossibility: A VSSC ( k, d ) message adversary guarantees that, eventually, there is an interval of d consecutive rounds where every communication graph contains at most k strongly connected components consisting of the same processes (with possibly varying interconnect topology), which have no incoming links from outside processes. We present a consensus algorithm that works correctly under a VSSC ( 1, 4 E + 2 ) message adversary, where E is the dynamic network depth. Our algorithm maintains local estimates of the communication graphs, and applies techniques for detecting network stability and univalent system configurations. Several related impossibility results and lower bounds, in particular, that neither a VSSC ( 1, E − 1 ) message adversary nor a VSSC ( 2, ∞ ) one allow to solve consensus, reveal that there is not much hope to deal with (much) stronger message adversaries here. However, we show that gracefully degrading consensus, which degrades to general k-set agreement in case of unfavorable network conditions, allows to cope with stronger message adversaries: We provide a k-universal k-set agreement algorithm, where the number of system-wide decision values k is not encoded in the algorithm, but rather determined by the actual power of the message adversary in a run: Our algorithm guarantees at most k decision values under a VSSC ( n, d ) + MAJINF ( k ) message adversary, which combines VSSC ( n, d ) (with some small value of d, ensuring termination) with some information flow guarantee MAJINF ( k ) between certain VSSCs (ensuring k-agreement). Since related impossibility results reveal that a VSSC ( k, d ) message adversary is too strong for solving k-set agreement and that some information flow between VSSCs is mandatory for this purpose as well, our results provide a significant step towards the exact solvability/impossibility border of general k-set agreement in directed dynamic networks. Finally, we relate (the eventually-forever-variants of) our message adversaries to failure detectors. It turns out that even though VSSC ( 1, ∞ ) allows to solve consensus and to implement the Ω failure detector, it does not allow to implement Σ. This contrasts the fact that, in asynchronous message-passing systems with a majority of process crashes, ( Σ, Ω ) is a weakest failure detector for solving consensus. Similarly, although the message adversary VSSC ( n, d ) + MAJINF ( k ) allows to solve k-set agreement, it does not allow to implement the failure detector Σ k, which is known to be necessary for k-set agreement in asynchronous message-passing systems with a majority of process crashes. Consequently, it is not possible to adapt failure-detector-based algorithms to work in conjunction with our message adversaries.

Details DOI

TCS Journal 2011 Journal Article

Synchronous consensus under hybrid process and link failures

Martin Biely
Ulrich Schmid
Bettina Weiss

We introduce a comprehensive hybrid failure model for synchronous distributed systems, which extends a conventional hybrid process failure model by adding communication failures: Every process in the system is allowed to commit up to f ℓ s send link failures and experience up to f ℓ r receive link failures per round here, without being considered faulty; up to some f ℓ s a ≤ f ℓ s and f ℓ r a ≤ f ℓ r among those may even cause erroneous messages rather than just omissions. In a companion paper (Schmid et al. (2009) [14]), devoted to a complete suite of related impossibility results and lower bounds, we proved that this model surpasses all existing link failure modeling approaches in terms of the assumption coverage in a simple probabilistic setting. In this paper, we show that several well-known synchronous consensus algorithms can be adapted to work under our failure model, provided that the number of processes required for tolerating process failures is increased by small integer multiples of f ℓ s, f ℓ r, f ℓ s a, f ℓ r a. This is somewhat surprising, given that consensus in the presence of unrestricted link failures and mobile (moving) process omission failures is impossible. We provide detailed formulas for the required number of processes and rounds, which reveal that the lower bounds established in our companion paper are tight. We also explore the power and limitations of authentication in our setting, and consider uniform consensus algorithms, which guarantee their properties also for benign faulty processes.

Details DOI

TCS Journal 2011 Journal Article

The Asynchronous Bounded-Cycle model

Peter Robinson
Ulrich Schmid

This paper shows how synchrony conditions can be added to the purely asynchronous model in a way that avoids any reference to message delays and computing step times, as well as system-wide constraints on execution patterns and network topology. Our Asynchronous Bounded-Cycle (ABC) model just bounds the ratio of the number of forward- and backward-oriented messages in certain (“relevant”) cycles in the space–time diagram of an asynchronous execution. We show that clock synchronization and lock-step rounds can be implemented and proved correct in the ABC model, even in the presence of Byzantine failures. Furthermore, we prove that any algorithm working correctly in the partially synchronous Θ -Model also works correctly in the ABC model. In our proof, we first apply a novel method for assigning certain message delays to asynchronous executions, which is based on a variant of Farkas’ theorem of linear inequalities and a non-standard cycle space of graphs. Using methods from point-set topology, we then prove that the existence of this delay assignment implies model indistinguishability for time-free safety and liveness properties. We also introduce several weaker variants of the ABC model, and relate our model to the existing partially synchronous system models, in particular, the classic models of Dwork, Lynch and Stockmayer and the query–response model by Mostefaoui, Mourgaya, and Raynal. Finally, we discuss some aspects of the ABC model’s applicability in real systems, in particular, in the context of VLSI Systems-on-Chip.

Details DOI

I&C Journal 2003 Journal Article

Interval-based clock synchronization with optimal precision

Ulrich Schmid
Klaus Schossmaier

We present description and analysis of a novel optimal precision clock synchronization algorithm (OP), which takes care of both precision and accuracy with respect to external time. It relies upon the generic interval-based algorithm of Schmid and Schossmaier [Real-Time Syst. 12 (2) (1997) 173] and utilizes a convergence function based on the orthogonal accuracy algorithm of Schmid [Chicago J. Theor. Comput. Sci. 3 (2000) 3]. As far as precision is concerned, we show that OP achieves optimal worst case precision, optimal maximum clock adjustment, and optimal rate, as does the algorithm of Fetzer and Cristian [Proceedings 10th Annual IEEE Conference on Computer Assurance, Gaithersburg, MD, 1995]. However, relying upon a perception-based hybrid fault model and a fairly realistic system model, our results are valid for a wide variety of node and link faults and apply to very high-precision applications as well: Impairments due to clock granularity and discrete rate adjustment cannot be ignored here anymore. Our accuracy analysis focuses on the nodes’ local accuracy interval, which provides the atop running application with an on-line bound on the current deviation from external time. We show that this bound could get larger than twice the necessary lower bound (“traditional accuracy”), hence OP is considerably suboptimal in this respect.

Details DOI

TCS Journal 1993 Journal Article

The average CRI-length of a controlled ALOHA collision resolution algorithm

Ulrich Schmid

We investigate the expected CRI-length (collision resolution interval) of a hybrid collision resolution algorithm based on slotted ALOHA with controlled retransmission probability, e. g. , we study the average number of slots necessary for the resolution of an initial collision of multiplicity n. An algorithm similar to binary exponential backoff for adjusting the retransmission probability w. r. t. the channel load is used prior to the application of the ALOHA resolution algorithm, thus operating it in the region of nonexponential behaviour. Mellin-transform techniques are used for the derivation of an asymptotic expression for the desired quantity, which turns out to be O(n log n).

Details DOI