Scribd
Upload
11 views77 pages

Distributed Computing 2

The document discusses the architecture of distributed programs, which consist of asynchronous processes that communicate through message passing without shared memory or global clocks. It introduces models of distributed executions, including causal precedence relations and logical clocks, which help manage the ordering of events and messages in distributed systems. Additionally, it covers scalar and vector time mechanisms for tracking event sequences and ensuring consistency in message delivery across processes.

Uploaded by

Daram Vishnu Vishnuvardhan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
11 views77 pages

Distributed Computing 2

The document discusses the architecture of distributed programs, which consist of asynchronous processes that communicate through message passing without shared memory or global clocks. It introduces models of distributed executions, including causal precedence relations and logical clocks, which help manage the ordering of events and messages in distributed systems. Additionally, it covers scalar and vector time mechanisms for tracking event sequences and ensuring consistency in message delivery across processes.

Uploaded by

Daram Vishnu Vishnuvardhan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Ppplitedtons L g-commeree, yederated heavatng , mobile yobely pe @isernateve —Oendevert—_ receive event Ly The TS she oan om mesinge lags A Distributed Program © A distributed program is composed of a set of asynchronous processes, pr, P2y sy Pir soos Pre - © The processes do not shate a global memory and communicate solely by passing messages. @ The processes do not share a global clock that is instantaneously accessible to these processes. @ Process execution and message transfer are asynchronous. © Without loss of generality, we assume that each process is running on a: different processor. @ Let Gj denote the channel from process p; to process pj and let my denote a message sent by pj; to pj. © The message transmission delay is finite and unpredictable. -~-- ns sssc NNNNNNNNNN A Model of Distributed Executions ® The execution of a process consists of a sequential execution of its actions ® The actions are atomic and the actions of a process are modeled as three types of events, namely, internal events, message send events, and message receive events, @ Let ef denote the xth event at process py ® For a message m, let send(m) and rec(m) denote its send and receive events respectively ® The occurrence of events changes the states of respective processes and channels. @ An internal event changes the state of the process at which it occurs. ® A send event changes the state of the process that sends the message and the state of the channel on which the message is sent. © A receive event changes the state of the process that receives the message and the state of the channel on which the message is received A Model of Distributed Executions. Causal Precedence Relation © The execution of a distributed application results in a set of distributed events produced by the processes. © Let H=Ujh; denote the set of events executed in a distributed computation. © Define a binary relation — on the set H as follows that expresses causal dependencies between events in the distributed execution. mit ie, or Vex, Vey GH, ef > of ef mix or Tran hos Trans! Shei aes a © The causal precedence relation induces an irreflexive partial order on the events of a distributed computation that is denoted as 1=(H, —). yA fe Corn We Te erp FIFO we a cm tt Counrey MS Sag Models of Communication Networks ® The “causal ordering” model is based on Lamport's “happens before relation, ® A system that supports the causal ordering model satisfies the following property: CO: For any two messages mj and my, if send(m,) send(myj), then rec(m) —» rec(my). This property ensures that Causally related messages destined to the same destination are delivered in an order that is consistent with their causality relation ° Causally ordered delivery of messages implies FIFO message delivery. (Note that CO c FIFO ¢ Non-FIFO.) © Causal ordering model considerably simplifies the design of distributed algorithms because it provides a built-in synchronization. oot ax ve peed h ON w Sendo) % Saad bon) => Sender.) —> Sead ( (rs) —> Sond Cm) — > Sen} (03) 5 ad Bar Qecy (e)) > Recv (™) bog Implementing Logical Clocks © + A logical global clock, denoted by gc), that is a representation of process p's local view of the logical global time. Typically, lc is a part of gai. The protocol ensures that a process's logical clock, and thus its view of the global time, is managed consistently. The protocol consists of the following two rules: @ RI: This rule governs how the local logical clock is updated by a process when it executes an event. © R2: This rule governs how a process updates its global logical clock to update its view of the global time and global progress, © Systems of logical clocks differ in their representation of logical time and also in the protocol to update the logical clocks Scalar Time @ Proposed by Lamport in 1978 as an attempt to totally order events in a distributed system. © Time domain is the set of non-negative integers. © The logical local clock of a process p; and its local view of the global time ate squashed into one integer variable G, @ Rules RI and R2 to update the clocks are as follows: © Ri: Before executing an event (send, receive, or internal), process p; executes the following: =C4d (d>0) In general, every time R1is executed, d can have a different value; however, typically d is kept at 1. Scalar Time @ R2: Each message piggybacks the clock value of its sender at sending time. When a process p; receives a message with timestamp Cinsg, it executes the following actions: a > G i= max(Ci, Coup) » Execute RI > Deliver the message. @ Figure 3.1 shows evolution of scalar time Scalar Time Evolution of scalar time: Figure 3.1: The space-time diagram of a distributed execution, an wa 87 the receipt of Vector Time ° i i alue of the vec i r ecu ° am ctor clock h y ° Vector Time Comparing Vector Timestamps @ The following relations are defined to compare two vector timestamps, vh and vk: vh=vk (vk < vi) @ If the process at which an event occurred is known, the test to compare two timestamps can be simplified as follows: If events x and y respectively occurred at processes p; and p; and are assig respectively, then ed timestamps vh and vk > vhli] < vk(i] v4 x|ly vil] > vALi) A vil] < AL n—7 et va Ci « VSO wily (vace) 29K) 9 cont) <9) ¢ Ri), then the i component of vector clock at pi s the number of events that have occurred at p; until t ¢ has timestamp vh, vil] denotes the number 0 ess p; that causally precede e. Clearly, > otal number of events that causally precede omputation. Vector Time Process p; uses the following two rules R1 and R2 to update its clock: © Ri: Before executing an event, process p; updates its local logical time as. follows: . veili] := veil) + 4 (d > 0) © R2: Each message m is piggybacked with the vector clock vt of the sender process at sending time. On the receipt of such a message (m,vt), process p, executes the following sequence of actions: * Update its global logical time as follows: Tsk Execute RI. » Deliver the message m. Singh shemales Deena Technique ‘tomipusiyec <2 te a Us t=2 Ly o° 1 thee Lytle 4 Lay O=3 Vector Time Process. ues the following two rs Rare 2 to uplte its clock * A, Sefer executing a eet. proces pupae it lea lope ine a4 falows wll=wines — (@>0) * F Each mesate ms igatacad wih the vector dock vf the sender ote at sening tine. the recep ofc a ase (eth aes ‘recut: the follwing sequence of actors Undies allel tn os lowe BSKS0 stl mae) > Eves A, + Dane the menage m, poke thn ks — pouty 7 folly love ult coe baes < ca Ge 3 a J ip ak af “OS ej oe - co-f diishvibpakel Snaps > panto 2 sibs Q\ State Sint rucovdwd J (on sired pucm not covded System model © At ay instant, the state of proces p, dented by LS, is 2 result ofthe sequence of al th events executed by p til that instant. @ For an event e and a proces$ state LS), e€LS; iff ¢ belongs to the sequence of events that have taken proces p, to state LS} 1 Foran event e and a proces state LS;, ef 5; iff e doesnot belong to the Sequence of events that have taken process py to state LS, © Fora channel Cj, the following set of messages can be defined based on the local states ofthe processes p and p, ‘Transit: transit(LS;, LS}) = {my |send(mj) € LS, A\rec(mg) ¢ LS; } Consistent global state 1 The global state of» dtributed 9 the proceses andthe channels, © Notations global tate GS i dtned as, 65 = {ULS. U5) © A tlobal state GS is consent lob! sta Atala alba tate i satisfies the flowing two stem isa cllection ofthe lca states of CE sd) mye5Cy 0 elm 2: send £LS; => mygSCy 1 ree(my) 65, JeLS,. (@ is ELOR on in Terms of C

You might also like