| EPSRC Reference: |
EP/C003454/1 |
| Title: |
The Doomsday Protocol |
| Principal Investigator: |
Morrison, Professor R |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of St Andrews |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
16 August 2004 |
Ends: |
15 November 2004 |
Value (£): |
3,850
|
| EPSRC Research Topic Classifications: |
| Information & Knowledge Mgmt |
Software Engineering |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
The intuition behind the Doomsday protocol is stated in the following terms. The government of a certain country needs to keep a global track of all people having citizenship of that country. A citizen may move from the country of their birth to any other country during their lifetime, eventually dying in a country perhaps different from that of their birth. The government Registry Office wishes to keep as accurate a record as possible of the size of this diaspora, and particularly to detect if and when it becomes extinct.However, it is imperative to avoid a false positive in this regard, which would constitute a serious violation of the human rights of the remaining population. The only information available to the government about individuals consists of two notifications, one at the registration of their birth and one at the registration of their death, each sent from the country where the event occurs. Is this information sufficient; if not what additional constraints will make it so?It turns out that the information is sufficient under two conditions:* Communications to the Registry Office from any particular country are delivered in the order they are sent.* When a birth occurs in a certain country, at least one citizen must be resident there currently and in perpetuity - we call them a witness to the birth.These conditions guarantee that extinction will never be called erroneously, and they bound the error in any instantaneous estimate of the population size. The work here is to prove formally that when the Registry Office detectes that there are no people in existence there really are none.The Doomsday protocol as described above is an alegory for a generic family of distributed termination detection algorithms. These are important since they detect globally stable states in parallel computations that communicate by asychronous messages. In this application we seek support for a Visiting Fellow to develop the Doomsday protocol.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.st-and.ac.uk |