text:
# A Historic Name-Trail Service

## 1 Introduction

The online world is inhabited by nomads. People change their online names as they switch Internet service providers (ISPs), either because they change jobs and they use the ISP of their employer, or because they switch to a better, cheaper, or more convenient service for their personal ISP. As a result, people accumulate a legacy of online identifiers that are, in most cases, dangling pointers into obscurity, making it hard to reach people.

Unfortunately, sometimes an obsolete online identifier does point to something, and this can be much more dangerous than a dangling identifier. If the obsolete identifier belongs to my previous personal ISP, then some unrelated, unfortunate subscriber of that same ISP is bothered by my legacy of spam. If the obsolete identifier belongs to my previous place of employment, it might allow my sensitive communications to reach a potentially disgruntled former colleague or boss.

The problem stems from the simple fact that online identifiers *do not* belong the people that they name; they belong to the organization that manages the associated name space. An employee of Sample University does not own her Sample U. email address; that address belongs to the university itself, which loans it out to its employee for the duration of her employment there. Similarly, my yahoo.com address only names me as long as Yahoo! allows me to use it and maintains its service. This is essentially a mobility problem: a mobile person moves slowly from identifier to identifier in a potentially-changing landscape of online names over which he has little control or authority. We call this the *personal-identity mobility* problem.

The promise of unique personal identifiers as a panacea for all kinds of identity mobility has been made many times with dubious success. In some cases, the proposed identification scheme requires a retrofit of the entire communications infrastructure of the Internet to work . In other cases, the “unique personal identifier” is just another identifier assigned from a proprietary name space .

In this paper we propose the HIstoric Name-Trail Service (HINTS). In our naming scheme, current online identifiers, email addresses and instant messaging account names remain the primary identifiers that people use in everyday communications. However, HINTS enables a person voluntarily to build a trail that connects all the identifiers that person uses over time into a single *name history*. A correspondent can then safely name the person by using a potentially obsolete identifier qualified with a time at which that identifier was successfully used in the past. With this information the appropriate name history for a unique person can be found and followed to its latest entries, which provide a more recent way to reach the sought person.

HINTS offers mobile people control over forward pointers from their old to their current online identifiers. Even if an old name belongs in a name space maintained by a now-defunct organization, that name can still be resolved within HINTS to a current identifier for its past owner. This independence of a historical name from the provider of its associated name space promotes a robust, persistent way to refer to people, even when the practical names we use in everyday life are neither robust, unique nor persistent.

The goal of this paper is to introduce the concept of historic naming as a means to address identity mobility, and to describe a simple version of HINTS that can be deployed using today’s technology. However, our current efforts focus on designing and implementing a decentralized, more fault tolerant and secure version of HINTS, which we also briefly describe in this paper.

We proceed by providing an abstract model of the current personal online identification landscape, in Section 2. In Section 3 we introduce the basic concepts of HINTS, including the structure of the name space, the functionality of the service, and the implementation considerations involved. We evaluate the benefits offered by HINTS in Section 4, by delineating what the service can and cannot do, given how personal online identification works today. We then elaborate on the next step for HINTS, namely security and fault-tolerance, we discuss what additional requirements these properties place on online service providers, and we sketch an enhanced design in Section 5, before we conclude.

## 2 A Model For Personal Online Identification

This section outlines the naming model on which the historic name-trail service is based. This model abstracts the way in which names are *currently* associated with people online. We also describe the components that currently provide naming services and explain the division of control and naming responsibilities between these services and their clients.

People need names online for a variety of purposes, such as authentication, communication, and authorization. In most cases, these names are simple, such as plain email addresses . In other cases, online names may be two-tiered, starting with a primary application-unspecific name, which is used to look up application-specific addresses in a directory via a directory access protocol such as LDAP . For simplicity, we take the former approach in this paper. Specifically, we use email addresses as the *primary* names of people online in our examples. However, the techniques we describe in later sections apply directly and without change to names in other applications, such as instant messaging, or to two-tiered naming environments.

The names people use are drawn from a multitude of independent *name spaces*. A name space is a set of all possible names that are or can be assigned by a single administrative entity, called a *name-space provider*. For example, Yahoo! Inc. is the name-space provider operating the yahoo.com name space: this is the set of all possible account names for Yahoo! Inc.’s services, such as web mail, instant messaging, calendaring, etc. In most cases, the name-space provider responsible for a name is easy to determine from the name itself. For example, name@yahoo.com is a name in Yahoo!’s name space. The computers responsible for maintaining a name space are the *name servers* of the provider. To find an authoritative name server for a name space, we can access the Domain Name Service , either through a distinct DNS resource record type, or through a straightforward name mapping (e.g., names.sample.edu for the sample.edu name space).

A person online may be addressable via multiple names drawn from different name spaces. For example, one may be addressed using names assigned by a school, by a personal Internet service provider, by web services such as Yahoo! and Hotmail, and by professional associations such as the ACM. These names can be used for distinct or overlapping purposes: professional, personal, commercial.

The association of a name with a person follows the regulations defined by the corresponding name-space provider. These regulations may dictate whether a name association is temporary or permanent, whether a name may be reassigned after its previous association is discontinued and, if so, the minimum amount of time between successive assignments of a single name. For example, Sample University’s Computer Science Department assigns names to its graduates for life, whereas ISPs assign names to clients for the duration of the pertinent service agreement. It is important to note, however, that the name-space provider is the ultimate controller of the name space, regardless of the “promises” it makes to those using its names. It is not uncommon, for example, that a claimed permanent name assignment has had to change for legal, social or political reasons. As an example experienced by one of the authors at Sample University, the arrival of a new faculty member who desired an email address already assigned to a graduate resulted in a reassignment of that email address to the faculty member, in spite of the institution’s guarantee of lifelong identifier assignments to its graduates.

In most cases today, a person exercises implicitly his “stewardship” of a name assigned to him, by being able to access the application for which the name is assigned. For example, in today’s Internet, if I can read and send email as name@yahoo.com, then I am assumed to be the person to whom that name has been assigned. Though not bulletproof, this simplistic form of authentication is widely used for signing up in mailing lists, for signing up for web services or even for conducting business online. The name-space provider can revoke an association between a person and his name by stopping that person from accessing the named service; for example, the provider can cancel the associated web email account, or change the requisite password. Aside from intra-enterprise settings, not many name-space providers today offer rigorous security in how they assign names, and how their clients assert ownership on their names. Section 5 describes a more secure naming model, very similar to an attribute certification model, that allows us to address the problem more comprehensively.

In the remainder of this paper, we limit *mobile person* to be someone who wishes to remain reachable despite identifier changes. A *correspondent person* is someone who wishes to reach a mobile person. In the examples we use, Jane Mobile is a mobile person, and Dan Friend is a correspondent of Jane’s.

## 3 A Historic Name-Trail Service

The primary goal of this work is to provide mobile people with a forwarding service that is available to help them remain reachable despite their identity mobility. We accomplish this by allowing a mobile person to determine to what his historic names—names qualified with a time when they validly named that person—point. We approach the problem first by taking the simplest path possible: a centralized, trusted service that operates similarly to most web services currently deployed and works with no cooperation from current infrastructure. We explore more sophisticated, secure and fault-tolerant possibilities in Section 5.

Reachability despite identity mobility requires the transfer of some of the naming “power” over a name from the associated name-space provider to the person to whom the provider assigns the name, within closely guarded *temporal* confines. Specifically, even though a provider can do anything it wishes to a name, its actions cannot be applied retroactively: if Yahoo! assigns jmobile@yahoo.com to Jane Mobile from August 1999 to May 2000, it cannot later “change history” so as to strip Jane of her control over jmobile@yahoo.com for the indicated time period; Jane’s authority over jmobile@yahoo.com from August 1999 to May 2000 is *persistent*.

By imposing this persistence of authority, HINTS splits responsibilities between mobile people and name-space providers. Name-space providers are responsible for creating and destroying associations between names and people (in fact, between names and people who can access the service state for that name). People are responsible for acting on behalf of, and being reachable as a particular name during the period that they have been assigned that name.

This separation of control enables the definition of a “virtual” global persistent name space, with most of the ambitious properties suggested in IdentiScape , such as persistence, controllability and human-centricity, but without requiring the creation and maintenance of a centralized name service for a global, flat name space implied by that system.

### 3.1 The Name Space

We define the HINTS name space by extending names with a continuous time designation. For example, to refer to the person named by the identifier jmobile@yahoo.com in March of 2000 we construct the identifier Historic\[jmobile@yahoo.com, 03/2000\]. More generally, the HINTS name space contains identifiers of the form Historic\[name@namespace, time\]. A HINTS name corresponds to a time-specific primary name, and is meaningful both while the associated primary name is valid (i.e., assigned), and after that primary name has been reassigned or obsoleted by its name-space provider.

The time component of the identifier defines a version of the chosen name space at a particular, coarse-grained time. The time component may designate an entire year, a year and a month, or a full date. Since identifiers change at “human” time scales, refining the time component to anything shorter than a day may be unnecessary. We assume that clocks of clients or providers are at least coarsely synchronized (e.g., they all agree on what day it is), but we address a more secure timing environment in Section 5.

