Interesting Paper on the Immirzi Parameter, and more…

In Loop Quantum Gravity, the Immirzi parameter is somewhat troubling…largely because it’s such an odd value.

It was once calculated to be some ugly value like:

Or something like that. Bizarre!

Well, a paper came out that argued that:

Microscopic state counting for a black hole in Loop Quantum Gravity yields a result proportional to horizon area, and inversely proportional to Newton’s constant and the Immirzi parameter. It is argued here that before this result can be compared to the Bekenstein-Hawking entropy of a macroscopic black hole, the scale dependence of both Newton’s constant and the area must be accounted for. The two entropies could then agree for any value of the Immirzi parameter, if a certain renormalization property holds.

(Emphasis added). Fascinating!

The paper is called “Renormalization and black hole entropy in Loop Quantum Gravity” by Ted Jacobson.

There was a second paper that crossed my eye because of something that stuck out from Carlip’s Class. This student with a British accent asked why not place the universe within a box? We do it for the Hydrogen atom, among other things, so why not do it for quantum gravity?

Well, the obvious answer is the philosophical problems with this in the context of classical general relativity. However, a paper has come out about this very subject! It’s very exciting purely from the nostalgic feeling the abstract conjures:

The curvature perturbation in a box by David H. Lyth

The stochastic properties of cosmological perturbations are best defined through the Fourier expansion in a finite box. I discuss the reasons for that with reference the curvature perturbation, and explore some issues arising from it.

Next on the reading List is a lengthy piece dealing with particle propagators in arbitrary backgrounds.

This piece fascinates me partially because it comforts my inner general relativist in dealing with background independency (or more spacifically, a sort of pseudo-background independency) for quantum theory.

Particle propagation in non-trivial backgrounds: a quantum field theory approach by Daniel Arteaga

The basic aim of the thesis is the study of the propagation of particles and quasiparticles in non-trivial backgrounds from the quantum field theory point of view. By “non-trivial background” we mean either a non-vacuum state in Minkowski spacetime or an arbitrary state in a curved spacetime. Starting with the case of a flat spacetime, the basic properties of the particle and quasiparticle propagation are analyzed using two different methods other than the conventional mean-field-based techniques: on the one hand, the quantum state corresponding to the quasiparticle excitation is explicitly constructed; on the other hand, the spectral representation of the two-point propagators is analyzed. Both methods lead to the same results: the energy and decay rate of the quasiparticles are determined by the real and imaginary parts of the retarded self-energy respectively. These general results are applied to two particular quantum systems: first, a scalar particle immersed in a thermal graviton bath; second, a simplified atomic model, seizing the opportunity to connect with other statistical and first-quantized approaches. In the second part of the thesis the results are extended to curved spacetime. Working with a quasilocal quasiparticle concept the flat-spacetime results are recovered. In cosmology, within the adiabatic approximation, it is possible to go beyond the flat spacetime results and find additional effects due to the universe expansion. The cosmologically-induced effects are analyzed, obtaining that there might be an additional contribution to the particle decay due to the universe expansion. In the de Sitter case, this additional contribution coincides with the decay rate in a thermal bath in a flat spacetime at the corresponding de Sitter temperature.

Fascinating papers, all of them well worth reading.

Lisp for the Low Level Man: An Introduction to Liskell

So, you want to program Lisp on a slow/old computer? Use Liskell, it’s Haskell and Lisp combined into a new language.

The example given on the home page of Liskell in action is actually pretty interesting:

(define (fact n)

(if (== n 0)
1
(* n (fact (- n 1))))))))

Compare this to the old school Haskell:

fact n =

if n == 0

then 1

else n * (fact (n - 1)))

It has the beauty of Lisp and the speed as well as efficiency of Haskell. It’s a beautiful language for those that like functional languages (all eyes turn to John Armstrong :P).

Please Criticize This…

OK, I am working on the explanation of Unix-like file systems intended for programmers that don’t know anything about the Unix-like file system structure. This is a rough draft, and I know the appendix is sketchy, it needs to be - well - written. I think I did a half decent job, but it occurs to me as I write the technical documentation that there is no explanation of the Unix-like file system concept. So please please please help me by demanding clarification at points!

