INFORMATION PROCESSING 77, B. GILCHRIST, EDITOR
`© IFIP, NORTH-HOLLAND PUBLISHING COMPANY (1977)
`
`DISTRIBUTED SYSTEMS-TOWARDS A FORMAL APPROACH
`
`GERARD LE LANN
`IRISA-Universite de Rennes-BP 25 A
`35 031 Rennes Cedex, France
`
`Packet-switching computer communication networks are examples of distributed systems. With the large
`scale emergence of mini and micro-computers, it is now possible to design special or general purpose
`distributed systems. However, as new problems have to be solved, new techniques and algorithms must be
`devised to operate such distributed systems in a satisfactory manner, In this paper, basic characteris(cid:173)
`tics of distributed systems are analysed and fundamental principles and definitions are given. It is
`shown that distributed systems are not just simple extensions of monolithic systems. Distributed control
`techniques used in some planned or existing systems are presented. Finally, a formal approach to these
`problems is illustrated by the study of a mutual exclusion scheme intended for a distributed envi(cid:173)
`ronment.
`
`1. INTRODUCTION
`
`cesses called logical entities.
`
`Computer communication networks using packet-swit(cid:173)
`ching technology provide for the interconnection of
`data-processing equipments of any kind. Such systems,
`sometimes simply referred to as computer networks,
`may be viewed as multi-macroprocessors whenever the
`goals of resource-sharing are achieved. With the
`large-scale emergence of mini and microcomputers, it
`is now possible to envision building general or spe(cid:173)
`cial purpose multimini and multimicrocomputers to be
`operated in a non-centralized manner. The need for
`automatic resource-sharing arises here as in a simi(cid:173)
`lar way it does for multimacroprocessor systems.
`
`Two kinds of resources must be considered :
`- system resources, multi-accessed by users and for
`which multiplexing is required (hidden sharing)
`- user resources, which users agree to share accord(cid:173)
`ing to some protocol of their own (explicit sharing).
`
`This paper discusses the problems of system resource(cid:173)
`sharing in a distributed environment. An example of a
`user-sharing problem is distributed data-base sharing.
`
`2. DISTRIBUTED SYSTEMS-ELEMENTS FOR A FORMAL APPROACH
`
`Experimental and public packet-switching computer
`communication networks have been built and operated
`since 1968 1 examples are Arpanet, [7], Cyclades,
`[13], EIN, [1], Telenet, [17] and Datapac, [4]. The
`communication subnet of these networks is an example
`of a distributed system : all nodes have equal
`rights and responsabilities and no central "con(cid:173)
`troller" is needed for the subnet to switch packets.
`Other examples are multicomputers like DCS {6] and
`Pluribus [8]. Finally, some multimicroprocessors
`currently planned by manufacturers will include "dis(cid:173)
`tributed features", in particular, those designed to
`have high availability characteristics.
`
`A definition of what is meant by distributed system
`is needed. Then, analysis of the fundamental proper(cid:173)
`ties of computer systems makes it possible to tell
`whether or not a given system has distributed fea(cid:173)
`tures.
`
`2.1 Definitions
`
`In a computer system, system resources are not
`accessed as such by users but through a set of ser(cid:173)
`vices usually referred to as an operating system.
`Examples of services which we call operating func(cid:173)
`tions are : communication, user scheduling, resource
`allocation, hardware resource handling, system data
`management, •.• These functions are run through pro-
`
`155
`
`Let F = {fi' ici}.be the set of the operating func(cid:173)
`tions and Ei = {e}. jcJ(i)} be the set of entities
`participating in fuctioQ fi. At any instant t, it is
`possible to.define stCejl as the instantaneous state
`of entity ej. It is therefore theoretically possible
`to define the global state of Ei at instant t as the
`vector St(Eil =
`{ ... , stCEiJl. ... for all jcJ(i)}.
`
`A system will be said to be fi·centralized if there
`exists kcJ(i) such that St(Eil is known to ek'
`
`An example is a system in which dim(Eil = 1 1 another
`example is a system in which entities run the ope(cid:173)
`rating function fi by using a common "system table".
`
`A system will be said to be totally centralized if
`it is fi-centralized for any ici.
`
`In contrast, a system will be said to be fi·distri(cid:173)
`buted if there does not exist kcJ(il such that
`St(Ei) is known to e~.
`
`A system will be said to be totally distributed if it
`is fi-distributed for any ici.
`
`Typical cases of distributed systems are systems in
`which cooperating entities do not share the same phy(cid:173)
`sical space and/or do not have a common time referen-·
`ce. In such systems, an entity may get either a par(cid:173)
`tial and coherent view of the system or a complete
`but incoherent view of the system, coherence meaning
`that observations are made at the same moment in the
`system (absolute time). This absence of uniqueness
`both in time and space has .very important conse(cid:173)
`quences.
`
`2.2 Time and space
`
`It is well known in Physics that the sentence "event
`E occured at time t" is meaningless if there is no
`indication about which time reference is used. Simi(cid:173)
`larly, the statement "I am in location 1" has no
`meaning as long as a space reference and a time re(cid:173)
`ference have not been defined. Then, to the purpose
`of describing the behaviour of an entity, we will use
`a precise time-space reference where internal states,
`time lengths, names and instants may be defined.
`
`We define the absolute Reference as the ideal refe(cid:173)
`rence such that speed of communication between this
`reference and any other time-space reference is infi(cid:173)
`nite and where every space location may be given a
`unique name.
`
`PALO ALTO NETWORKS Exhibit 1035 Page 1
`
`

`
`156
`
`1977 IFIP Congress Proceedings
`
`(i) System properties
`
`An entity may be viewed as a finite-state automaton;
`a decision to switch
`to a new state is possible
`through the observation of a specific sequence of
`events received during a time period (t-a, t), mea(cid:173)
`sured in the local time reference.
`
`property Q : a is a finite value
`property M : there are several time-space references
`for entities in the system
`
`All systems studied here are assumed to have proper(cid:173)
`ties Q and M.
`
`The propagation delay between two entities is the
`time needed, as measured in the absolute Reference,
`to transmit an elementary signal from one entity to
`the other.
`
`: for any pair of entities, propagation
`property P1
`delays --;:;r:e fixed, finite and known with absolute
`accuracy 1 they may be different for each pair
`property P2 : propagation delays are variable, fini(cid:173)
`te and their values are not known with absolute
`accuracy
`property_K3 : propagation delays are variable, fini(cid:173)
`te and known a posteriori with absolute accuracy
`property P4 : propagation delays are variable but
`their values are upper bounded.
`
`We should mention that these properties are common
`to all systems that are spacially distributed with
`finite propagation delays, including, for example,
`conventional logic design. Formalization of these
`properties was felt necessary so as to infer from
`them, basic principles which should be useful to
`distributed system designers.
`
`(ii) Classification
`
`- Systems with properties Q, M and P1 will be called
`Perfect Multireference Systems (PMSJ
`- Systems with properties Q, M and P3 will be called
`Quasi··Perfect Mul tireference Systems (QPMSJ
`- Systems with properties Q, M and P2 will be called
`Multireference Systems (MS).
`
`Let V be a sequence of events occuring within a sys(cid:173)
`tem ; let E be th!3 set of entities observing V. E(cid:173)
`vents may be observed in two ways : referenced wi(cid:173)
`thin a time-space reference Ri• iEI, with I being
`the set of the time-space references of E or refe(cid:173)
`renced within the absolute Reference. It may be in(cid:173)
`teresting to consider the following problems :
`(a) is it possible to build in Ri' for any iEI, the
`absolute chronological ordering of events (as obser(cid:173)
`ved in the absolute Reference) ?
`(b) do all the entities of E observe identically the
`set of events V ?
`
`Answers to these questions arr given in table 1.
`
`Table 1
`
`PMS
`
`QPMS
`
`(a)
`
`(b)
`
`YES
`
`YES*
`
`YES
`
`NO
`
`MS
`
`NO
`
`NO
`
`* if the value a (property Ql is the same for all
`entities in the system.
`
`A graphical representation of properties P2, P3 and
`P4 may help to answer questions (a) and (b) 1 an
`example is given in fig. 1.
`
`absolute
`
`time ~n A
`
`absolute
`
`time in B
`
`- - u+v
`
`Fig. 1
`
`In this example, three time-space references are re(cid:173)
`presented. Three events X, Y, Z originated in B must
`be reported to A and C. It is easy to see that there
`may exist cases for which A, B and C will not be in
`agreement ; for instance, C may miss the observation
`of event Z, whatever the finite value of u+v, Thus,
`if time is the only dimension used to achieve coope(cid:173)
`ration between entities, systems having property P4
`are identical to Multireference Systems.
`
`(a) Principle of time nondeterminancy
`
`For any given sequence of events, it is impossible to
`prove that two different entities will observe iden(cid:173)
`tically this sequence of events. An example of an e(cid:173)
`vent is a change of internal state 1 as these changes
`are observable from the outside only through communi··
`cation, one may state another principle ;
`
`(b) Principle of relativistic observation
`
`In a non-perfect system, it is impossible to prove
`that any two entities will have the same global view
`of a given subset of the system.
`
`As a consequence, the environment of any entity
`cannot perceive the pair (t, e(t)J with an absolute
`certainty, t being the entity local time and e(t)
`the current internal state of the entity. It will be
`possible either to know e(t) and to state that the
`entity will reach that state in a predefined time in(cid:173)
`terval 6t with some probability or to pick up an ins(cid:173)
`tant t and not being able to associate with certainty
`a given state e(t]. Then we have the following prin(cid:173)
`ciple :
`
`(c) Principle of state nondeterminancy
`
`The instantaneous state of an entity may only be ex(cid:173)
`pressed in terms of possible values associated with
`some probabilities.
`
`This means that the global state of a non-perfect
`system does not exist. As a consequence, according
`to the definition, these systems are totally distri-
`
`PALO ALTO NETWORKS Exhibit 1035 Page 2
`
`

`
`Distributed Systems-Towards a Formal Approach
`
`157
`
`buted systems.
`
`(il Congestion control
`
`It should be pointed out that if we agree to consi(cid:173)
`der infinite values for propagation delays, then the
`above principles are valid a fortiori.
`
`In fact, reunion of properties P2 and Q imposes that
`entities sometimes have to consider a propagation de(cid:173)
`lay as being infinite. This may. or may not be in
`accordance with reality. A propagation delay is tru(cid:173)
`ly infinite when the signal never reaches the desti(cid:173)
`nation entity; this may happen for two reasons
`- entities in charge of communication handling
`failed
`-
`the destination entity failed (was excluded from
`the system) before receiving the signal.
`
`In some cases, failure-tolerant techniques are manda(cid:173)
`tory. There is no essential difference with techni(cid:173)
`ques intended for distributed systems. An example of
`this approach is given in 4.
`
`As was pointed out before, system r·esources are
`accessed through operating functions. For every func(cid:173)
`tion, the decision about how and when to run the re-·
`lated entities is what is called control. Obviously,
`in a centralized system, control is performed by the
`"central" entity for that function (e~ in the defi(cid:173)
`nition), According to the basic principles, problems
`to be solved with distributed systems are :
`- control must be achieved without knowledge of the
`global state. Therefore, what is needed is that each
`entity behaves according to some algorithm working
`on an approximation of this state. In spite of th:l.s
`uncertainty, these algorithms must be such that en(cid:173)
`tities are kept in a legitimate state and that the
`global system behaviour is a convergent process
`-
`there is no entity which is, a priori, in charge of
`performing the control. Then, one is left with the
`problem of designing a common and secure protocol
`providing for the distribution of control among en(cid:173)
`tities. It must also be proved that algorithms and
`protocols do not lead to inconsistencies and dead(cid:173)
`locks.
`
`According to the bas:l.c principles, time should not be
`used to. achieve synchronization between entities.
`
`It it now possible to refine our terminology : what
`is called a distributed system in this paper is any
`non-perfect multireference system with distributed
`control for some of the operating functions.
`
`Examples of solutions to the above problems will now
`be presented.
`
`3. EXAMPLES OF DISTRIBUTED SYSTEM TECHNIQUES
`
`3.1 Congestion control arid end-to-end flow control
`in computer communication networks
`
`End-to-end flow control allows for monitoring the
`transmission of data between a source entity and a
`destination entity, a specific sub-system being in
`charge of performing the real transmission. The pur(cid:173)
`pose of congestion control is to guarantee that the
`resources of the transmission sub-system are always
`used bfficiently, i.e. that fair sharing of the sub(cid:173)
`system between several source-to-destination flows
`is possible and that deadlocks may be either avoided
`or suppressed. Referring to the introduction and
`thinking in terms of hierarchical systems, end-to(cid:173)
`end flow control is a problem of user resource(cid:173)
`sharing at a given level, whereas congestion control
`is a problem of system resource-sharing at the next
`level, this being true for any level ih the hierar(cid:173)
`chy. Similar views are discussed in detail in [15),
`
`Among the various existing schemes, isarithmic con(cid:173)
`gestion control is one for which extensive analysis
`has been performed, [16]. A constant amount of per(cid:173)
`mits is maintained over the network ; the algorithm
`for the entities is the following one : a new input
`packet is accepted only if the local permit value is
`greater than zero 1 when a packet reaches its desti(cid:173)
`nation, the entity may either store the correspond(cid:173)
`ing permit or ship that credit to another entity de(cid:173)
`pending on whether or not a given threshold value
`has been reached for the amount of local permits.
`
`Here, control is completely and permanently distri(cid:173)
`buted over the entities. Isarithmic control appears
`as an efficient mechanism fpr avoiding global con(cid:173)
`gestion. Nevertheless, this technique does not ful(cid:173)
`fill the requirement of resistance to entity failu(cid:173)
`res and no solution has been proposed as yet for
`controlling losses of permits,
`
`Most of congestion control mechanisms are uniform,
`in the sense that they do not discriminate between
`traffic sources. Some mechanisms, for example CLL in
`Cigale, [14), attempt to intervene only on those
`traffic ~ources which contribute to the load.
`
`(ii) ~d-to-end flow control
`
`The purpose of end-to-end flow control is to monitor
`data transmission between two entities such that the
`resources of these entities are properly utilized
`and the entities are kept synchronized. Because of
`different physical spaces and time references, exis(cid:173)
`tence of errors and duplication in transmission, tra(cid:173)
`ditionnal mechanisms like the producer-consumer sche(cid:173)
`me are not practicable ; this view is consistent •
`with the conclusions of a recent analysis described
`in [18].
`
`A basic scheme which is now widely accepted and was
`first introduced in Cyclades [3] is the Window mecha(cid:173)
`nism, [2, 19], Messages to be transmitted are sequen(cid:173)
`tially numbered by the sender. This allows the re(cid:173)
`ceiver to detect loss and duplication of messages.
`The flow of data is acknowledged up to the first
`missing message. Together with the acknowledgment
`number (a), a credit value (c) is returned to the
`sender meaning that transmission of messages is
`allowed up to number (a+c), It can easily be shown
`that the Window mechanism is resistant to erroneous,
`lost or duplicated messages.
`
`3,2 Load-sharing in multicomputer systems
`
`The operating function considered here :l.s processor(cid:173)
`assignment in a system where processors are logi(cid:173)
`cally equivalent, i.e. they all have the same capa(cid:173)
`bilities. Entities are processes responsible for
`computing processor load and running the load(cid:173)
`sharing algorithm. System-wide throughput and res(cid:173)
`ponse time are optimal when the load is equally dis(cid:173)
`tributed over the processors.
`
`Automatic load sharing should only be performed by
`the entities themselves and not by the external re(cid:173)
`questors. This provides for the necessary indepen(cid:173)
`dence between different logical levels in the sys(cid:173)
`tem. As a consequence, processor failures, ·extension/
`reduction of the configuration and changes in the
`hardware topology are totally irrelevant to the
`other system levels.
`
`Two methods for achieving automatic load-sharing
`are now presented.
`
`(i) Diffusion technique
`
`This technique is similar to adaptive routing mecha(cid:173)
`nisms. For every entity, the notion of a neighbour
`is defined ; regularly, entities exchange a load-
`
`PALO ALTO NETWORKS Exhibit 1035 Page 3
`
`

`
`158
`
`1977 IFIP Congress Proceedings
`
`vector V = {1, i} with their neighbours, l being the
`minimum value of the loads most recently received by
`the entity and i being the identity of the corres(cid:173)
`ponding processor. Then, at any moment, upon receiv(cid:173)
`ing an external request, an entity is able to route
`it immediately to the less loaded processor. Stabi(cid:173)
`lity conditions must be computed according to hard(cid:173)
`ware performances and processing requirements.
`
`(ii) Circulating vector· technique
`
`A successor is defined for each entity, such that
`all entities are located on a virtual ring. On this
`ring, one or several load vectors circulate, the di(cid:173)
`mension of the vectors being equal to the number of
`entities, The individual algorithm simply consists
`of each entity updating its own component with the
`current load value upon receiving a vector, record(cid:173)
`ing a copy of it and transmitting this vector on to
`the ring. Notice that loss of a vector or creation
`of several vectors is not catastrophic to the system.
`
`The efficiency of these techniques has been eva-11
`luated by means of a simulation model, Some results
`may be found in [10]. These mechanisms may be used
`as they stand to distribute the load evenly in a
`system or they may be used in connection with some
`other mechanisms when it is necessary to take loca(cid:173)
`lity constra:i.nts into account.
`
`3.3 Distributed allocation of resources
`
`The problem is the following one : U-entities (users)
`must be allocated R-entities (resources) l specific
`entities are in charge of multiplexing several U(cid:173)
`entities and performing the resource allocation (in
`a system described somewhere else [9], these enti(cid:173)
`ties are called controllers). A communication sub(cid:173)
`system is used by the controllers to send their re(cid:173)
`quests directly to R-entities ; how should deadlocks
`be avoided ? From sever·al techniques, the circu(cid:173)
`lating control token scheme is now presented,
`
`For every controller, a successor is defined such
`that contr·ollers are located on a virtual ring. One
`representation of a n-controller ring may be {i·+i+1,
`modulo n, ig(O,n-1)}; each integer i being the iden(cid:173)
`tity of a controller. Asynchronous and natural time
`division is achieved by the means of a unique con(cid:173)
`trol token circulating on this virtual ring ; a con(cid:173)
`troller is allowed to send allocation requests only
`when it owns the control token ; R-entities are pro(cid:173)
`vided with waiting files in which requests are re(cid:173)
`corded, up to a pre-defined limit (congestion can-
`t roll. When all requests have been answered, the con(cid:173)
`trol token is transmitted to the successor on the
`ring l
`later, the U-entity will receive a message
`from each requested R-entity indicating that it has
`now moved to the first position in the file and that
`utilization of the resource is allowed. The average
`number of R-entities to be requested at a time is
`not independent of the circulating speed of the con(cid:173)
`trol token and it influences directly the system(cid:173)
`wide job throughput. Extensive simulation described
`in [12] has been performed to evaluate the perfor(cid:173)
`mances of this technique.
`
`This is an example of a technique which must be
`shown to survive failures ; of major concern is the
`guarantee that the control token (CT) is never lost
`and that there is only one token on the ring. A pro(cid:173)
`tocol fulfilling this requirement exists and is now
`presented,
`
`4. A SECURE PROTOCOL TO ACHIEVE MUTUAL EXCLUSION IN
`A DISTRIBUTED SYSTEM
`
`We will discuss problems related mainly to control(cid:173)
`ler failures such as what we should do when the con(cid:173)
`troller which owns the CT goes down and thus removes
`the CT fmm the ring ?
`
`4.1 Ring failures
`
`First, assume that an error control mechanism based
`on "life messages", [7, 9]. is provided at the hard(cid:173)
`ware level which allows for the virtual ring recon(cid:173)
`figuration. Then, controller i may be temporarily
`excluded from the ring, the successor of controller
`i-1 being controller i+1.
`
`Second, let us briefly discuss problems related to
`failures of the interconnection structure (unibus,
`multibus, digital loop, multidrop telephone line,
`radio/satellite communication channel, matrix switch,
`store-and-forward networks, ••. l. Transmission err·ors
`are easily recovered by using a simple mechanism
`like the Window technique. If the structure does not
`provide for more than one physical path between any
`pair of controllers, then it is of no help to design
`a failure tolerant distributed protocol ; it the
`structure does so, then failure of a structure sub(cid:173)
`set can be controlled and recovered by using well
`known techniques like adaptive routing or alternate
`fixed routing.
`
`4.2 The protocol
`
`The protocol consists of a precedence rule and an
`election phase algorithm.
`
`(i) Hypothesis
`
`- controllers identities are integer values : (0,
`n-1) for n controllers (H1)
`·- controllers may access the header of messages cir(cid:173)
`culating on the ring
`-
`the CT and other tokens are empty messages (only
`the header)
`- each controller owns a timer ; this timer is reset
`at each CT occurence
`-
`the system is asynchronous ; timer values are not
`necessarilly identical ; if they are, no consequence
`can be drawn from this (principle of time nondeter(cid:173)
`minancyl
`J each controller is provided with its own
`time clock (H2l
`-· the sequence of messages on the ring is unchanged,
`i.e. messages received by a controller are retrans(cid:173)
`mitted FIFO
`- creation of a CT is an instantaneous action
`-· when timer awakes, the controller generates ins-
`tantaneously a token carrying :i.ts own identity
`this token is candidate for being the new CT
`
`(ii) Precedence rule
`
`A controller which has generated a token and which
`receives the CT before its own token has completed a
`period must remove this token from the ring.
`
`Indeed, "ear·ly" generation of a token may be due to
`large round trip times for the CT, short timer va(cid:173)
`lues and so forth. In any case, as a CT is circu(cid:173)
`lating on the ring, there is no need for local ac(cid:173)
`tion.
`
`(iii) Election phase algorithm
`
`The problem is to design an algorithm such that one
`can prove that, when the control token (CTl is lost,
`there is a unique controller to be elected as res(cid:173)
`ponsible for regenerating a new CT (constraint A),
`in a finite time delay (constraint B).
`
`Let I be the set of controllers participating in the
`election i.e. controllers for which timers awake
`between the loss of CT and regeneration of a new CT;
`let S(i), igi, be the set of tokens identities as
`recorded by controller i after a complete rotation of
`token i
`; obviously, one of these identities will be
`i itself.
`
`Uniqueness in the choice for several controllers is
`guaranteed if
`
`PALO ALTO NETWORKS Exhibit 1035 Page 4
`
`

`
`the algorithm is unique for all con-
`
`condition (a)
`tr·ollers
`value of S(i), iEI is the same for
`condition (b)
`all controllers.
`
`Unfortunately, there are cases for which condition
`(b) is not true, see fig. 2 1 Tj being generated af(cid:173)
`ter T i crossed contra ller j and before T k crossed
`fhe same controller, one is left with a situation
`where S(il = {Lk} and S(k) = {i.j,k}.
`
`One may be tempted to solve the problem by using one
`of these solutions
`Solution 1 : for each token 6rossing a controller,
`the local timer is reset to its initial value ; a
`new token is generated locally only when the timer
`awakes.
`Solution 2 : solution 1 plus : each controller must
`remove from the ring any token circulating after the
`first token so that only that one will be left on
`the ring.
`
`It should be noted that in this case, all control(cid:173)
`lers, even those not participating in the election
`(which means permanently), are required to record
`crossing of any token. It is not difficult to con(cid:173)
`clude that these solutions are not acceptable, becau(cid:173)
`se of H2 and condition (b),
`
`T
`X
`Ti and T k have completed a revolution
`Fig. 2
`
`As the set of controllers is strictly ordered (H1),
`a simple algorithm may be proposed
`0 : if i =min S(i), then entity i immediately gene(cid:173)
`rates the new CT
`
`In order to demonstrate that ll satisfies constraint
`A, let us describe first the state-transition table
`of entity ion the ring (table 2).
`
`Table 2
`
`~ 0
`
`s
`
`.
`
`1
`
`a
`
`ll
`
`~
`
`ll
`
`ll
`
`ll
`
`a
`
`Cl
`
`Cl
`
`2
`
`a
`
`'1:(
`
`1f
`
`3
`
`a
`
`ll
`
`'6
`
`4
`
`Cl
`
`a*
`
`Cl
`
`Distributed Systems-Towards a Formal Approach
`
`159
`
`Comments :
`0
`awaking of the timer
`1
`reception of the control token
`2
`reception of a candidate token, the identity of
`which is smaller than i
`reception of a candidate token, the identity of
`which is larger than i
`reception of the candidate token i (after one
`complete revolution)
`idle, control token timer is set
`candidate token timer is set and i is prepared
`to regenerate a new contr·ol token
`candidate token timer is set and i is not res(cid:173)
`ponsible for the control token regeneration
`generation of the new control token and imme(cid:173)
`diate switching to state a
`
`3
`
`4
`
`a
`ll
`
`a*
`
`We will use the following notation
`I(CT,xl
`instant of control token reception by en(cid:173)
`tity X
`I(t(x],y) = instant of reception of the candidate to(cid:173)
`ken x by entity y
`instant of generation of a candidate token
`by entity x
`occurence of event 4.
`
`I(x,ol
`
`I(x,xl
`
`Let us imagine that two entities x and y generate
`"simultaneously" (during the same revolution on the
`ring) a control token, thus violating constraint A
`and we will show that this situation is impossible.
`Let us assume, for example, that icentity (x) < iden(cid:173)
`tity (y).
`
`Entity y will generate a new token if and only if
`state (y] at time I (y, y J is ll ; this implies : 1 and
`~between I(y,o) and I(y,yl where; means non occu(cid:173)
`rence of event n.
`
`Identically, assuming that x will generate a new to(cid:173)
`: T between I(x,ol and I(x,xl.
`ken implies (x < y)
`
`It is easy to show that a subset of these conditions
`leads to a contradiction.
`
`I(t(xl,yl > I(y,y) for
`~between I(y,ol and I(y,y)
`entity y ; 1 between I(x,ol and I(x,xl
`I(CT,xl >
`I(x,xl with the CT received by x being the token ge(cid:173)
`nerated by y. This constraint and the FIFO hypothe(cid:173)
`sis imply that for entity y : I(t(x],y) < I(y,y).
`
`It has thus been demonstrated that the CT cannot be
`generated by two different entities during one revo~
`lution on the ring.
`
`Constraint B is obviously fulfilled by 0 and it is
`possible to compute bound values for the time T
`needed to regenerate a new CT. If xis the identity
`of the first controller to initiate the election pha(cid:173)
`se after loss of the CT and if e is the maximum value
`of the time required for a controller to process a
`token and to hand it down to its neighbour on the
`ring, then we have :
`R ~ T ~ x(R - 9) + e
`T being counted from the instant of timeout for con(cid:173)
`troller x,
`
`(iv) Failures during the election phase
`
`When considering the failure of a controller partici(cid:173)
`pating in the election phase, two problems must be
`tackled, Failure of the controller which is precisely
`the one being elected by the other controllers as
`responsible for generating the new CT is not catas(cid:173)
`trophic ; protection against infinite waiting is pro(cid:173)
`vided by timers
`the election phase will only be
`longer than for a failure-free situation.
`
`The other problem is what t8 do with tokens generated
`by controllers which have failed before tokens have
`completed a period. One protocol may be that only
`controller i is allowed to remove Ti from the ring.
`
`PALO ALTO NETWORKS Exhibit 1035 Page 5
`
`

`
`[9] G. Le Lann and R. Negaret, Operating pr·inciples
`for a distributed multimicroprocessor, First
`European Symp. on Microarchitecture of C'OrfiPUter
`Systems, North-Holland, Nice, June 1975, 219-
`222.
`[10] G. Le Lann et al., Distribution of access and
`data in large data bases, Int. Symp. on Techno(cid:173)
`logy for Selective Dissemination of Information,
`IEEE, San-Marino, Sept. 1976, 94-98.
`[11] G. Le Lann, Introduction ~ !'analyse des syste(cid:173)
`mes multireferentiels, These de Ooctorat d'E(cid:173)
`tat, University of Rennes, May 1977, 180 p.
`(French).
`[12] R. Negaret, Etude de !'allocation de ressources
`dans les systemes informatiques repartis, These
`de Doctorat de 39 cycle, University of Rennes,
`Dec. 1976, 190 p. (French).
`[13] L. Pouzin, Presentation and major design as(cid:173)
`pects of the Cyclades computer network, Third
`ACM/IEEE Data Communication Symp., Tampa, Nov.
`1973, 80-85.
`'
`[14] L. Pouzin, Distributed congestion control in a
`packet network : the channel load limiter, INWG
`Protocol Note 36, June 1976, 6 p.
`[15] L. Pouzin, Flow control in data networks-methods
`and tools, Third ICCC. Toronto, Aug. 1976, 467-
`474.
`[16] W.L. Price, Simulation of packet-switching net(cid:173)
`works controlled on isarithmic principles,
`Third ACM/IEEE Data Communication Symp .. Tampa,
`·
`Nov. 1973, 44-49.
`[ 17] L. G. Roberts~. Telenet principles and practice,
`On Line Symp. on Communications Networks,
`London, Sept. 1975, 315-329.
`. .,
`[18] D.L. Russell and T .H. Bradt. Error res)llnchroni(cid:173)
`zation in producer-consumer systems, Fifth ACM
`Symp. on Operating Systems Principles:-Austin,
`Nov. 1975, 106-113.
`[19] H. Zimmermann, The Cyclades end-·to-end protocol,
`Fourth ACM/IEEE Data Communication Symp., Quebec
`City, Oct. 1975, 7.21-7.26.
`
`160
`
`1977 IFIP Congress Proceedings
`
`This is acceptable provided that failures are either
`exceptional or of short dur·ation. Otherwise, other
`controllers must be allowed to destroy ~okens per(cid:173)
`taining to dead controllers 1 for instance, the last
`elected controller may be responsible for this.
`
`Another solution is based on mutual help and mutual
`suspicion principles being applied in the whole sys(cid:173)
`tem.
`
`When a controller failur·e is detected, its neigh(cid:173)
`bours help to "clean" the situation. One of the ac(cid:173)
`tions to be taken could be precisely to withdraw
`from the ring all tokens and messages generated by
`this failing controller. These actions are then de(cid:173)
`pendant upon an error control mechanism situated at
`another logical level in the system.
`
`Problems related to ring reconfiguration after a
`failure, r·eintegration of a controller on the ring
`as well as a second protocol achieving mutual exclu(cid:173)
`sion are analysed in detail in [11].
`
`We should mention the practical utility of the elec(cid:173)
`tion protocol. Controllers are autonomous not only
`while the system is running but also at the initia(cid:173)
`lization phase. No ex~ernal action is needed as con(cid:173)
`trollers will undertake spontaneously an election
`when the system is turned on. In this sense, this
`approach is different from the one described in [5]