Many different HINTS names may denote the same person. Since Jane Mobile held the name jmobile@yahoo.com from August 1999 to May 2000, any HINTS name that corresponds to the same primary name and with a time designation within the validity period points to her. For example, Historic\[jmobile@yahoo.com, 9/8/1999\] and Historic\[jmobile@yahoo.com, 1/2000\] are valid HINTS names for Jane Mobile.

Some HINTS names denote multiple people. Consider the scenario in which Yahoo! Inc. reassigned the name jmobile@yahoo.com to a different person, James Mobilewski, in September of 2000. Then the HINTS name Historic\[jmobile@yahoo.com, 2000\] is *multivalent*, in the sense that it points to two different people, Jane Mobile and James Mobilewski. A multivalent HINTS name is essentially a list name, since it names *all* of the possible people to whom the included primary name points during the time designation of the historic name. Therefore, historic names with narrow time designations are preferable to those with very broad time designations, when possible.

### 3.2 A Personal Naming History

HINTS relies on a *name history* to resolve historic names. A name history links together HINTS names that refer to the same person. The objective behind maintaining a name history is to be able to reach a currently valid name-to-person association, starting with a now obsolete one. In the Jane Mobile example, the goal is to be able to obtain name janem@hotmail.com, which is currently valid and is held by Jane, starting with Historic\[jmobile@yahoo.com, 03/2002\], even though jmobile@yahoo.com is no longer held by Jane. Figure 1 shows an example name history for Jane Mobile.

A name history is maintained as a sequence of historic records pertaining to a single name within a single name space, such as jmobile@yahoo.com. An online entity called a *name historian* maintains these records. The history of a name is modified due to either assignment changes or linking changes.

Changes in assignment affect to whom a particular name points. These are effected in provider-specific ways, such as changes in the password needed to receive service under a particular name, etc. Assignment changes can be detected by the name historian either directly, through an explicit notification from the name-space provider, or indirectly, through failure of a mobile person to respond to a challenge issued to his formerly assigned name. Since in this design we assume no cooperation from name-space providers, only indirect detection of assignment changes is possible. However, the historian can initiate indirect detections of assignment changes reactively, at the request of a mobile person.

Changes in linking affect how a single person assumes different online names over time. The historian emulates the concept of a “person” online by maintaining a trail of “personal manifestations”, such as knowledge of the same secret password or of the secret portion of the same cryptographic key pair. Linking represents the intention of such an online person to be or not to be named by particular online names. The mobile person requests explicitly to be linked to or unlinked from a name by contacting the name historian with the appropriate request.

Assignments and links must both support the association of an online name with the historian’s online representation of a mobile person. Specifically, to accept such an association, the historian must establish two facts: first that the mobile person wishes to assume that name, as communicated directly to the historian via a linking request; *and*, second, that the online person has access to that name, which the historian can detect indirectly by sending a challenge to that name via email (or any other applicable protocol) and expecting an appropriate response.

The historian periodically reestablishes both assignment and linking for an association. Since the name-space providers are not aware of the service, the historian has no recourse but to poll the name space periodically or in response to user requests, so as to establish whether the assumed mobile person still has control of his former name. Similarly, to avoid cases where a mobile person who becomes unavailable is assumed to be asserting control over a name by default for extended time periods, the historian expects periodically that person to reassert his links actively.

Figure 2 illustrates an *association record*, the basic building block of a historic name database. The specific record identifies Jane Mobile using her first and last names, although in practice a person is identified by the historian using an internal, private, implementation-specific name space for mobile person identification that no correspondent ever sees. An association record is active if it covers the present time (that is, its expiration time is in the future). An expired association record is archived and becomes immutable.

Figure 3 illustrates some of the historic associations that the name historian maintains for Jane. As shown in Figure 1, the name-space provider for jmobile@yahoo.com unassigns the name from Jane on May 25, 2000. As a result, even though Jane wishes to retain the name, as evidenced by the link extension she requested to July 1st, the historian stores an archived association record that only extends up to the last time both the name-space provider and Jane agreed on the association, May 1, 2000.

### 3.3 The Name Historian

In this section, we delineate the functionality available to users of HINTS. In particular, we describe the interface to the name historian itself, its design and some implementation details.

The primary objective of any name service is to support name resolution: given a personal identifier, the service must return a “pointer” to the identified person. In the HINTS context, this means that HINTS names must be resolved to primary names, such as email addresses. If Dan Sender wishes to send email to Jane Mobile, he must first resolve the HINTS name with which he previously reached her successfully (Historic\[jmobile@yahoo.com, 03/2000\]) to a currently valid primary name (jane@sample.edu). Keeping track of the last time an email address was used successfully is arguably functionality that current email clients can easily offer, and is very similar in complexity to keeping track, for example, of the last time a web URL was used, which most web browsers do transparently by default. Alternatively, correspondents can remember an approximate time period when they contacted a mobile person and construct a historic name accordingly, perhaps by referring to saved correspondence with the mobile person and extracting dates from that correspondence.

The name historian runs a centralized, trusted service maintaining name histories. The historian is trusted to check the validity of the name histories it stores and to report on those histories when asked. Given the naming model we assume in this design (see Section 2), the historian is a powerful component in the network. In Section 4 we examine the shortcomings of having such a centralized design, and we propose alternatives in Section 5, based on stronger assumptions about name-space providers.

The historian operates a name space itself, consisting of the account names of its users. This name space, however, is only used to authenticate mobile people to the historian and need not be visible externally to the service. The historian manages its own name space similarly to how most web services manage their account name spaces: a client (mobile person in this case) signs up online and receives an account and a means of authentication, such as a password or an asymmetric key pair, for future exchanges with the historian.

To accomplish the task of resolution, the historian must also be able to receive link requests from mobile people as described in the previous section, and send and verify challenges to the holders of primary names to detect name assignment changes.

HINTS can help correspondents who must rely on their own memory to construct a resolution request by presenting them with a history of name associations for the same name. For example, Dan Friend remembers having contacted Jane in the late 90’s, but that is as specific a time frame as he can recall. If he can find out that jmobile@yahoo.com belonged to someone from 1995 to 2000, and then to someone else from 2000 to 2002, then Dan can reasonably choose Historic\[jmobile@yahoo.com, 1999\] to locate Jane Mobile.

In summary, the history service must be able to perform the following tasks:

* Create mobile person accounts.
* Request link changes (linking and unlinking) between a mobile person account and a primary name.
* Resolve a historic name to a currently assigned primary name.
* Retrieve a list of association periods for a primary name.

The historian maintains a database of association records, as described in the previous section. The database maintains two sorted indices, one on \[*name*, *start time*\] and another on \[*person*, *start time*\].

When a mobile person requests to be linked to a name, the historian contacts that name with a random number as a challenge, by email or any other applicable protocol. If the email is returned with the appropriate response to the challenge, then the historian considers the name assigned to the mobile person and creates a new association record. Algorithm 1 details this process.

Links are severed in a similar manner, although no confirmation from the associated primary name is necessary; the reason for severing a link is exactly that the associated primary name is no longer under the control of the mobile person and, as a result, a confirmation from the primary name might not even be possible. However, a notification is sent to the primary name, to make it harder for an unauthorized user of the historian account to make changes unobtrusively. Algorithm 2 describes the process in more detail.

Correspondents query the historian for resolved historic names in a simple request-response protocol. The historian resolves a historic name by, first mapping it to an internal account and then finding the latest still-valid association from that account to a primary name. Algorithm 3 has the details.

Listing association periods for a name is a straightforward operation helped by the database indices maintained.

## 4 Discussion

The name historian we describe in Section 3 achieves the primary goal of this work, reachability in the face of identity mobility. HINTS accomplishes this without the need for brand new globally visible, unique, persistent identifiers for every mobile person. Furthermore, it requires no retrofitting of current name-space providers’ practices, requires no cooperation whatever from those providers, and can be deployed incrementally.

Unfortunately, the simple centralized approach we take here has some shortcomings that can become significant as an increasing fraction of the world’s business and fraud are transacted online. First, it relies on the honesty of the organization that operates the name historian. A centralized, centrally operated historian is a single point of failure, for failures including corruption, malfunction, connectivity disruption or going out of business. Second, the scheme offers no tangible assurances for the correctness of the information it gives out. For example, when a correspondent receives a primary name in response to a resolution request, he has to take the answer on faith; he has to believe that the historian did not invent the association and that the historian checked the validity of the association (i.e., issued a challenge to the claimed primary name and received a satisfactory response). Third, the scheme is only useful to those correspondents and mobile people who trust the historian. If no single historian is globally trusted, then there is no straightforward way to allow any correspondent to reach any mobile person.

Another issue that can potentially affect the utility of HINTS is its reliance on the correspondents’ knowledge of past names for a mobile person. If I never knew Jane Mobile before, there is no historic name that I can use to resolve Jane’s current contact information. HINTS is not intended as a search engine for finding contact information for people I have never attempted to reach before. We believe that web search engines and currently deployed lookup services such as WhoWhere  are more appropriate for that purpose. However, old contact information gathered from such a web search becomes more valuable with HINTS, since it can then potentially be resolved to current contact information.

