Trust-but-Verify Name Service.pdf

A distributed name service is proposed, called Trust-but-Verify, which provides robustness against adversarial attacks under certain assumptions. The system consists of peers with unique identities, and the goal is to implement Join, Leave, and Lookup operations concurrently and reliably in an asynchronous environment without trust relationships. A certification authority is assumed to be available, which issues certified names to peers and prevents peers from taking over names of other peers. The system is designed to be robust against adversarial peers with an unlimited number of identities, as long as the adversarial peers are in the minority. The operations are defined as follows: Join(p) adds a peer p to the system, Leave(p) removes a peer p from the system, and Lookup(Name) returns the IP address of the peer with the given name or NULL if no such peer exists. The system is designed to be robust against various attacks, including Sybil attacks, and is assumed to be asynchronous with arbitrary adversaries and bounded presence. The certification authority maintains a mapping of names to IP addresses, and the lookup operation is well-defined as long as the operations are correctly implemented and executed.