Cheers!
AngryPhysicist

Revision 1 Added more information about how the directory really is-a file.

An Introduction to Unix-like File Systems

What the hell’s a file system?

A file system is used nowadays to manage the hard disk, floppy disk, and well any block device. It uses files to centralize data, and directories to organize files and other directories.

The hard disk has a geometry (see the appendix) so the file system has to “respect” this. There are various approaches to making a file system, we shall inspect the Unix approach specifically since this is a manual for a Unix-like operating system.

The Unix Approach: Inodes

It should be emphasized EVERYTHING “IS-A” FILE! Unix is (sorta) object oriented like that, that’s one of the appeals to it. Any operation that can be done on a file (read, write, open, close, etc.) can be performed on directories, devices, etc.

The file system is key to the Unix philosophy…everything “is-a” file after all! The file system is like the heart of Unix…so it is worthy to spend time to discuss the idea behind the Unix-like file systems. We shall use pseudo-code that is similar to C# or D.

The basic idea is this: everything is a file. A file is represented by a data structure called an inode (index node). The inode (also written as “i-node”, “index-node”, etc.) has fields that store information about the file or the addresses of the blocks. If you are unfamiliar with disk geometry, there is an appendix on it. A toy inode could be:

struct inode{
uint mode;
uint size;
uint *blocks[MAX_ADDRESSES];
}

There are only three simple fields that really define an inode. One tells us what sort of file we are dealing with. In unix, we have ordinary files and directories, as well as file representation of the various devices, pipes, and sockets. (The last two, pipes and sockets, are a sort of data structure used in interprocess communication.)

The next thing that gives us information about the file is the size of the file, which is given to us by the field uint size.

Last, and by no stretch of the imagination least, uint *blocks[MAX_ADDRESSES]. This field is the pointers to the various blocks that the inode stores the data in. Typically, the last several blocks are so-called indirect blocks. They hold addresses to blocks which are then used to hold addresses to more blocks. Singly indirect blocks use 1 indirect block (that is, the address it refers to is a block full of addresses; the exact number of addresses is equal to (the size of the block in bytes) / (the size of the variable one uses for addressing in bytes)). TO figure out how much data storage this gives us, we have the number of addresses in the indirect block given, we shall call it N. Now, each address refers to a block of data, so there is: N * (size of a block in bytes) bytes per singly indirect block.

A doubly indirect block uses a block that is full of addresses to another indirect block. That is to say, the address referred to us by the inode is a block full of addresses. These addresses refer us to more blocks which are chalk full of addresses. These addresses then refer us to the data. To figure out how many addresses it refers to, we simply figure: (1 block of addresses) * (X bytes per block) * (1 address per Y bytes) = number of addresses referring us in the first indirect block. We previously called this N. Now, each address refers us to what is pragmatically a singly indirect block. So we have: N * ( N * (size of a block in bytes) ) = bytes supported in a doubly indirect block.

There is also the triply indirect block. If you haven’t spotted the pattern so far, here’s the trick: for an Z indirect block, it supports N**Z * (size of a block in bytes) bytes. So for our triply indirect block, it is: N * (N * (N * (size of a block in bytes) ) ) bytes.

To figure out how many bytes an inode supports total, simply sum up the direct blocks with the indirect blocks. It’s a simple sum.

The Organization of the Disk

The basic structure of the inode approach more or less organizes the hard disk (or any block device really) into several components. We shall briefly cover this organization here.

The first important block is the zeroeth block: the boot block. It is the block that is loaded into memory after bios. It must be preserved at all costs.

Then we have two bit map blocks. The first is the inode bitmap. The idea is that the disk has a finite space (despite our wishes!). There are only so many inodes that are needed. So we allocate a section of space for these inodes. We need to keep track of whether these inodes are being used or are free. We use a bitmap to do this. A bitmap is really just a collection of bits (ones and zeroes). The first bit refers to the first inode, the second bit refers to the second inode, etc. We indicate whether an inode is used by a 1 and it is free by representing it with a 0 in the bitmap.

