# Tag Info

98

Computers have a "real-time clock" -- a special hardware device (e.g., containing a quartz crystal) on the motherboard that maintains the time. It is always powered, even when you shut your computer off. Also, the motherboard has a small battery that is used to power the clock device even when you disconnect your computer from power. The battery doesn't ...

21

The problem is known as Firing squad synchronization problem. The problem itself, is strictly related to finite state automata. Here, each soldier is a finite automaton; you know that the next state of each soldier depends on its current state and the current states of its two neighbors (except for the first and last soldier). The first soldier in this ...

19

The system clock is needed to synchronize all components on the motherboard, which means they all do their work only if the clock is high; never when it's low. And because the clock speed is set above the longest time any signal needs to propagate through any circuit on the board, this system is preventing signals from arriving before other signals are ready ...

13

If you remove the battery on the motherboard then the computer wouldn't have any way to tell the time. This is also the case with mobile phones. If you let a phone discharge and then not recharge it for more than a few weeks it will also "forget the time" because the small auxiliary battery is discharged completely and nothing is powering on the real-time ...

10

Inability to measure asymmetry No, you can't measure the asymmetry. Consider these two communication diagrams, the first with a negative clock offset and equal delays and the second with no clock offset and entirely asymmetric delays (but the same round trip time). The important thing to notice is that, from the perspective of both the PC and the server, ...

5

No, there's no need for a vector clock in a centralized system. A vector clock uses a $N$-vector of timestamps, where $N$ is the number of computers in the distributed system and the $i$th component of the vector block is a timestamp chosen by the $i$th computer. In a centralized system you'd use a $N$-vector with $N=1$, so it just reduces to a single ...

5

You could try to measure time from RAM transfer rates. You'd need to know the precise clock ratio between the RAM and the CPU. There would have to be a precise clock ratio; I don't think this is the case on typical PC architectures as the RAM and the CPU have their own clock and I'm not sure the RAM peak transfer rate is a constant. You'd need to block all ...

4

As it has been pointed out by both @kramthegram and @Wandering Logic, event $a$ "happened before" event $b$ does not imply that $a$ has physically caused $b$ (to happen). Such causality used in Lamport's paper is often called potential causality. It captures all possibilities, often inducing a huge causality graph, and in practice it wrecks the scalability/...

3

The Network Time Protocol (NTP) uses a rather simple basis, it assumes that the roundtrip time is divided equally between up and down delays after server processing is subtracted. NTP keeps 4 timestamps per poll: client send $t_0$, server receive $t_1$, server send $t_2$ and client receive $t_3$. Server timestamps being in the server's clock and client ...

3

Look at the definition of $<_H$. We say that $e_1<_H e_2$ (event 1 happened before event 2) if: $e_1,e_2$ took place in the same process, and $e_1$ happened first (events within the same process are ordered). $e_1,e_2$ are the sending and receiving of some message $m$, correspondingly. Finally, we take the transitive closure of the above, and this ...

3

Note that causality is an undefined term in the paper. Lamport is using it in an informal explanation. He's assuming that could causally affect is an intuitive concept that will mean the same thing to his readers as it does to him. I think for Lamport $a$ could causally affect $b$ actually means something more like information could flow from $a$ to $b$ ...

3

The answer provided by @Benjoyo is not accurate. The CPU clock can be lower than the system clock, at least in microcontrollers. As seen in this link, the PIC microcontrollers have the CPU clock, with a rate of $f_{cy}$ (also called instruction cycle frequency), and the system clock, with a rate of $f_{osc}$ (oscillator frequency). Physically, what ...

3

All it's saying is that the messages between two processes need to be received in the order they are sent. If I'm going to send only differences between the previous message, we both better agree on what "the previous message" is. For example, if I send "increment the first and second component" and then "increment the first and third component" but you ...

3

