# Tag Info

109

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 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 ...

14

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 ...

7

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/...

6

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 ...

6

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$ ...

5

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 ...

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

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 ...

4

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" ...

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 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

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 ...

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

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. ...

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

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

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 point ...

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

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

Vector clocks overflow for the same reason that regular integers do. Vector clocks generally maintain a fixed number of bits per process to capture the event count for each respective process. There is naturally a maximum value that each of these bit strings can represent. Any one of these values can potentially be increased beyond their capacity, and thus ...

1

Lamport clocks are not designed to allow you to infer all causality. No one ever claimed that knowing the Lamport timestamp is enough to read out the causality of all messages. Rather, Lamport clocks provide a partial ordering that is consistent with causality: if event $a$ happens before event $b$ (causally), then $a$'s timestamp will be smaller than ...

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 ...

1

From your question, it seems you already have the answer, but you are not acknowledging it as "the answer". It is exactly as you describe it: The logic circuit takes time $t$ to stabilize. This $t$ is given by the low-level description of the circuit (adding all the $t_{\text{high-low}}$ and $t_{\text{low-high}}$ in the longest path (the critical path). ...

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