A third issue that affects the potential success of HINTS is concern for the privacy of individuals. Entering identifiers into a HINTS name trail is voluntary; if a person wants obsolete identifiers to remain so, they need not tell HINTS about those identifiers. However, mobile people need to be aware that there is a risk that messages sent by correspondents to those old identifiers may reach someone else who now has control over that old identifier. If those messages are potentially sensitive, then mobile people may desire to see a widespread use of HINTS. Furthermore, we believe that identifiers inevitably “leak out” to the outside world. True protection from spam and other threats is better performed using other techniques, such as the use of a personal communications proxy through which all incoming communications may be filtered .

In the next section, we sketch an enhanced name historian design that offers the same functionality as what we present in earlier sections, but also alleviates the security and fault-tolerance concerns addressed above. We are currently focusing our design and implementation efforts on this stronger version of HINTS.

## 5 A Secure Name Historian

We believe that the increasing need for online security, the rising cost of identity theft and spoofing and the evolving standardization projects for secure directory access will soon change how name-space providers do naming. We expect that providers will act much more like cooperative but competing certification authorities in the future; in fact, most large enterprises and even some governments  do perform naming or digital certification within their own realms in this more secure fashion.

Furthermore, we believe that unconditional trust in any centralized service is going to be increasingly difficult to digest for security-conscious mobile people.

In this section we enhance our earlier design for a historic name-trail service to address two major concerns: First we use cryptography to prevent illegitimate changes in name-to-person associations, as can be caused by IP and email address spoofing, and eavesdropping on unsecured email. Second, we relax the need for trusting the name historian unconditionally, by employing secure time stamping  and undeniable attestation techniques , to limit the amount of unobtrusive damage a corrupt historian can cause to its clients’ name histories.

We start by describing the stronger and slightly more cooperative name-space providers we need for this enhanced design, and then outline how our earlier concerns can be addressed.

### 5.1 Certification Authorities As Name-Space Providers

A certification authority is not much more than a name-space provider that accompanies the assignment of a name to a person with the issuance of a signed statement called an *identity certificate*, such as the one shown in Figure 4. Note that Jane Mobile is not mentioned explicitly in the certificate. Instead, the provider assigns the name to the person who knows the secret portion of the public key AB34D9…, after having established that Jane Mobile holds that key. The kind of identity verification performed before a name-space provider assigns a name to a person’s public key is provider-specific and out of scope in this paper.

The name-space provider can revoke an assignment by publishing a *revocation certificate*, such as that shown in Figure 5, or by publishing another identity certificate for the same name but a different public key.

Finally, the name-space provider refreshes an assignment by issuing new identity certificates for the same name and key before the previous assignment expires.

Besides this basic certification functionality, in this environment of higher security awareness we assume that name-space providers are cooperative with the history service, in the sense that they notify the historian of name assignment changes by conveying to the historian newly issued identity or revocation certificates. For replay protection, we also assume that each such certificate issued by a name-space provider contains a nonce value, which in the simplest case is the time of issuance, but can also be a random number picked as a freshness challenge.

### 5.2 Certified Historic Naming

One straightforward way to address this harder naming problem is to make all information that the historian maintains signed, so as to prevent illegitimate modifications. To make sure that a corrupt historian cannot divert a name trail by changing to what historian user accounts point, mobile people are represented in name histories by their signing key pairs, called *person keys*, similarly to the approach taken in SPKI/SDSI . In this manner, the online representation of a person becomes “the person who knows the secret signing key”.

Name assignments can be naturally represented with the identity and revocation certificates that name-space providers issue. Linking can be represented with similar *link* and *severance certificates* (see Figures 6 and 7, respectively), signed by mobile people (i.e., the holders of historian accounts) who lay claim on different primary names. Instead of storing a single association record per primary-name-to-mobile-person association, the historian stores all signed certificates delineating the assignment and the linking time periods that make up an association.

The historian can perform the same tasks as those in Section 3.3 with only little more difficulty. For example, to resolve a historic name, the historian must find an association from the historic name to a mobile person and then back from the mobile person to a currently valid name association, as detailed in Algorithm 3. Instead of just locating an association record, the historian must find the appropriate certificates justifying the association from the given historic name to a person and back to another primary name; not only does the historian have to return the answer it found—a primary name or a negative answer—but it must also return a *proof*, the set of certificates that support its response. The correspondent must then check that all the statements are signed correctly, and that they in fact do support a valid resolution, regardless of whether the answer was a primary name or a name-not-found response.

Unfortunately, there are three major issues that face clients of such a name historian: the short lifetime of digital signatures, the need for temporal ordering of historic records, and the need for a “closed”, append-only historic database. We elaborate on all three in turn.

First, digital signatures have a limited lifetime. How does one make sure that a statement signed a few years back was correctly signed at the time, even though the signing key may have by now expired? Some work has been done to make signed documents usable even after the pertinent signing key has expired . In any case, the client must either trust the name-space providers themselves to maintain historic records of when they used what public key pair to sign their issued statements, or trust an external authority, such as the KASTS Key Archival Service , to maintain these records. Briefly, this service maintains a securely time stamped archive of the keys that different name-space providers use during their lifetimes, along with the times when those keys were used. A client who wishes to verify a signed statement, including the certificates we describe above, can look up the name of the provider and the appropriate time period. The returned key can be then used to verify the signature on the statement. However, it is important to also ascertain that the statement was signed *while* the key found was still valid (i.e., before it expired or was revoked).

