Common use of Roadmap Clause in Contracts

Roadmap. The paper is composed of 6 sections. Section 2 describes the anonymous shared memory model and the failure detector class AΩ. An anonymous consensus is presented in Section 3. Its generalization to the case of systems with homonym processes follows (Section 4). Section 5 surveys related work and Section 6 concludes the paper. 2 System model Anonymous shared memory model. We consider a system Π of n ≥ 2 deterministic processes. Processes are anonymous: they do not have identifiers, and they execute identical algorithms. The total number of processes n is however known by the processes. The system is asynchronous, in the sense that each process runs at its own speed, independently of the other processes. Processes communicate with each other by reading and writing atomic shared registers (they are linearizable [26]). Registers are multi-writer and multi-reader: every register can be written in, or read from, by every process. In the pseudo-code we use to describe our algorithm, shared objects are denoted by upper-case letters, while lower-case identifiers are reserved for processes’ local variables. Failures and failure detectors. Processes may crash. A process is correct in an execution if it never crashes in this execution; otherwise it is faulty. We make no assumption on the number of crashes that may occur during a run. As noted in the Introduction, a failure detector is a distributed oracle that provides processes with possibly unreliable information about failures [11]. Several classes of failure detectors suited to anonymous systems have been defined [8]. The failure detector we consider is anonymous Ω, denoted hereafter AΩ. Each process is provided with a primitive AΩ.query(), which returns true or false. The following property, termed eventual leadership is ensured: there exists some correct process p0 such that eventually every AΩ.query() always returns true at p0, and false at every other process.

Roadmap. The paper is composed of 6 sections. Section 2 describes the anonymous shared memory model and the failure detector class AΩ. An anonymous consensus is presented in Section 3. Its generalization to the case of systems with homonym processes follows (Section 4). Section 5 surveys related work and Section 6 concludes the paper. 2 System model Anonymous shared memory model. We consider a system Π of n ≥ 2 deterministic processes. Processes are anonymous: they do not have identifiers, and they execute identical algorithms. The total number of processes n is however known by the processes. The system is asynchronous, in the sense that each process runs at its own speed, independently of the other processes. Processes communicate with each other by reading and writing atomic shared registers (they are linearizable [26]). Registers are multi-writer and multi-reader: every register can be written in, or read from, by every process. In the pseudo-code we use to describe our algorithm, shared objects are denoted by upper-case letters, while lower-case identifiers are reserved for processes’ local variables. inria-00625704, version 1 - 22 Sep 2011 Failures and failure detectors. Processes may crash. A process is correct in an execution if it never crashes in this execution; otherwise it is faulty. We make no assumption on the number of crashes that may occur during a run. As noted in the Introduction, a failure detector is a distributed oracle that provides processes with possibly unreliable information about failures [11]. Several classes of failure detectors suited to anonymous systems have been defined [8]. The failure detector we consider is anonymous Ω, denoted hereafter AΩ. Each process is provided with a primitive AΩ.query(), which returns true or false. The following property, termed eventual leadership is ensured: there exists some correct process p0 such that eventually every AΩ.query() always returns true at p0, and false at every other process.