The second bitmap that follows this is the block bitmap. Just as the inode kept track of the free and used inodes, the block bitmap tracks the blocks and whether they are free or taken.

Now we have the space allocated to the inodes. This is the inode table. It is the contiguous space of inodes that keeps track of, and organizes, the disk.

The rest of the disk is used for the data directly (or as indirect blocks full of addresses). They do not hold inodes, etc.

Directories in Unix Like File Systems

Well, we see what a file is (it’s just a collection of blocks basically!). What about a directory? It seems a little more complicated. The directory is a file. However, unlike an ordinary file that stores data, a directory has special entries within it. The directory entry is a glorified pointer to a file. It stores the file name, the inode number of the file, and sometimes other fields that are useful.

We treat the directory as a file. A file is an inode. An inode stores addresses to blocks of memory for data. A directory, however, has no data other than these glorified links called directory entries. Well, since we cannot really change the structure of the inode, we need to simply change the data that are stored on the blocks. We use things called directory entries, a data structure often shortened to dir_entry. Let us look at a simplistic one:

struct dir_entry {
char name[NAME_LENGTH];
int inodeNumber;
}

This is the simplest directory entry. It has two fields that are really important: the name of the entry within the directory, and the inode number.

The inode number refers to the inode being the Nth inode in the inode table. This is useful if we wish to know where the inode is, and if we would just so happen like to actually access the data.

Supposing that the maximum length of the name is 256 (i.e. #define NAME_LENGTH 256), then the size of a dir_entry is: (256 char) * (1 byte per char) + (1 int) * (4 bytes per int) = 256+4 = 260 bytes. That is roughly half of a sector (512/2 = 206, I know I know!). And an inode can refer to (supposing that there are 16 addresses all together) 16 blocks directly (I’m lazy, so I won’t try to calculate out “What if we use 1 singly indirect block? What if we use 1 doubly indirect block? What if…?”). Thus, in a handwavy lazy fashion, there are at most 32 entries in a directory this way…yes yes this also assumes that 1 block is 1 sector big (and 1 sector is 512 bytes). <!–I lied, I will calculate out how many dir_entry there are for: 1 singly indirect block, 1 singly and 1 doubly indirect block, and 1 singly 1 doubly and 1 triply indirect blocks. Well, for a singly indirect block using 4 bytes for addressing, we have (512 bytes per block) * (1 address per 4 bytes) = (512/4) addresses = 128 addresses. Thus if each refers to a block, we have (128 blocks) * (512 bytes per block) = 65536 bytes. Thus for an inode with 15 direct addresses and 1 singly indirect block, we have (15 addresses + 128 addresses) * (512 bytes) = 73,216 bytes. There are 281.6 directory entries, round it down and we have 281 directory entries.

Suppose now we have 14 direct blocks, 1 singly indirect block, and 1 doubly indirect block. The doubly indirect block has 128 addresses that refers to 128 addresses, or (128 addresses) * (128 addresses) = 16,384 addresses. Now, to add together all the addresses: (14 direct addresses) + (128 singly indirect addresses) + (16384 doubly indirect addresses) = 16,526 addresses. Now this supports: (16526 blocks) * (512 bytes per block) = 8,461,312 bytes. This in turn supports (8461312 bytes) * (1 dir_entry per 260 bytes) = 32543.507692308 dir_entries. We round down to 32,543 directory entries.

For 13 direct blocks, 1 singly indirect block, 1 doubly indirect block, and 1 triply indirect block, let us calculate this one out. We know how many addresses there are for direct, singly indirect, and doubly indirect blocks, but we are ignorant of the number of addresses supported by the triply indirect block. Let us figure it out now. There is a block that has addresses to other blocks full of addresses to other blocks. That is (128 addresses) * (128 addresses) * (128 addresses) = 2,097,152 addresses. Now this inode supports: (13 direct addresses) + (128 singly indirect addresses) + (16384 doubly indirect addresses) + (2097152 triply indirect addresses) = 2,113,677 addresses. This in turn supports a total of: (2113677 addresses) * (1 block per address) * (512 bytes per block) = 1,082,202,624 bytes. Now, each directory entry is 260 bytes, so that means that this inode approach supports (1082202624 bytes) * (1 dir_entry per 260 bytes) = 4162317.784615385 directory entries. We round this down to become 4,162,317 directory entries.
–>

Appendix: Disk Geometry

Disk geometry is an interesting concept in and of itself. The hard disk is divided into atoms of 512 byte sectors. Typically file systems use a “block” concept, where there are 1, 2, 4, 8, or sometimes 16 sectors in a block. Note how it’s always a multiple of 2 (2**0, 2**1, 2**2, etc.).

A Brief Anecdote and A Deformation Quantization of Gravity

The Brief Anecdote

OK, so I was talking with the lead developer of Brainix and we hit a snag. Largely because it’s a microkernel, it’s indescribably difficult to program correctly. So, we said to each other “What should we do?”

Our conclusion was, well, nonexistent. That’s right, we didn’t come to a conclusion (we’re too cool to solve problems ). What I suspect will happen is we’ll end up making Brainix a hybrid kernel with the drivers running in the user-space so the Operating System won’t crash so much.

We’ll try making the operating system Unix-like…but in doing so we’ll try to resolve some problems like: the devices are supposed to be represented as files, but there is an ambiguity over the “block device” vs. “character device” dichotomy (e.g. the Network device is neither apparently). Perhaps we’ll make a more object oriented approach to solve this problem.

I suggested that we should start using the D programming language and using javadoc in-code documentation so that: 1) it’s easier to program, 2) it’s easier for “newbies” to learn the operating system concepts. We’ll see how things turn out I guess. A “problem” that arises is that either we can’t use classes (we can just as easily use structs) or we will have to hack together our own special compiler from the GNU D Compiler front-end (we may have to “slightly” change the Object class). This problem depends on whether we want to focus on embedded systems (or really old computer systems) or if we want to make operating systems for “recent” computers (i.e. with at least 512 megs of RAM, 1 GHz processor, etc. etc. etc.).