The ephemeral nature of digital signatures and signing keys also makes it hard to maintain the online representation of mobile people when the historian is not fully trusted, since mobile people must change the public keys that represent them regularly. People do this by issuing and submitting *delegation certificates* to the historian (see Figure 8, delegating their “personhood” from older keys to newer ones. Again, timing is of the essence, since a delegation must be performed before the previous key has to be abandoned, due to expiration or compromise.

Second, any secure historic database must incorporate timing information on when its different records were archived. This is necessary for archived signatures, as described in the previous paragraphs, but also for authorization purposes, in key delegations or associations. For example, given a historic name, to establish the appropriate name association from assignment and linking certificates one must have knowledge of the relative temporal ordering of the issuance of those certificates. It must be shown that the historic name designates a time *after* an identity certificate and a linking statement created an association between the pertinent name and mobile person, but *before* those certificates expire or any potential revocation or unlinking statements came in effect. Relative temporal authentication of certificates in centralized  and decentralized  certificate archives can be invaluable here.

Briefly, relative temporal authentication uses one-way, collision-resistant hash functions, such as SHA-1 , to define the temporal ordering from earlier historic records to later ones. In a sense, a tamper-evident linked list is created from all historic records, so that earlier records appear earlier in the list. Then regularly picked placeholder records from the list are published in a widely witnessed, secure, write-once publication medium, such as a high-circulation newspaper; a verifier who cares about when a particular record was appended into the historic database can trace the linked list backwards and forwards to find the previous and next, respectively, list links published in the newspaper, which in turn places the record in question in a rough time frame, that is, between the publication dates of two newspaper issues in the newspaper example. The collision-resistance and one-way property of the hash function used to link records together guarantees that once a record has been placed in the historic database and the next link from the database has been “committed” on a newspaper, neither the maintainer of the database nor anyone else can tamper with the past, changing when records appear to have been incorporated, adding or removing records, or modifying the contents of those records. This is the basic mechanism behind secure time stamping .

Third, it is important that the historian be unable to “forget” historic records that it has successfully accepted when they were submitted to it. For example, if a name-space provider submits a revocation certificate to the historian and the historian accepts it, it should be unable to deny the existence of such a revocation certificate convincingly when queried later. Undeniable attestation  is a cryptographic construct that allows clients to verify the historian’s claimed existence or non-existence of certain records. The basic idea there is to construct a sorted data structure that allows *undeniable attestations* on its contents, that is, proofs that a particular element belongs or does not belong to the data structure. In the secure HINTS design, the database indices are, in fact, undeniable attesters.

An essential requirement is that attestation proofs are significantly shorter in size than the entire data structure itself. Consider, for example, a historic name database that holds a few billion certificates for many names and many mobile people. It would be extremely unrealistic to have to look through every single record in such a large database before being able to conclude no interesting revocation certificate has been archived there. The constructs from the work by Buldas et al.  and Maniatis and Baker  offer attestations with sizes logarithmic in the number of records stored, which, for extremely optimistic lifetime and popularity projections for a service like HINTS, never exceed roughly 20 KBytes; this is quite an acceptable size for records one expects to receive over the network once or twice a day.

### 5.3 Status

The reduced-trust version of the HINTS design, and a further completely decentralized HINTS, are still under active development. Although we have already designed—or implemented from existed designs—the tools and techniques we describe in the previous section, we have yet to deploy and quantify the implementation of this more secure HINTS system.

## 6 Related Work

The literature regarding naming in distributed systems is vast, so in this section we confine ourselves to a sampling of systems and products that attempt to provide online names specifically for people.

An early design of a global name service  describes how a global hierarchical name space can be implemented across a distributed set of computing resources. Our approach is in a sense the opposite: we assume there are reasons for many separate name spaces to exist, and that people’s online identifiers will move from one such name space to another. It is this identity mobility we address.

The new Internet domain names ending with .name are intended to provide a flat global name space for individuals that is not associated with particular employers and institutions. These names could indeed function as the primary names in our naming scheme. However, there are still many reasons why registrants for these names may end up changing their online identifiers in any case. People who fail to pay their bills may lose access to their .name identifiers. People who change personal names, such as when getting married or taking stage names, may want to reflect this by changing their online identifiers as well. Moreover, these online identifiers may not be the only online identifiers registrants use. A user of a .name identity may also have email service through an employer, and it is hard to prevent identifiers from these other name spaces from ”leaking out” in such a way that correspondents will not attempt to use them after they become obsolete.

IdentiScape  describes a flat global name space for people, in which identifiers do not necessarily reflect their personal names but instead can be a set of space-separated words in unicode. The hope is that this name space is large enough to accommodate many names per person, for everyone in the world, for the next one hundred years. In the back end, IdentiScape maintains identity objects, which are repositories of access-controlled personal information, such as application-specific addresses, credit card numbers and user-specific attributes. In the model of Section 2, IdentiScape is a two-tiered naming scheme. The authors of IdentiScape list identifier persistence as one of the desired traits of online identifiers, but there is nothing to suggest that users will not change names within the IdentiScape name space or use identifiers from other name spaces as well, leaving identity mobility issues unsolved in IdentiScape.

*CommonName*  is one of many online redirection services (others are OneName  and Novell’s DigitalMe ). CommonName allows the use of common names or phrases instead of URLs or email addresses. It also allows the owner of a common name to set up different redirection schedules, for example, the CommonName “Jane Mobile” is redirected to Jane’s personal email address during the weekend but to her work email address on a weekday. Further personalization is possible, such as maintaining globally accessible bookmarks, notes, etc. CommonName provides plug-ins for popular email applications and web browsers. A common name is first assigned according to availability, but then checked by a human for “appropriateness”. Common names must be “appropriate and relevant to \[the\] subscribers’ web and e-mail resources.”

A CommonName is assigned to an account for the duration of the account or the service:

> CommonName is committed to providing this service free of charge for as long as it is commercially viable for it to do so.

However, once an account is discontinued, its CommonName can be reassigned .

*PingID*  is very similar to IdentiScape . An identity server, privately held by an owner of an identity, is responsible for authorizing (or not) the release of information according to whomever is asking. The business goals cover the usual applications: single sign-on, password management, privacy management. PingID does not address identity mobility, in that it does not allow reverse lookups from obsolete primary names to its own name space.

*Classmates.com*  is a service that allows people to register the school or college they attended, the military base at which they served, or the company for which they worked. This allows people who, for example, attended the same class at the same school to reconnect in the future. HINTS has very similar goals to this venture. We also seek to map a mobile person’s presence in the past to a current contact; however, we take a purely online and more general approach, in that a correspondent need not know anything more than the mobile person’s identifier used in the past, rather than first and last names and a class year. This makes it easier for email and other applications to run identifiers through HINTS automatically, perhaps every time they are used, to make sure the most recent identifier is accessed, although it limits the amount of heuristic weeding one can do on likely candidate names. In addition, HINTS provides a trail of past identifiers, allowing correspondents throughout a recipient’s history of identifiers to contact the recipient, even if the correspondents did not know the recipient when he graduated from Sample University in 1957.

## 7 Conclusion

The extremely volatile environment typical to online services and their users makes identifier changes and the commensurate management problems a painful fact of online life. In this paper, we address the problem of identity mobility, by extending the names people commonly use in today’s applications with a designation of a time when those names were successfully used.

We present a simple design for HINTS, a historic name-trail service, that allows mobile people to record and make available their movements through the “identifier landscape”. Correspondents can follow those name trails from where a person has been (i.e., a name she used to have) to where that person is (i.e., a name she uses now). In this way, a correspondent can resolve a temporally qualified name into a name that is valid now; he can use that name to reach a mobile person whom he has not contacted in a long time, avoiding names that point to no one and reassigned names that point to the wrong person.

Finally, we describe how security can enhance HINTS in the increasingly naughty Internet to prevent illegitimate use of historic names and name-history corruption by a malicious service itself. We outline a design for such an enhanced HINTS system, which we hope to evaluate and make available soon.


format: text

text:
# Galaxy formation using halo merger histories taken from N-body simulations

## 1 Introduction

Hierarchical models of galaxy formation must describe both the growth and collapse of density perturbations to form dark matter halos and the baryonic processes which lead to the formation of stars. Despite uncertainty as to the exact nature of the dark matter itself, the formation and evolution of dark matter halos appears to be reasonably well understood. The two main approaches to this problem are direct numerical simulations and analytic techniques such as the Press-Schechter theory (). Encouragingly, the mass functions of dark matter halos predicted using these very different approaches are found to agree to within 50% (). The analytic model described by Sheth & Tormen () based on the assumption that objects collapse ellipsoidally rather than spherically achieves even better agreement with N-body simulations. Mo & White () present halo abundances from this and several other models.

This understanding of the hierarchical build up of structure provides the starting point for semi-analytic models of galaxy formation, which attempt to follow the development of galaxies from primordial density fluctuations. In semi-analytic models, merger histories for dark matter halos may be taken directly from dark matter simulations (e.g. ). Alternatively, extensions to the Press-Schechter theory which predict the conditional halo mass function () and halo survival times, formation times and merger rates () may be used to construct realisations of merger histories for individual halos. Simple analytic modelling is then used to follow the evolution of the baryonic component, including prescriptions for processes such as star formation and its possible effects on the remaining gas. Semi-analytic models (e.g. ) have successfully reproduced many observable properties of galaxies, such as the local field galaxy luminosity function and distributions of colour and morphology. When combined with N-body simulations, semi-analytic models have also successfully reproduced galaxy clustering properties (e.g. ).

Semi-analytic models utilising merger trees generated using algorithms based on the extended Press-Schechter (EPS) formalism have two closely related advantages over models which take merger histories from N-body simulations. Creating Monte-Carlo realisations of merger trees for a set of halos generally requires fewer computing resorces than carrying out an N-body simulation of a similar number of halos. In both cases, improving the mass resolution increases the computational load, but since the load is much less in the Monte-Carlo case, significantly better mass resolution may be achieved. Methods based on the Press-Schechter theory, however are only applicable to initially Gaussian fluctation fields. N-body simulations, on the other hand, have the advantage that the non-linear evolution of density fluctuations is followed in complete generality, without the need for any of the assumptions involved in creating EPS merger trees.

There are advantages to both of these methods, and which is more appropriate depends on the problem being addressed. In this paper we investigate the effects of the choice of merger trees on the predictions of one particular semi-analytic model. We describe a new method of extracting merger trees from an N-body simulation and incorporate these merger trees into a semi-analytic galaxy formation model based on that of Cole et al. (). We compare the predictions of this model to those of a similar model utilising Monte-Carlo realisations of halo merging histories. In order to identify the reasons for the discrepancies that we find, we determine the changes that must be made to the Monte-Carlo model to reproduce the N-body results.

The use of N-body merger trees in semi-analytic models allows a halo-by-halo comparison between the semi-analytic treatment of baryonic processes, such as gas cooling, and direct numerical simulations of galaxy formation. In a companion paper () we carry out such a comparison between a “stripped down” version of the semi-analytic model described in this paper and a smoothed particle hydrodynamics simulation of a cosmological volume.

This paper is laid out as follows. In Section 2 we explain how we obtain merger trees from an N-body simulation. In Section 3 we investigate the effect on our semi-analytic model of utilising merger trees derived from N-body simulations rather than Monte-Carlo realisations. In Section 4 we present our conclusions.

## 2 Extracting Merger Trees

We now present the method we used to calculate the merger histories of dark matter halos identified in an N-body simulation. The simulation, which will be referred to as the GIF simulation, was carried out by the Virgo Consortium using a parallel adaptive particle-particle/particle-mesh ($`\mathrm{AP}^3\mathrm{M}`$) code known as Hydra () as part of the GIF project. The simulation assumes the $`\mathrm{\Lambda }\mathrm{CDM}`$ cosmology with mean mass density parameter $`\mathrm{\Omega }_0=0.3`$, cosmological constant $`\mathrm{\Lambda }_0=0.7`$ in units of $`3H_0^2/c^2`$, power spectrum shape parameter $`\mathrm{\Gamma }=0.21`$, present day rms linear fluctuation amplitude in $`8h^1\mathrm{Mpc}`$ spheres $`\sigma _8=0.90`$, and Hubble constant $`h=0.7`$ in units of $`100\mathrm{k}\mathrm{m}\mathrm{s}^1\mathrm{Mpc}^1`$. It contains $`256^3`$ dark matter particles each of mass $`1.4\times 10^{10}h^1\mathrm{M}_{}`$ in a box of side $`141.3h^1\mathrm{Mpc}`$. The gravitational softening length in the simulation is $`30h^1\mathrm{kpc}`$ at $`z=0`$. This simulation is described in more detail by Jenkins et al. (), where it is referred to as $`\mathrm{\Lambda }\mathrm{CDM2}`$, and by Kauffmann et al. (). While halo catalogues and merger trees based on this simulation are publically available, here we make use of only the simulation outputs themselves and construct merger trees using a somewhat different algorithm to that of Kauffmann et al. We use 44 output times from the simulation which are spaced equally in $`\mathrm{log}_{10}(1+z)`$ between $`z=0`$ and $`z20`$.

### 2.1 Identifying Halos

In order to construct merger histories for dark matter halos in an N-body simulation, a catalogue of halos must be produced for each simulation output using a group finding algorithm. The algorithm used here is the “friends of friends” (FOF) method of Davis et al. (), which simply links together any particles with separations less than the linking length $`b`$, usually expressed in terms of the mean interparticle separation. Given sufficiently large numbers of particles in each object, the FOF algorithm finds regions bounded by a surface of constant density. The density threshold is proportional to $`1/b^3`$.

The FOF approach has the advantage that it imposes no constraints on the geometry of the halos identified, but it may occasionally artificially join two nearby halos if a transient “bridge” of a few particles forms between them. It will be seen in Section 2.2 that this can cause problems when attempting to generate merger trees using FOF group catalogues, and a method of identifying and splitting artificially joined halos is described in Section 2.2.

The usual choice for the linking length in cosmologies with $`\mathrm{\Omega }=1`$ is $`b=0.2`$ (e.g. ), which identifies halos with a mean density similar to that predicted by the top hat spherical collapse model (). However, in cosmologies with $`\mathrm{\Omega }<1`$ there is no rigorous justification for any particular choice. Here, we choose to set $`b=0.2`$ at all redshifts as in the $`\mathrm{\Omega }=1`$ case. See Eke, Cole & Frenk () and Jenkins et al. () for further discussion.

The other parameter needed by the FOF algorithm is the minimum number of particles, $`N_{\mathrm{min}}`$, required to constitute a group. It is important that $`N_{\mathrm{min}}`$ be as small as possible, since detailed merger trees can only be obtained for halos much larger than the smallest resolvable group. Kauffmann et al. () found that in their simulations groups as small as 10 particles are dynamically stable systems and that for 95% of these groups, 80% of the particles remain in the same group at subsequent times.

We therefore identify halos using a linking length $`b=0.2`$ at all redshifts, with a minimum group size of ten particles. The resulting catalogues may still contain some groups which consist of unbound particles which happen to be close together at this particular timestep. To remove these, we follow Benson et al. (\[2001b\]) and calculate the total energy of each group. Unbound groups are not immediately discarded, because they may only be unbound due to the presence of a small number of fast moving particles. The binding energy of each particle is calculated, and the least bound particle is removed from the group. This is repeated until the group becomes bound. If half of the particles are removed or the group is reduced to less than $`N_{\mathrm{min}}`$ particles we discard it. Up to 5% of all groups are discarded, with a similar number of groups being reduced in mass by this procedure. The affected groups generally consist of around 10-20 particles.

We use the procedure described above to generate halo catalogues for 44 simulation outputs between redshifts $`z=20`$ and $`z=0`$, spaced approximately evenly in $`\mathrm{log}_{10}(1+z)`$.

### 2.2 Constructing N-body Merger Trees

In an idealised picture of the process of hierarchical structure formation (e.g. Press-Schechter theory), dark matter halos may increase in mass by mergers, but cannot lose mass. Consequently, any halo identified in a simulation prior to the final output time should still exist at subsequent output times, although it may have become subsumed within a larger halo through a merger. In any case, the constituent particles of the original halo should still all be members of a single group. It should therefore be possible to identify each halo in the simulation as a progenitor of a single halo at the next output time.

In practice there are several ways in which a halo can lose particles. Halos may be disrupted by tidal forces caused by other nearby halos. The masses of simulated halos can also fluctuate because the FOF algorithm imposes a somewhat arbitrary boundary on the halo and outlying particles which are considered group members at one timestep may lie just beyond the boundary at the next timestep.

The technique we use to determine merger histories is intended to take into account this uncertainty in the definition of a halo and a possible loss of particles. First, we consider two adjacent output times from the simulation, $`t_1`$ and $`t_2`$, where $`t_1<t_2`$. Each halo at time $`t_1`$ is labelled as a progenitor of whichever halo at time $`t_2`$ contains the largest fraction of its particles. This process is repeated for all pairs of adjacent output times. It is then straightforward to trace the merger history of each halo which exists at the final output time. Fig. 1 shows an example of a merger tree created in this way for a halo with a final mass of about $`9\times 10^{12}h^\mathit{1}\mathrm{M}_{}`$, or around 700 particles.

In the semi-analytic model used here, galaxies are assumed to form at the centres of dark matter halos, so the centre of each halo in the merger tree must be defined. We choose to follow Kauffmann et al. (), who identified the most bound dark matter particle as the position of any galaxy which forms in the halo. We define the binding energy of a particle as the sum of its kinetic energy and the gravitational potential energy due to the other particles in the halo. This approach differs from that of Benson et al. (\[2001a\]), who associated the central galaxy in a halo with the centre of mass. Once a galaxy forms it is assumed to follow this particle until the parent halo merges with another halo and dynamical friction, calculated as described in Cole et al. (), causes the galaxy to merge with the central galaxy of the new halo. We therefore check that the most bound particle of a halo remains a member of the same halo as the majority of the halo’s constituent particles at the next output time. If this is not so, we choose the most bound particle from those which *are* in the correct halo at the later output time. This problem generally only occurs in smaller halos which may be easily disrupted.

During the construction of the merger trees, we also attempt to deal with the problem mentioned in Section 2.1 — the possibility that nearby halos may be artificially linked by the FOF algorithm. The problem occurs if two halos become temporarily linked by a transient “bridge” of particles which causes the FOF group finder to consider them as a single, large group. When the bridge is later broken, the group splits, leaving the two original halos. Our tree building method would identify the large, joined group as a progenitor of the larger of the two final groups.

These situations are identified by looking for groups at the earlier time $`t_1`$ whose particles are shared between two or more groups at the subsequent output time $`t_2`$. This indicates that between times $`t_1`$ and $`t_2`$ the group has split into smaller groups which we refer to here as “fragments”.

We split such spuriously joined groups into one new group for each fragment which contains more than $`N_{\mathrm{min}}`$ of its constituent particles. Particles belonging to one of these fragments at time $`t_2`$ are assigned to the corresponding new group at the earlier time $`t_1`$. Particles belonging to no fragment, or to a fragment with fewer than $`N_{\mathrm{min}}`$ particles from the joined group, are assigned to the new group corresponding to the fragment “closest” to their position at time $`t_1`$. The separations used are weighted by a factor $`M^{1/3}`$ to account for the spatial extent of the groups, where $`M`$ is the mass of the fragment.

The splitting procedure is first carried out for halos at the penultimate timestep and then repeated for each earlier output time in order of increasing redshift. For each timestep a modified group catalogue is produced, which is then used to determine whether any halos at the previous timestep need to be split. This ensures that if any bridge between a pair of halos persists for more than one timestep the halos are split at each timestep where the bridge exists.

### 2.3 Mass Conservation

In the galform semi-analytic model of Cole et al. (), halos may gain mass through mergers with other halos. The mass of a halo always increases with time, and the difference between the mass of a halo and the sum of the masses of its progenitors is due to the accretion of small, unresolved dark matter halos.

The N-body merger trees may contain halos which decrease in mass from one timestep to the next for the reasons described in Section 2.2 — the nature of the definition of a halo imposed by the FOF group finder and the possibility of disruption by tidal forces. Consequently, a halo in a N-body merger tree may be somewhat *less* massive than its progenitors. In the galform model this corresponds to the unphysical situation where a negative amount of mass is accreted in the form of sub-resolution halos.

The solid lines in Fig. 2 show the distribution of the ratio $`\mathrm{\Sigma }\mathrm{M}_{\mathrm{prog}}/\mathrm{M}_{\mathrm{halo}}`$, where $`\mathrm{M}_{\mathrm{halo}}`$ is the mass of a halo and $`\mathrm{\Sigma }\mathrm{M}_{\mathrm{prog}}`$ is the total mass of the immediate progenitors of the halo, which exist at the previous timestep. Halos at all timesteps (other than the first) are included. If these merger trees had been created using the technique of Cole et al. (), then this ratio would always be less than one. It can be seen from Fig. 2 that for halos less massive than about $`10^{12}h^1\mathrm{M}_{}`$ the total mass in the progenitors can occasionally exceed the mass of the halo they form at the next timestep by up to 50%. More massive halos are less affected, but there are still rare instances where the largest halos have progenitors with masses 5-10% greater than the mass of the halo.

Mass conservation can be forced on the N-body merger trees by simply adjusting the masses of some of the halos. Two opposite approaches to the problem are possible. Mass can be added to those halos which are less massive than their progenitors, or mass can be removed from the progenitors themselves. In order to show that the changes made to the halo masses have little effect on the semi-analytic model, we create merger trees using both methods.

Enforcing the conservation of mass in merger trees by adding mass is relatively straightforward. If a halo is less massive than its progenitors, its mass is increased to match that of the progenitors. The halo may, in turn, be a progenitor of a later halo which may now become less massive than its own progenitors. This later halo’s mass will then also be increased. Changes made to halo masses at early times may therefore propagate to later times.

Similarly, if mass is removed from a halo to force conservation of mass, it may become less massive than its progenitors and reductions in mass could then propagate to earlier times. We attempt to remove mass in such a way as to minimize the effects on earlier halos. Each halo has a certain amount of “excess” mass beyond that of its progenitors, which was accreted over the last timestep in the form of sub-resolution objects. This mass, if it exists, may be removed without the change propagating to earlier halos. When a halo which is less massive than its progenitors is found, mass is first removed from the excess mass of the largest progenitor. If still more mass must be removed, it is taken from the excess mass of the other progenitors in decreasing order of mass. If all of the excess mass of the progenitors is removed and yet more mass needs to be taken away, the masses of all of the progenitor halos are simply scaled down by a constant factor.

The dotted lines in Fig. 2 show the sizes of the changes we are forced to make when we enforce mass conservation by adding mass to halos. These lines show the distribution of the ratio $`\mathrm{\Sigma }\mathrm{M}_{\mathrm{prog}}/\mathrm{M}_{\mathrm{halo}}`$ if $`\mathrm{\Sigma }\mathrm{M}_{\mathrm{prog}}`$ is evaluated after the progenitors of the halo at all previous timesteps have been made at least as massive as their own progenitors. $`\mathrm{M}_{\mathrm{halo}}`$ is still the original halo mass. Where this ratio exceeds 1, it is the factor by which $`\mathrm{M}_{\mathrm{halo}}`$ must be scaled to ensure that the halo is at least as massive as its progenitors. It can be seen that the required changes to individual halos are generally small, and adjustments are required much less frequently in well resolved halos. However, the masses of a minority of halos are affected quite significantly and it is necessary to show that these changes do not affect the galaxy population predicted by the semi-analytic model. The algorithms described above are two opposite ways of dealing with the problem of mass conservation in the merger trees. While artificially altering the halo masses is clearly not ideal, if, as is the case, both methods produce very similar results when the merger trees are fed into the semi-analytic model we can then conclude that the changes we have made are insignificant. This comparison is carried out in Section 3.3.

## 3 Comparison between GALFORM and N-body GALFORM

In this section we describe our semi-analytic model, indicating how it differs from the model of Cole et al. () on which it is based. We also explain how merger trees obtained from a simulation may be incorporated into the model.

### 3.1 The N-body GALFORM model

We use the galform semi-analytic model to treat the process of galaxy formation within the dark matter halos in the GIF simulation. The model is described in detail by Cole et al. () so here we present only a brief description of features that are important to this work. The original model of Cole et al. will be referred to as “standard galform”, and the version using merger trees taken from a simulation will be referred to as “N-body galform”.

The starting point for the standard galform model is a set of merger trees created using a Monte-Carlo technique. The history of each halo is divided into a number of discrete timesteps. Extended Press-Schechter theory is used to estimate the probability that a halo “fragments” into two progenitors when a step back in time of size $`\delta t`$ is taken. The masses of the fragments are chosen at random from a distribution consistent with extended Press-Schechter theory. Halos are repeatedly split in this way to create merger trees. A mass resolution limit is imposed on the merger trees, below which progenitors are considered to be material acquired through continuous accretion. The mass resolution is normally set sufficiently high that the results of interest are not sensitive to its value. In the N-body galform model, we replace these merger trees with those calculated directly from the GIF simulation as described in Section 2.2. The mass resolution limit is then determined by the mass of the smallest halo which can be resolved in the simulation.

The dark matter halos in the merger tree are assumed to be spherically symmetric with the radial density profile of Navarro, Frenk & White (, ):

$$\rho (r)\frac{1}{r/r_{\mathrm{NFW}}(r/r_{\mathrm{NFW}}+1)^2},$$
(1)
where $`r_{\mathrm{NFW}}`$ is the scale radius of the halo and is related to the concentration parameter, $`c`$, defined by Navarro, Frenk & White () through $`r_{\mathrm{NFW}}=r_{\mathrm{virial}}/c`$, where $`r_{\mathrm{virial}}`$ is the virial radius of the halo. The concentration parameter is set using the method described in the appendix of the same paper. We do not allow for any scatter in the concentration parameter as a function of halo mass.

Our treatment of the cooling of gas within halos is identical to that of Cole et al. (). Initially, the amount of gas in each halo is taken to be equal to the mass of the halo times the universal baryon fraction. The gas is assumed to be shock-heated to the virial temperature of the halo when it forms. We assume that the radial density profile of the gas is given by

$$\rho _{\mathrm{gas}}(r)1/(r^2+r_{\mathrm{core}}^2),$$
(2)
where the core radius is given by $`r_{\mathrm{core}}/r_{\mathrm{NFW}}1/3`$ in accordance with the simulations of Navarro et al. (). This core radius is allowed to grow with time from an initial value, $`r_{\mathrm{core}}^0`$, as gas is removed by cooling in order to maintain the same gas density at the virial radius. This ensures that the pressure at the virial radius, which would be maintained by shocks from infalling material, remains unchanged.

To determine the rate at which gas can cool and form a disk at the centre of the halo, the cooling time of the gas is calculated as a function of radius using the cooling function of Sutherland & Dopita (). Gas which has had time to cool and fall to the centre of the halo is added to the disk where it is available to form stars.

When halos merge, the most massive galaxy becomes the central galaxy in the new halo. The resolution of the simulations used here is insufficient to follow the evolution of substructure within the dark matter halos. Instead, the dynamical friction time scale, as defined by Lacey & Cole (), is used to determine when each satellite will merge on to the central galaxy. It should be noted at this point that the orbital parameters used to determine the dynamical friction time for each galaxy are assigned at random from a distribution consistent with the numerical results of Tormen (), even when using merger trees obtained from the simulation.

### 3.2 Parameters in the N-body GALFORM model

The galform semi-analytic model requires a number of parameters to be specified, which can be divided into three categories. There are numerical parameters, parameters describing the background cosmology and parameters which describe the physical model of galaxy formation.

The numerical parameters are the mass resolution, $`M_{\mathrm{res}}`$, the number of timesteps in the merger tree and the starting redshift. In the N-body galform model these are all constrained by the properties of the simulation used to obtain the merger trees. The mass resolution is the mass of the smallest halo which our group finding algorithm can resolve, there is one timestep for each simulation output and the starting redshift is the redshift of the first output. The cosmological parameters $`\mathrm{\Omega }_0`$, $`\mathrm{\Lambda }_0`$, $`h`$, $`\sigma _8`$, $`\mathrm{\Gamma }`$ and, in the case of a simulation with a baryonic component, $`\mathrm{\Omega }_b`$, are also fixed by the simulation.

The remaining parameters allow us to vary the treatment of the processes involved in galaxy formation. The parameters we are interested in are:

* $`r_{\mathrm{core}}^0`$: the initial size of the core in the radial gas density profile, specified in terms of $`r_{\mathrm{NFW}}`$ (see eqn. 2).
* The evolution of $`r_{\mathrm{core}}`$ with time. The radius $`r_{\mathrm{core}}`$ may be a fixed fraction of $`r_{\mathrm{NFW}}`$ or it may be allowed to increase with time as described in Section 3.1
* $`f_{\mathrm{df}}`$: A factor by which the dynamical friction time scale for a satellite galaxy, which is used to determine when the galaxy merges with the central galaxy of the halo, may be scaled. Increasing $`f_{\mathrm{df}}`$ reduces the rate at which galaxy mergers occur within halos.

The other parameters in the model are the same as those in the reference model of Cole et al. (), with the following minor changes: $`v_{\mathrm{hot}}=250\mathrm{k}\mathrm{m}\mathrm{s}^1`$ and $`f_{\mathrm{ellip}}=0.5`$. The parameter $`v_{\mathrm{hot}}`$ determines the efficiency with which energy injection from supernovae and young stars reheats and ejects cold gas from galactic disks. The parameter $`f_{\mathrm{ellip}}`$ is used to decide the outcome of mergers between central and satellite galaxies. If the ratio of the mass of the satellite to the mass of the central galaxy is greater than $`f_{\mathrm{ellip}}`$, any gas in the disks of the two galaxies is converted into stars and an elliptical galaxy is produced. If the ratio is smaller than $`f_{\mathrm{ellip}}`$, any stars present in the satellite are added to the bulge of the central galaxy and any gas is added to the disk. These changes to the Cole et al. model are required to obtain a realistic luminosity function at $`z=0`$ with the higher baryon density, $`\mathrm{\Omega }_\mathrm{b}=0.038`$, which we use here.

Our prescription for star formation differs slightly from that of Cole et al. In our model, the time scale for star formation is given by

$$\tau _{}=\tau _{}^0(V_{\mathrm{disk}}/200\mathrm{k}\mathrm{m}\mathrm{s}^1)^\alpha _{},$$
(3)
where $`V_{\mathrm{disk}}`$ is the circular velocity of the galaxy disk and the time scale, $`\tau _{}^0`$, is set to 3Gyr. We set $`\alpha _{}=2.5`$. The way $`\tau _{}`$ scales with redshift in this model results in reduced star formation and more gas rich mergers at high redshift and has been shown () to better reproduce the properties of SCUBA and Lyman break galaxies. Kauffmann & Haehnelt () also find that a star formation scheme with an increased star formation timescale at high redshift is required to reproduce observations of damped Ly$`\alpha `$ absorption systems and the increase in number density of bright quasars from $`z=0`$ to $`z=2`$. It should also be noted that, for the purposes of this comparison, the details of our star formation prescription are not critical, since the same scheme is used in both the standard and N-body galform models.

### 3.3 Effects of mass conservation

The upper panels of Fig. 3 show the galaxy luminosity functions in the $`\mathrm{b}_\mathrm{J}`$ and K bands predicted by the N-body galform model with the parameters of Section 3.2, using the two different methods described in Section 2.3 to enforce mass conservation in the merger trees. Over most of the luminosity range plotted, the two curves are essentially identical but there appear to be more galaxies at very faint $`\mathrm{b}_\mathrm{J}`$ magnitudes when mass is removed from the merger trees. The majority of these galaxies formed in halos near the 10 particle ($`1.4\times 10^{11}h^1\mathrm{M}_{}`$) mass resolution limit imposed by the FOF group finder and their halos subsequently merged with other, larger dark matter halos. When mass conservation is enforced by removing mass from the merger trees (the dotted lines in Fig. 3) it is possible to end up with some halos with mass less than the resolution limit which can harbour galaxies with $`\mathrm{b}_\mathrm{J}`$ band magnitudes around -14 or fainter. If, instead, mass is added to halos less massive than their progenitors, then the merger trees contain no halos with masses below the FOF resolution threshold and hence fewer faint galaxies.

These sub-resolution halos often exist in the merger trees of larger halos and could affect the evolution of larger, brighter galaxies. However, the agreement of the luminosity functions suggests that any effect is insignificant. The global star formation history and Tully-Fisher relation shown in the lower panels of Fig. 3 are similarly unaffected.

Overall, the choice of mass conservation method appears to make very little difference to the quantities plotted in Fig. 3, which suggests that the small amounts of mass being added to or removed from the merger trees do not significantly affect the properties of the resulting galaxies. The only region of the luminosity function which is affected is largely populated by galaxies which formed in halos with little or no resolved merger history, where the model cannot be expected to give reliable results. For the remainder of this paper we choose to enforce mass conservation by adding mass to the merger trees since this does not introduce halos with masses below the resolution limit.

### 3.4 Comparison with standard GALFORM

The mass resolution of the merger trees taken from the GIF simulation is equal to 10 particle masses or $`1.4\times 10^{11}h^1\mathrm{M}_{}`$, i.e. $`N_{\mathrm{min}}=10`$. This is much larger than the mass resolution, $`M_{\mathrm{res}}=5.0\times 10^9h^1\mathrm{M}_{}`$, used by Cole et al. (). This will clearly affect the properties of the galaxies predicted by the N-body galform model, since gas will be unable to cool and start forming stars until lower redshifts when halos with masses greater than $`M_{\mathrm{res}}`$ have formed. In order to investigate the effect of limited mass resolution on the N-body galform model, we identify the properties of the merger trees which differ between standard and N-body galform and use this knowledge to produce a modified version of the standard galform model which reproduces the behaviour of the N-body galform model. We can then increase the mass resolution of the merger trees in the modified model and observe the effects on the predicted galaxy properties.

There are four main reasons why the merger trees in the two models may differ. Firstly, there is the difference in mass resolution described above. Therefore, we initially degrade the mass resolution of the standard galform model to match that of the GIF simulation by setting the minimum halo mass, $`M_{\mathrm{res}}`$, equal to the mass of $`(N_{\mathrm{min}}1)`$ dark matter particles — any halo of this mass or less in the N-body simulation would not be identified by the FOF group finder and would not be included in the N-body merger trees.

Secondly, Jenkins et al. () have shown that the Press & Schechter () halo mass function (used in the standard galform model) differs somewhat from the mass function determined from N-body simulations. We replace the Press-Schechter mass function in the standard galform model with the mass function determined by Jenkins et al. This ensures that the distribution of halo masses at $`z=0`$ in the standard galform model matches the distribution in the simulation.

The number of timesteps also differs between the two models. In the standard galform model we use 150 timesteps evenly spaced in $`\mathrm{log}_{10}(1+z)`$, whereas in the N-body case we have only 44 simulation outputs. However, we find that if we degrade the time resolution of the standard galform model to match that of the N-body model the properties of the galaxy populations predicted change very little.

Finally, the distribution of progenitor masses for halos of a given mass predicted by the standard galform model does not reproduce the distribution found in N-body simulations with complete accuracy. Benson et al. (\[2001a\]) show that an empirical correction can be used to bring the progenitor mass distributions in the semi-analytic and N-body merger trees into closer agreement. The threshold linear overdensity for collapse from the spherical collapse model, $`\delta _c`$, is replaced with an effective threshold $`\delta _c^{\mathrm{eff}}=f_{\delta _c}\delta _c`$. In the $`\mathrm{\Lambda }\mathrm{CDM}`$ cosmology employed in the GIF simulation, the following form for $`f_{\delta _c}`$ was found by Benson et al. to give reasonable agreement between the progenitor mass functions between redshifts 0 and 3:

$$f_{\delta _c}=1+0.14[\mathrm{log}_{10}(\mathrm{M}_{\mathrm{halo}}/h^\mathit{1}\mathrm{M}_{})15.64],$$
(4)
where $`\mathrm{M}_{\mathrm{halo}}`$ is the mass of the final halo at redshift $`z=0`$. This form of modification was suggested by Tormen ().

These modifications are intended to produce semi-analytic merger trees with statistical properties closely matched to those of the N-body merger trees. Fig. 4 shows the galaxy luminosity functions in the $`\mathrm{b}_\mathrm{J}`$ and K bands, Tully-Fisher relations and global star formation histories for both the modified galform model described above (dotted lines) and the N-body galform model (dashed lines). It can be seen from the figure that these two models predict populations of galaxies with very similar statistical properties. The luminosity functions are in reasonable agreement for $`\mathrm{K}`$ brighter than about -18 and $`\mathrm{b}_\mathrm{J}`$ brighter than about -15. The Tully-Fisher relations and star formation histories are also in close agreement.

As pointed out previously, the fainter galaxies in these models occupy halos with very poorly resolved merger histories and their properties may be largely determined by the effects of limited mass resolution. The solid lines in Fig. 4 show the properties of the galaxies in the modified galform model when the minimum halo mass $`M_{\mathrm{res}}`$ is reduced to $`5.0\times 10^9h^1\mathrm{M}_{}`$. This is much less massive than the smallest halo Benson et al. were able to resolve in their simulations and consequently, in this regime, eqn. (4) has not been tested and cannot be relied upon to produce a realistic distribution of progenitor masses. We do not expect this model to reproduce the results of Cole et al. but we show it only to provide some indication of the magnitude of the effect of introducing low mass halos into the merger trees.

This “improvement” in mass resolution increases the number of faint galaxies, which form in small, previously unresolved halos. With a higher minimum halo mass the gas in these small halos is unable to cool until it becomes incorporated into objects more massive than $`M_{\mathrm{res}}`$. This is reflected in the luminosity functions which show that there are slightly more bright galaxies and far fewer faint galaxies at $`z=0`$ in the model with poor mass resolution. The star formation history is consistent with this, showing that poor mass resolution results in reduced star formation at $`z>1`$ and increased star formation at $`z0`$. However, calculating the global star formation rate involves a sum over all halos. At high redshifts this includes a large number of halos of low mass whose abundances may be unrealistic due to our extrapolation of eqn. (4). Reducing $`M_{\mathrm{res}}`$ appears to have little or no effect on the Tully-Fisher plot.

Overall, the predictions of the N-body galform model closely match those of the standard galform model when we take into account the differences in the halo mass function, the progenitor mass distribution and the mass resolution. The differences between the modified galform models with high and low mass resolution indicate that, at low luminosities, the properties of the galaxies in the N-body model are seriously affected by the resolution of the simulation. In order to attempt accurately to reproduce the properties of observed galaxy populations with $`\mathrm{b}_\mathrm{J}`$ band magnitudes fainter than about -17, an N-body simulation with significantly improved mass resolution would be required.

## 4 Conclusions

In this paper we have examined how the statistical properties of the galaxies predicted by a semi-analytic model depend on the way in which the dark matter halo merger histories are created. We have developed a method for calculating merger histories from N-body simulations and used the resulting merger trees in a semi-analytic model of galaxy formation based on that of Cole et al. (). We refer to this model as N-body galform and compare it to an otherwise identical “standard galform ” model, which uses halo merger histories generated using the Monte-Carlo algorithm of Cole et al. This algorithm is based on the extended Press-Schechter (EPS) theory.

We find that in a significant number of cases, halos in the N-body merger trees are less massive than their progenitors at the previous timestep. When this happens we are forced artificially to adjust the masses of the halo or its progenitors, since in our semi-analytic galaxy formation model halos may not lose mass. However, the luminosity function, Tully-Fisher relation and global star formation history of the galaxies predicted by the semi-analytic model remain almost exactly the same whether we add mass to the halo or remove mass from the progenitors when we encounter this problem. We conclude that the changes we are forced to make to the halo masses have very little effect on the semi-analytic model.

If the mass resolution in the standard galform model is degraded to that of the N-body simulation and the empirical fit of Benson et al. (\[2001a\]) is used to correct the distribution of halo progenitor masses, we obtain luminosity functions and Tully-Fisher relations in very good agreement with the N-body galform model. This shows that, apart from the issue of mass resolution, the only significant statistical differences between the N-body merger trees and those of Cole et al. are due to the known discrepancy between EPS theory and the results of N-body simulations.

By improving the mass resolution in the standard galform model to that used by Cole et al. we were able to obtain an indication of the effects of limited mass resolution on the N-body model. The mass resolution in the N-body merger trees is imposed by the particle mass in the GIF simulation, since halos with fewer than 10 particles ($`1.4\times 10^{11}h^\mathit{1}\mathrm{M}_{}`$) are not resolved. This limitation has a noticeable effect on the galaxy luminosity function and we find slightly more very bright galaxies, since gas may only cool in resolved halos. If only massive halos are resolved, cooling is delayed resulting in brighter galaxies at $`z=0`$. However, the most obvious effect of poor mass resolution is a drastic reduction in the number of galaxies with $`b_\mathrm{J}`$ magnitudes fainter than about -17. This demonstrates that the mass resolution of the GIF simulation is insufficient to make reliable predictions at these magnitudes. At brighter magnitudes the luminosity functions remain in good agreement.

In conclusion, when used as the starting point for semi-analytic modelling of galaxy formation, merger trees taken from an N-body simulation using the technique described in this paper result in similar galaxy populations to those obtained using the (slightly modified) Monte-Carlo algorithm of Cole et al. This supports the reliability of our method and provides a means to populate large cosmological N-body simulations with semi-analytic galaxies at a fraction of the computational cost of a hydrodynamic simulation of the same volume. When applied to the dark matter component of an Smooth Particle Hydrodynamics (SPH) simulation, our model will also allow us to compare SPH and semi-analytic treatments of galaxy formation, and in particular the cooling of gas within halos, on a halo-by-halo basis. This comparison is reported in a companion paper (Helly et al. .)

## Acknowledgements

We acknowledge support from PPARC and the Royal Society.


text:
# On a loss of information in a transition from quantum to a quasi-classical regime

## Abstract

By defining information entropy in terms of probabilities densities $`|\mathrm{\Psi }|^2`$ ($`\mathrm{\Psi }`$ is a wave function in the coordinate representation) it is explicitly shown how a loss of quantum information occurs in a transition from a quantum to a quasi-classical regime.

The Boltzmann-Gibbs-Shannon entropy

$$I=\underset{i=1}{\overset{N}{}}p_iLogp_i$$
(1)
($`p_i`$ is the classical probability) has an obvious relation to von Neumann entropy

$$S=Tr\rho Log\rho $$

where the diagonal terms of the density matrix $`\rho `$ are the probabilties $`p_i`$.

Usually in quantum mechanics the probability $`p_i`$ is considered as a function of energy $`E_i`$ (e.g. ). Since we study a rather narrow problem of information dynamics when the probability is described in terms of the wave function $`\mathrm{\Psi }`$, we will not discuss a more sophisticated (and complete) approach based on the density matrix and information processing involving quantum bits (qubits) ( e.g., ).

To achieve our goal ,we proceed along the lines used in derivation of continuity equation for probability density. To this end consider the probability in its coordinate representation. Thus $`p_i`$ can be viewed as a probability of finding a particle in a spatial interval $`\mathrm{\Delta }q_i=q_{i+1}q_i`$:

$$p_i=_{q_i}^{q_{i+1}}\mathrm{\Psi }(q)^{}\mathrm{\Psi }(q)𝑑q$$
(2)
Using the mean value theorem, we rewrite Eq.(2) as follows:

$$p_i=|\mathrm{\Psi }_i(\stackrel{~}{q}_i)|^2\mathrm{\Delta }q_i,q_i\stackrel{~}{q_i}q_{i+1}$$
(3)
where the sum of $`p_i`$ over all spatial intervals is

$$\underset{i=1}{\overset{\mathrm{}}{}}p_i=\underset{i=1}{\overset{\mathrm{}}{}}|\mathrm{\Psi }_i(\stackrel{~}{q}_i)|^2\mathrm{\Delta }q_i=1$$
(4)
Using Eq.(3) we get

$$p_iLogp_i=|\mathrm{\Psi }_i|^2\mathrm{\Delta }q_i[Log(|\mathrm{\Psi }_i|^2)+Log(\mathrm{\Delta }q_i)]$$
(5)
Now we take the following limit of (5)

$$\mathrm{\Delta }q_i0;\mathrm{\Delta }q_idq$$

As a result, Eq.(5) yields

$$p_iLogp_i|\mathrm{\Psi }(q)|^2dq(Log|\mathrm{\Psi }(q)|^21)+O(|\mathrm{\Delta }q|^2)$$
(6)
and equation (1) becomes respectively:

$$I=|\mathrm{\Psi }(q)|^2(Log|\mathrm{\Psi }(q)|^21)𝑑q$$
(7)
Therefore we narrow our discussion even more by restricting it with continuous spectra.

In a 3-D case the integration Eq.(7) is carried over a spatial volume $`d^3q.`$ This means that the expression

$$\rho _I=|\mathrm{\Psi }(q)|^2(Log|\mathrm{\Psi }(q)|^21)$$
(8)
can be interpreted as the volume information density

$$\rho _I=dI/dV$$
(9)
We find its time variation:

$$\frac{\rho _I}{t}=\frac{|\mathrm{\Psi }(q)|^2(Log|\mathrm{\Psi }(q)|^21)}{t}=\frac{|\mathrm{\Psi }|^2}{t}Log|\mathrm{\Psi }|^2$$
(10)
If we use the continuity equation for probability density (e.g.,)

$$\frac{|\mathrm{\Psi }|^2}{t}=\frac{\mathrm{}}{2im}div(|\mathrm{\Psi }|^2Log\frac{\mathrm{\Psi }}{\mathrm{\Psi }^{}})$$

then we obtain from Eq.(10)

$`{\displaystyle \frac{\rho _I}{t}}={\displaystyle \frac{\mathrm{}}{2im}}div(|\mathrm{\Psi }|^2Log{\displaystyle \frac{\mathrm{\Psi }}{\mathrm{\Psi }^{}}})Log|\mathrm{\Psi }|^2`$
$`div(|\mathrm{\Psi }|^2Log|\mathrm{\Psi }|^2{\displaystyle \frac{\mathrm{}}{2im}}Log{\displaystyle \frac{\mathrm{\Psi }}{\mathrm{\Psi }^{}}}){\displaystyle \frac{\mathrm{}}{2im}}Log{\displaystyle \frac{\mathrm{\Psi }}{\mathrm{\Psi }^{}}}|\mathrm{\Psi }|^2`$ (11)
Inserting the definition of the information density $`\rho _I`$, Eq.(8), and denoting the probability density $`|\mathrm{\Psi }|^2=\rho `$ into the first term on the right hand side of Eq.(On a loss of information in a transition from quantum to a quasi-classical regime) , we obtain

$$\frac{\rho _I}{t}=div[\frac{\mathrm{}}{2im}(\rho _I\rho )Log\frac{\mathrm{\Psi }}{\mathrm{\Psi }^{}}]\frac{\mathrm{}}{2im}Log\frac{\mathrm{\Psi }}{\mathrm{\Psi }^{}}|\mathrm{\Psi }|^2$$
(12)
Let us consider the transition to the classical case by representing the wave function as follows

$$\mathrm{\Psi }=\sqrt{\rho }e^{iS/\mathrm{}}$$
(13)
Using (13) in (12), we get

$$\frac{\rho _I}{t}=div[\frac{S}{m}(\rho _I\rho )]\frac{S}{m}\rho $$
(14)
In the classical limit $`\mathrm{}t_c/mL_c^20`$ ( where $`L_c`$ is a characteristic length and $`t_c`$ is the characteristic time) phase $`S`$ becomes a classical action. As a result $`S/m=\stackrel{}{v}`$, that is a classical particle velocity. This means that in this limit Eq.(14) yields

$$\frac{\rho _I}{t}=div[\stackrel{}{v}(\rho _I\rho )]\stackrel{}{v}\rho $$
(15)
If we integrate (15) over a volume $`V`$, use definition of the information entropy (9), and Gauss’s theorem, we obtain

$$\frac{}{t}\rho _i𝑑V=\frac{I}{t}=(\rho _I\rho )\stackrel{}{v}\stackrel{}{dA}\stackrel{}{v}\rho dV$$
(16)
By taking the boundary of the volume $`V`$ to infinity and assuming that $`\rho (q\mathrm{})0`$ we obtain from (16)

$$\frac{I}{t}=\stackrel{}{v}\rho dV$$
(17)
This means that in a transition from a quantum to classical regime the information entropy $`I`$ \[defined in the above narrow sense, Eq.(7)\] is not conserved. Instead, if the classical velocity is in the direction of an increase of probability density, the information entropy decreases. Inversely,if the classical velocity is in the direction of a decreasing probability density, the information density increases.

These results are in agreement with the meaning of the information entropy as a number of states accessible to a system. In a transition to a classical regime this number drastically decreases, thus signaling a decrease in information entropy. Quite in agreement with that, and from another point of view, the less probable states carry more information than the more probable states.

One can interpret these results as a statement that a classical regime has less degree of freedom than its quantum counterpart. This is definitely true when there is such a counterpart.

As we have already stated earlier, the above definition of information entropy is not fully appropriate for quantum mechanics because it does not take into account the information carried by a quantum phase. This serves as a strong indication that in the quantum region one needs to use another, more general, definition of information entropy , not necessarily associated with the qubits, which will account for the information associated with the quantum phase .

Acknowledgments

The author thanks V.Panico and C.Wulfman for the illuminating discussions of the results.