The "partial ordering" in the papar means partial order as in standard mathemtics theory. To be more rigorous, the "partial ordering" in that paper, also called "irreflexive parital ordering" in that paper, means strict partial order. (Yes, "strict" means "irreflexive".) (Yes, "order" can be used interchangeably with "ordering" sometimes. I prefer "order" ...

2

Consider a network of time servers known to be synchronous, $\theta = \{A, B, C\}$, and a client machine $P$. Let $T_{XY}$ be the one way time of flight from machine $X$ to machine $Y$, with the possibility that $T_{XY}\neq T_{YX}$. Let $\Delta_{XY} = |T_{XY} - T_{YX}|$ be the measure of the asymmetry between machine $X$ and $Y$. Now, consider that the ...

2

Here's my take: ...and here's a 3D version without the nice colors. Vertical black lines are processes; magenta lines are messages (wavy lines); spheres are events, and time is on the vertical (blue) axis. The planes are 'tick lines.' In Dr. Lamport's original diagrams, messages are only passed between "adjacent" processes. Presumably in a real ...

2

Your missing the selection of the word possible. It doesn't mean that the relationship is actually causal, just that it is possible for a to have a causal effect on b. His statements are not false, you're just reading more into them than he is actually stating. Just because it's possible doesn't mean it's true. The stronger statement is the inverse, if a ...

2

Technically, clock skew does this already. Specifically the technique known as "useful skew". When a data signal is going to travel from one storage element to another (both updating based on the clock), the clock that the source and destination elements receive are not quite the same. In "useful skew", the clock at the destination is delayed such that the ...

2

An N-bit wide data bus can transfer N bits in one clock cycle, after a latency of d clock cycles (or t seconds). I think the above sentence has everything you'd need to solve this problem.

2

You have a good understanding of clocking mechanism and how flip-flops (registers really, can be implemented using any clocked memory, not just flip-flops) are used to get a "final" reading after all propagation of signals have stabilized. But your question: The clock period is set such that the other circuitry (NAND gate in my case) has the time to ...

2

When you start Windows, it gains direct access to the memory of the Real Time Clock (RTC) and uses its date and time values to set the computer date and time. Timer interrupts maintain the computer time when Windows is running. A Time Daemon in Windows runs approximately once each hour after the Windows starts. The Time Daemon compares the time in Windows ...

2

I feel there are multiple questions in your post. I will attempt to answer the first - "...The clock period is set such that the other circuitry (NAND gate in my case) has the time to stabilize during the cycle. This is the contract. But how is it achieved? Shown below is a transistor level circuit of the D flip-flop shown in the picture in your post. If ...

2

Considering that any local action (e.g. increasing a counter) done by a process is an event, the Wikipedia sentence "A process increments its counter before each event in that process." does not make any sense to me. Let me try to answer your questions: Should we increment the counter before sending a message, as the sending of a message is itself ...

2

Your question is a bit vague, depending on what is communicating, so I will try to give a general answer. There are essentially two big ways of communicating: Sending data together with a clock signal (source synchronous): this is used in I2C, RAM, SPI Sending just data and let the other side recover the clock from it (clock recovery): this is used in USB, ...

2

Modern processors tend to have more clocks than processors in the past, because that means when a part of the processor isn't used, it may be possible to switch off that part completely, including the clock, to save energy. Clocks are often not synchronised, because synchronising and keeping them synchronised is expensive and complicated, and if you can ...

2

As Wikipedia explains: The algorithm of Lamport timestamps is a simple algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and conceptually provide a starting ...

2

It depends. If all atomic clocks would be turned off simultaneously, right now, that would be trouble. Because everyone relies on atomic clocks. And everything is organized in such a way that it doesn't matter much if a handful or two dozen stop working, but if they all stop working, then all the time servers in the world have no source for their time ...

2

No, "it doesn't make sense". You are correct in the sense that that choice is not a logical consequence of any requirements and known truths. It could be considered as arbitrarily selected. Well, we do not need to make any sense when we are forced to decide which one of two global timestamps, $(T_i,i)$ and $(T_j,j)$ where $T_i=T_j$, is earlier than the ...

1

You are right that the clock speed is determined by the slowest stage. But on most architectures it is not true that fetching(or any kind of memory access in fact) takes one cycle. This is an illusion provided by the CPU to makes things manageable. In practice if your CPU tries to fetch and the operation cannot be completed in one cycle then it will stall(on ...

1

The description is hopelessly outdated. For instance, "the Control Bus" ? I wouldn't even know what bus that would be. It's apparently not the "Internal Clock", so presumably "the Control Bus" is the external bus. Problem: modern CPU's don't have a single external bus. And it's not like each external bus has its own clock: modern high-speed parallel buses ...

Only top voted, non community-wiki answers of a minimum length are eligible