But I wish to present a conjecture:

AngryPhysicist’s Conjecture: It is impossible to have an efficient Microkernel that is also POSIX-compliant. It’s one or the other, but not both.

Remark: It is possible to have an efficient microkernel! It just can’t easily be Unix-like.
I’m actually a little sad that we are departing the microkernel approach, but we’re doing something that is easier to program. Perhaps first we should write a debugger for the operating system (supposing we want to make life easier for ourselves — real programmers don’t use debuggers though, they program in binary)? That would require us to figure out how to make a debugger though…

Now, on to the paper:

Generalized Lagrange Transforms: Finsler Geometry Methods and Deformation Quantization of Gravity by Sergiu I. Vacaru

ABSTRACT: We propose a natural Fedosov type quantization of generalized Lagrange models and gravity theories with metrics lifted on tangent bundle, or extended to higher dimension, following some stated geometric/ physical conditions (for instance, nonholonomic and/or conformal transforms to some physically important metrics or mapping into a gauge model). Such generalized Lagrange transforms define canonical nonlinear connection, metric and linear connection structures and model almost Kahler geometries with induced canonical sympletic structure and compatible affine connection. The constructions are possible due to a synthesis of the nonlinear connection formalism developed in Finsler and Lagrange geometries and deformation quantization methods.

I thought this was an interesting paper, Carlip remarked he never saw an attempt at Deformation Quantization of Gravity. Well, there you have it.

More Programming Notes of Pseudo-Interest…

I have stumbled upon a few gems worth noting. First off, there is the Metalinguistic Abstraction. It’s a “good read” as far as blogs go, with respect to programming.

There is also an Object Oriented version of Unix out: UnixLite. It’s (unfortunately) written in C++, but it’s interesting (to me at least) to observe an object oriented unix-like operating system’s source code. It is a “toy” operating system, but don’t let that fool you: you could possibly hack it into a full blown Linux clone.

Interestingly, Minix3 has just recently announced they ported SQLite. It appears to be trying to become a server operating system, but it still has this air of being a toy to it (a certain je ne sais quoi as the French would say, if I remember how to spell in French).

I am considering going back to Davis a wee bit early (i.e. next Saturday perhaps?), so I will be busy meeting with old acquaintances and so on and so forth.