Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Distributed Computing > 4 - Naming > Flashcards

4 - Naming Flashcards

1
Q

What is a Name?

A

Used to denote entities in a distributed system
Bits or letters

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Entity

A

Resources
Eg: Printer, host, hard drive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Address

A

Access point of an entity
Eg: Host address and port

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Why have names different from addresses?

A

Different names for different entities with the same address
One name to represent several addresses
Addresses could change
Addresses are not user friendly

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Real Identifier

A

Refers to at most one entity
Each entity is referred to by at most one identifier
An identifier always refers to the same entity

Eg: MAC address

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Is a phone number a real identifier?

A

No. It can change and be transferred

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the challenges of naming systems?

A

Design and implementation
Resolution of names to addresses

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Give three types of naming systmes

A

Flat (linear)
Structured (hierarchical)
Attribute based

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Flat naming

A

Unstructured names with no information for locatisation of an entity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Flat naming: How would you find an entity?

A

Cached Address
Searching the net (flooding/random walks etc)
Search in structured network (DHT, HLS)
Look up in directories

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

DHT

A

Distributed Hash Table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Flat naming search te chniques

A

Broadcast/multicast
Random Walk
Distributed hash tables
Hierarchical Location Services

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Broadcast/multicast search

A

Send every computer message.
Com,puter connected to entity replies with address

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Disadvantage of broadcast/multicast search

A

Traffic
Unnecessary Requests

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

ARP

A

Address Resolution Protocol

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

ARP: Resolves what?

A

Resolves IP to MAC

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

ARP: Method

A

Broadcast IP to all computers
Computer with IP replies with MAC address

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Random Walk Search

A

Msg to random neighbour until entity is found

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Random Walk disadvantage

A

Might take a long time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Distributed Hash Table Search

A

Use hash function to determine identifier.
Find entity using structure of overlay net

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

DHT Nodes concept

A

Distribute items over set of nodes
Nodes given identifiers
Every item hashed to key which refers to the node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Chord

A

Nodes organised into logical ring

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Chord: VIrtual vs Actual Nodes

A

Acual nodes are storage locations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

CHord: What are actual nodes aware of?

A

their successor (clockwise)
their predecessor (anti-clockwise)
additional nodes for fault tolerance

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Chord Mapping: Virtual node storage
Items are assigned to the successor. ie actual node with smallest id >= k
26
Simple Key Location search
Simply go around the ring until node is reached O(N) hops
27
Scalable Key Location search
Introduce shortcuts Every node is provided with a finger table
28
Finger Table
Routing table that has m = log(N) entries i = 1,2, ..., m i-th entry: succ(p+2^(i-1)) where p is the current node
29
Scalable Key lookup
key k, current node p if p < k < FTp, go to FTp(1) + stop. Otherwise, forward to FTp(j) where FTp(j) <= k < FTp(j+1)
30
HLS
Hierarchical Location Services
31
HLS Summary
Build a search tree Divide net into hierarchical domains Each domain rep by sep dir node
32
HLS not to be confused with..?
Do not confuse with Hierarchical naming This is a flat naming technique
33
HLS: Name resolution
Localitity principle: Start at local leaf node If node knows E, then follow downward Else go up
34
Locality: Moved within domain...
If entity moved in domain, only update leaf.
35
Locality: Moved to other domain...
If moved domain, only update leafs up to first common ancestor.
36
Locality: Replicated to other domain
If entity replicated in other domain, update nodes from that domain up to common ancestor
37
How might you avoid searching in HLS?
Caching Forwarding Pointers
38
Forwarding Pointers:
When an entity changes locaiton, it leaves a pointer to its new location.
39
Forwarding Pointers: Disadvantages
Long chain of pointers fault prone Latency Home-based Approaches
40
Forwarding Pointers: Disadv solution
When client calls server via forwarding pointer, client stub given new location Pointer removed when required.
41
Home based approaches to avoiding searches
Mobile device has home base which maintains mobile address
42
Home based approach: Problems
Latency, home base maintenance. Overhead if mobile address becomes static. Poor geographic scalability
43
Structured Naming
Hierarchical Name Spaces Can be split into meaningful parts
44
Structured Naming Examples:
Internet Domain, File path, phone number with country and area
45
Naming Graph
represented as directed graph - Edge label is name part - Directory node contains table of (ID,label) pairs - Leaf represents entity - Leaf attributes describe entity
46
UNIX: Boot block
Load OS into main mem
47
UNIX: Superblock
Info about file system: size, free blocks and index nodes
48
UNIX Index Nodes
Describes a dir, file or link. Contains attributes inode number corresponds to node id in naming graph
49
UNIX: Data Block
Actual file data
50
UNIX: Regular File
User data or exec. files
51
UNIX: Directory:
File that contains list of files including inode
52
UNIX: Name Linking
Unix allows hard links. The same path can reference the same entity
53
Symbolic Link
A type of alias where it does not directly refer to the entity but instead has the actual path as an attribute
54
Mounting
Used to merge name spaces in a transparent way
55
Mounting: Required info
Access protocol Server name Mounting point
56
Name Space Distribution: DNS
DNS is distributed over several systems: Global: tables rarely change Admin: Relatively stable Managerial: Nodes change frequently
57
Iterative Name Resolution
Client resolves name step by step contacting servers itself. Next address to check is provided to client
58
Recursive Name Resolution
Client asks name server to resolve. Name server forwards requests. Repeats until name server is reached with entity.
59
Iterative vs Recursive
Less work by servers - iterative Better server-side caching - recursive Lower latency - Recursive Lower mem usage - Iterative
60
Attribute naming systems
Assume; Entities have pairs Search entities by attributes
61
Resource Description Framework
Uniiversal language for describing resources (by relations)/
62
LDAP
Lightweight Directory Access Protocol
63
Use of LDAP
Accessing and maintaining distributed directory services
64
Main functions of LDAP
Update: modifying directory information Query: searching and comparing directory info Authentication
65
LDAP Schema | In terms of DNs and RDNs
Entries consist of set of attributes Entries have unique distinguished names (DN) which subset these attributes Each DN attribute is called a relative distinguished name (RDN)
66
Distributed LDAP Systems: DIT
Directory Information Tree can be distributed over multiple servers
67
Distributed LDAP servers:What agent does each have?
Each has a Directory Service Agent (DSA)
68
Distributed LDAP clients: What agent?
Each has a aDirectory User Agent (DUA) that communicate with DSAs to resolve queries

Distributed Computing (13 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions