Common use of Thesis Outline Clause in Contracts

Thesis Outline. ‌ The remainder of this thesis is organized as follows. In Chapter 2 we present our wab based consensus protocols, namely B -Consensus and R -Consensus, in Sec- tion 2.2. Also in Chapter 2, we present our multicoordinated consensus algorithm, in Section 2.3. In Chapter 3 we focus on the generalized consensus problem. In specific, in Section 3.4 we present our multicoordinated generalized consensus pro- tocol, Multicoordinated Paxos. In Section 3.5 we show how to instantiate Multico- ordinated Paxos to solve the generic broadcast problem. In Chapter 4 we deal with agreement among agents organized in groups and present our basic and extended protocols for such a scenario. We present our last contribution, the log service spec- ification and implementations, in Chapter 5. Finally, in Chapter 6, we conclude this thesis and point some directions for future works. Chapter 2‌ Multicoordinated Consensus 2.1 Consensus and the FLP Impossibility Result‌ Distributed problems and algorithms are commonly described in terms of a task to be attained by homogeneous agents. The standard specification of the consensus problem, for example, states that “a set of agents must eventually agree on a value, in spite of a maximum number of failures”. As a result, algorithms for such prob- lems are also given in terms of homogeneous agents with similar behavior. Because processes play different roles in real systems, we use a different approach and spec- ify problems and algorithms in terms of the roles which agents play. For example, in a client/server architecture, we refer to client agents and server agents, or to sender and receiver in a mailing system. In the case of consensus, we use three kinds of agents: proposer, learner, and acceptor. Because consensus subsumes many agreement problems, the same sets of agents may also make sense it their specifications and, hence, we will adopt the same terminology. To the best of our knowledge, specifications based on roles was introduced by Lamport [Lamport, 1998]. In the consensus problem, agents must agree on a single value out of a given set of proposals. Proposer agents issue proposals out of which one will become the decision. Once a decision is reached, learners must become aware of its value. In the context of a common distributed application, state machine replication, pro- posers can be thought of as clients issuing commands and learners as the application servers that execute the decided commands. For this reason, we interchangeably re- fer to proposals also as commands. Clients might also be learners to know whether their issued commands were accepted by the system to be executed. Formally, the safety requirements of consensus are three [Lamport, 2006b]: While the safety requirements are stated in terms of proposers and learners, the liveness requirement is stated over the set of acceptors. This happens because, as we pointed out, proposer and learner roles are associated with clients of applications, and it would be unreasonable requiring them not to fail. Acceptors, conversely, are part of the application infrastructure, and it is more reasonable to make reliability assumptions about them. We call a quorum any finite set of acceptors that is large enough not to forbid liveness and define the liveness requirement of consensus as follows: Liveness: For any proposer p and learner l , if p, l , and a quorum Q of acceptors are nonfaulty and p proposes a value, then l eventually learns some value. Under the assumed asynchronous crash-recovery model, it is well known that no fault-tolerant consensus algorithm can ensure termination in the presence of failures [▇▇▇▇▇▇▇ et al., 1985]. Phrased in terms of acceptors, this result implies that quorums must equal the set of all acceptors. Hence, algorithms must make extra assumptions about the system to ensure liveness if they must be fault-tolerant.