DHT Chord

Indicate the correct answers regarding flooding-based search in P2P systems (2 correct answers). Flooding guarantees logarithmic lookup complexity. Flooding does not require any routing state at intermediate nodes. Flooding generates a high communication overhead. Flooding is robust against single node failures. Flooding always guarantees no false negatives.

Which statements about a central server approach are correct? (2 correct answers). Lookup complexity is O(1). The system has no single point of failure. Node state is distributed evenly among all peers. The central server must store information about all nodes. It scales well for very large systems.

Which lookup strategy combines low communication overhead with low node state? (1 correct answer). Flooding. Central server. Distributed Hash Table. Random walk. Unstructured P2P.

Which statements about flooding search are true? (2 correct answers). It guarantees that the closest node responds first. The number of forwarded messages scales poorly with network size. Intermediate nodes do not know where the data is stored. Flooding requires consistent hashing. Flooding always returns complete results.

Why are DHTs introduced? (2 correct answers). To reduce communication overhead compared to flooding. To avoid the scalability problems of central servers. To support complex fuzzy queries efficiently. To remove the need for hashing. To guarantee O(1) lookups.

What is the typical per-node routing state in a DHT? (1 correct answer). O(1). O(N). O(log N). O(N²). O(√N).

How many hops are required on average for a DHT lookup? (1 correct answer). O(1). O(N). O(log N). O(N²). O(log² N).

Why is remapping expensive in traditional hash tables? (1 correct answer). Hash functions are too slow. Buckets cannot be resized. A change in table size affects almost all key assignments. Hash tables do not support collisions. Nodes cannot leave the system.

Which statements about consistent hashing are correct?(2 correct answers). Only a small fraction of keys move when nodes join or leave. All keys must be rehashed when a node joins. Nodes are responsible for intervals of the identifier space. Data items are assigned randomly without hashing. Node IDs depend on network topology.

Which statements about the identifier space are correct? (2 correct answers). Nodes and data share the same identifier space. The space is usually much larger than the number of nodes. Identifiers depend on geographic location. Identifiers change frequently during lookups. Only nodes are hashed, not data.

Which statements about routing in DHTs are correct? (2 correct answers). Routing can start at any node. The responsible node for a key is found deterministically. Routing requires global topology knowledge. Routing always follows physical network paths. Routing requires flooding.

Which statements about indirect storage are correct? (2 correct answers). The DHT stores pointers to the actual data. It adds an extra step to retrieve the content. It cannot handle large data items. It stores data directly on every node. It eliminates routing overhead.

Which steps are part of node arrival in a DHT? (2 correct answers). Lookup of the node’s ID to find its responsible range. Copying key-value pairs from neighbors. Rehashing the entire DHT. Stopping all lookups temporarily. Removing redundant data.

How do DHTs handle node failures? (2 correct answers). Use of redundant key-value storage. Alternative routing paths. Immediate system shutdown. Central repair server. Disabling lookups temporarily.

Which operations are part of the generic DHT interface? (2 correct answers). Put(key, value). Get(key). DeleteAll(). Flood(key). JoinAll().

Which properties apply to DHTs? (2 correct answers). Even distribution of keys. Self-organization. Central coordination required. Support for fuzzy queries. Physical and logical topology are identical.

Which of the following are DHT implementations? (2 correct answers). Chord. Pastry. Gnutella. BitTorrent tracker. Napster server.

Which statements about Chord identifiers are correct? (2 correct answers). Identifiers are l-bit numbers. Identifiers are derived using hash functions. Identifiers depend on uptime. Identifiers change during routing. Identifiers must be consecutive.

In Chord, which node is responsible for a key? (1 correct answer). The node with the same ID. The predecessor of the key. The successor of the key. A random node. The bootstrap node.

What is a disadvantage of simple Chord routing?. High memory usage. High implementation complexity. O(N) lookup hops. No fault tolerance. Requires flooding.

Which statements about finger tables are correct? (2 correct answers). Each node stores O(log N) fingers. Fingers cover exponentially increasing distances. Fingers store all node IDs. Fingers eliminate the need for successors. Fingers are static.

Which rule is used when forwarding a query? (1 correct answer). Forward to random neighbor. Forward to successor only. Forward to the farthest finger preceding the key. Flood the request. Forward to predecessor only.

What is the average lookup complexity in Chord? (1 correct answer). O(1). O(N). O(log N). O(N²). O(log² N).

How does Chord handle finger failures during routing? (2 correct answers). Use the previous finger. Trigger finger repair. Restart the entire DHT. Drop the query. Flood the query.

Why does Chord maintain successor lists? (2 correct answers). To tolerate node failures. To ensure correct routing. To improve fuzzy queries. To reduce hashing collisions. To avoid hashing.

Which actions are performed when a new node joins Chord? (2 correct answers). Construction of finger table. Construction of successor list. Reassignment of all keys. Shutdown of neighbors. Reset of the ring.

Why is periodic maintenance required in Chord? (2 correct answers). To detect failed nodes. To keep routing information correct. To reduce identifier space size. To eliminate redundancy. To stop churn.

What is the complexity of join/leave operations in Chord? (1 correct answer). O(1). O(N). O(log N). O(log² N). O(N²).

Which are advantages of Chord? (2 correct answers). Strong theoretical guarantees. Simple design. Proximity-aware routing by default. Zero maintenance overhead. Support for fuzzy queries.

Which statements describe disadvantages of Chord? (2 correct answers). No notion of physical proximity. Rings may become disjoint. High lookup latency O(N). Central coordination required. No fault tolerance.