# Describe what we mean by naming system, the differences between a flat and a structured naming system, and how a name server can be distributed hierarchically in two cases of a flat and a structured name system.

Names are used in naming system to refer to entities, accessed using an access point (characterized by an address); in particular, name resolution is obtaining a valid access point of an entity with a particular name. A name doesn't get resolved directly in an address, but to an identifier of the same entity; the ID doesn't change during the entity lifetime and every entity has one identifier. This allows to split the problem between mapping a name to an entity and locating the entity itself.

In flat naming, names have no structures and are simple strings. The resolution can be done using:

- broadcast or multicast (many hosts need to process the request, overhead)
- forwarding pointers (proxies forward the request, the client creates shortcuts and the chain gets cleaned after a while)
- Home based approach, relying on a fixed location (increase latency, poor geographic scalability)
- DHT, m-bit key, m-bit hash of an object, every node knows their successor, the k-object is contained into the node having the smallest id >= k

The hierarchical approach differs from the structured names because, with flat names, we have a graph of nodes that represents server, divided into domains. Every root into the domain spans the network, so the more you go up the more a node needs to know about the Network.
In the structured approach, names are organized into name spaces; the graph is composed of names, with directory nodes and leaf nodes, with absolute or relative path names. Usually they are divided into Global level, Administrational level and Managerial level; this system allows each node to know just the level after his own, avoiding a root that needs to know every part of the system.

# Describe how to use scalar clocks and how to obtain a totally ordered multicast communication

In ordering message in many application it's not necessary to agree on a time, but on the causality relaionship of events.
Scalar clocks allows to capture potential causal ordering among events: given an event e and event e', e->e' if they occur in the same process and e occurs before e'. If e->e' and the viceversa is not true, than they are concurrent.
Lamport achieved this with scalar clocks by using this rule: each process keeps a logical clock, Li:
Li starts at 0
Li gets incremented when sending a message
A sent message from Li contains the timestamp of Li
When receiving a message, Li is set to max(Li, msg_timestamp) +1 .

Total ordering is achieved by attaching process ids to clocks; for a totally ordered muticast communication, delivering message in the same orders to all process, messages (and their aknowledges) needs to be sent in multicast; they contain a carrystamp with the sender's scalar clock, and receivers (including the sender) store the message in a queue, sorted by the scalar clock. A message is delivered to the applicatin only when its the highest in the queue and all of the acks have been received. This allows each process to have the same queue, and all the message will reach the application in the same order. Finally, this require only reliable and FIFO links between process.

# 
a) which problem does it solve?
To avoid the use of a shared secret key between nodes (scalability gets a problem, needing n^2 keys or 2N with public key), an alternative is the use of a KDC for authentication. The Needham-Schroeder protocol protects against various attacks.
b) why does KDC put B inside message 4?
By butting B inside message 4, KDC is ensuring that a malicious attacker can't replicate the 4 message pretending to be B; in fact, Alice would notice that the message has B inside
c) why does KDC put RA1 inside message 4?
RA1 is used as a random number to avoid that a malicious attacker, after stealing Kb,kdc, can replicate the 4rd message forever, even after a new negotiation of the Kb,kdc; by using a Nonce, the KDC links the random number (nonce) to a particular Kb,kdc
d) why does KDC put RB1 inside message 4?
RB1 is used to assure Alice that the 4rd message is not replicated, even in case of a compromise of Ka,b; RB1 ties the request of contact between Alice and Bob before the exchange with the KDC.

# Describe the Christian's algorithm to synchronize clocks; would you use it in a WSN? Under which hypothesis?

In the christian's algorithm, each clients send a request to the time server; assumptions are fast travelling messages;
To get the new time to use, T1 = Cutc + Tround/2 , where Tround/2 is T1-T0-I (the interval from the receivment and the answer in the time server).
The problems are different:
- Time might need to run backwards on client machine to get synchronized; instead, adjust the clock speed, advancing it slowly than in normal condition.
- The round trip time may not be uniform, so one solution could be to take the average between different measurements

The algorithm could be used in WSN under the hypothesis of an equal travel time for the request and the response (likely in a non-dense area), and being the distance between devices likely short, there shouldn't be any problem about the travel time in relation to the time accuracy.

# Describe the techniques for reliable group communication
To achieve reliable group communication over non reliable channels, there are various techiques:

- ACK : When a Receiver does receive a packet, it sends an ack to the sender; the sender knows who didn't receive it. The biggest problem is ack implosion and network cost for the numbers of ack.
- NACK: To avoid an ACK, NACK gets used: every receiver has a random delay; after the delay, it sends a NACK packet in multicast to other receivers too, blocking their delay, so only a few NACKS will circulate in the network. The Sender will then send the message again in multicast; problem: every receiver needs to process the nack
- Hierarchical approach: a tree is used, where receivers are organized in groups controlled by a coordinator (that choose any strategy in the group); the tree is routed at the sender. A coordinator can ask for retransmission at its parent coordinator. Finally, a coordinator can remove a message from a buffer when it receives an ack from all the receivers of the group, and all the child coordinators.

# Distributing a key for secure group communication:
a) describe the problem, with trivial solutions (computionally expensive)
Secure group communication is used to manage securely a group of servers; often KDC are used, but they produce more problems (reliability and maybe replication, but that makes a server vulnerable). Requirements are backward secrecy, forwards secrecy. Possible solution are:
- symmetric encryption, with a key for each pair of partecipants (O(n^2) keys, O(n) encrypt)
- public key encryption, with O(n) keys, O(n) encryption, but expensive from a computational point of view
- symmetric with a single key, O(1) encryption and only one key (more prone to attacks)

b) logical key(tree) hierarchy and centralized flat table
Both the solution allows a Leader to choose the new key, performing fast key distribution
- Logical key(tree) hierarchy: Leaves are member with keys, the Root is the data encryption keys, and each member knows the keys up to root; if a node leaves, only the keys that the node knows needs to be changed, in the path to root; can be done encrypting every key with the children (tree MUST be stable).
- Centralized flat table: all the process are identified with an ID, and for every bit in the ID each node has a key, + 1 DEK; if a member leaves, the keys related must be changed: encrypt the new dek' with every other still valid key, then encrypt the expired keys with the new dek' and the correspondent old K. Problem: if more partecipants exit at the same time, collusions!

# How to use vector clocks to get a causally ordered broadcast primitive
In vector clocks, each process mantains a vector Vi of N values, with #N = number of processes. V[i] is the number of events occured at Pi.
- they start at 0
- an event at Pi increment V[i]
- Pi attach a timestamp to the message it sends, incrementing it before sending
- When receiving a message, sets Vi[j] = max(Vi[j], t[j]) for all j!=i, and increments i

We say that e->e' if V(e) <V(e') ( V<=V' and V!=V').

To obtain causality, a slight modifcation is needed: message gets sent to all the boards in parallel; when sending a message, increment. When receiving, merge.
Hold a reply until the previous message is received: ts[j] = Vi[j] +1, and ts[i] <= ts[j] for all i != j. In this way, we are sure to preserve the order between messages and replies. This allows for less congestion in the network, avoiding the ack implosion ofa totally ordered multicast.

# Is it possible to get consensus among a group of processes that may fail? Under which assumption? Can you prove is correctness?

The assumptions under which consensus can be assured for faulty processes are reliable links and synchronization; without synchronization, it's proved that it's impossible to reach distributed consesus.
To get resilience, redundand process groups are needed, so healthy process can work in the group even if some of them fails. To get the correct number of processes in a group where information is stored by the set of replicated processes and assure resillience for up to f fails, we need f+1 processes. With byazntine fails, the number is 2f+1.
In particular, for consensus on a particular value:
- every process starts with an initial value
- no two processes decide on different values
- if all process start with v, then v is the only possible value
- all non-faulty process eventually decide

For crash fails, the floodset algorithm can be used; let W be a set for every process, and v0 be an initial value; each process sends its set to all the processes, adding the received set to W.
If #W=1, decide on W[0]
If #W>1, decide on v0 or all the processes decide on the sam function (max(W))

Each process may stop during every turn; f+1 are enough because:
- if no process fails during a round r, with 1<=r<=f+1, then all the process will have the same W after the r round
- If two processes have the same W set after r rounds, then for all the rounds r<r1<f+1 , they'll keep the same W set
- if process i and j are active after f+1 rounds, then wi=wj at the end of round f+1

With byzantine failures, we have weaker properties:
- no two non faulty process decide on different values
- if all non faulty starts with v, then v is the only possible deicision
- all non faulty processes must decide eventually

The solution is form a vector with received values, and send it everytime to others, computing vector using the majority for each vector position. Since we need to tolerate F failures, but we can't know if the N(number of proces F response we received are coming from non-faulty processes or if F non-faulty replicas are being slow in answering, we need to be sure that N-2F > f, so the correct replicas that responded outnumbers the faulty replicas; this gives us N>=3F+1

# In the context of access control, consider the problem of capabilites delegation using a proxy
a)decribe the innesr structure of a proxy
A process may want to delegate some rights to another processes; a scheme to support rights delegation is called proxy; it provides rights to the owner, and who receives it can create proxies with at best the same rights assigned. Internally, a proxy is composed by the Access Rights R, the Public Part of the secret S+ Proxy, and a signature (this make the certificate), and the private part of a secret, a key that is the proof that a process granteed it. When the delegated server asks a resource to the server with its right, the server answers with a challenge that can be solved only by knowing the private part of the secret (how to decrypt the public part).
b) A grants R on O to B, and B grants R' on O to C; wh C cannot pretend to be entitled with R.

# Describe the different mobile code paradigms; which one is implemented by RMI?
Mobile code allows to move the code or both the code and the state in a distributed application at runtime. Different paradigms can used:
- Client-server, where the client asks a request to the Server that runs the related code and returns the result (RPC)
- Remote-Evaluation, the client sends the code to the server that executes it and returns the result
- Code-On-The-Demand: the client asks for a resource, the server returns the code and the client will be allowed to execute it on its own
- Mobile Agent: during execution, the client can pass the state and the code to the server.

We can differentiate between strong mobility (the code and the executional state gets moved to a different computational unit) or weak mobility (only the code gets moved). The paradigms are really strong for developers, because it allows to add components and features to a running enviroment. The main drawback is that Securing is really hard.

# Cut and consistent cut; make examples.
A global state is the union of local states of each process and the messages going through the links; since in a distributed system we can't have a global picture, it's necessary to approximate it with a cut. In particular, a cut of N processes is the union of the histories of the processes up to a certain event. Moreover, a cut is consistent if, for every event, e, in the cut is present the event e' that orginated e. Examples of inconsistent cut is simply when we have an event e but not the event that originated the send of message e.

# Describe the diffie-hellman protocol
a)description: With the Diffie-Hellman key exchange between two parties (e.g. Alice and Bob), Alice picks a number x, and computes sends n,g,(g^xmodn) to Bob; Bob picks a number y, and sends back g^y modn to Alice. Both Alice and Bob have now a shared secret key, that is g^(xy)modn; for it to be secure, the numbers n and g, that are publicy known (so an attacker could see them) must have math properties that makes it difficult to discover x and y.

b) What problem does it solve?
Diffie Hellman solves the problem of initial exchange of symmetric keys, in non-secure challenges; the exchange must be done between different parties, or between a single party and the KDC (Key Distribution Center).

c) Why is only a partial solution?
The exchange is safe in relation to passive attacks, but not active ones (e.g. man in the middle); both authentication (and so integrity) are needed for the DH key exchange; anyway, a secret key exchange has been converted into a public key exchange, since confidentiality is no more required.

d) Which other solutions have been proposed to solve the problem?
Another solution to solve the initial key exchange problem is the use of a KDC; the main benefit is moving the problem of security from the single nodes to the KDC, and a single nodes don't need to remember an high number of keys; the cons are the presence of a single point of failure, that needs to be highly reliable, so replicated; but being replicated, they're vulnerable to security attacks. In particular, the problems are secure communication and managment of a group of replicated servers.

# Describe how to use scalar clocks to guarantee mutual exclusion in accessing a resource in a distributed way
To guarantee mutual exclusion with scalar clocks, it's possible, we can consider a list of processes P, and in particular a process P(i) asking for a particular resource.
- To ask for the resource, he sends a broadcast message contaning its timestamp (processes get ordered using their ID, to have a total ordering)
- If a process receive a request of a resource he has not acquired, he sends back an ack
- If a process receive a request of a resource that he is asking too, he sends back an ack if the tm of the request he received is lower than his own request; otherwise, he adds the request to a queue
- When a process release a resource, he sends ack to all the processes he has in the queue
- A process acquire a resource only if he has received ack from all the processes in the group

Assumptions are reliable channels and processes.

# Write a data store by replating basic data store functionalities across different processes; if you suppose that the process may fail, how many of them you need to guarantee k-fault taulerance? Why? What if you assume byzantine failures? (?)

To guarantee k-fault taulerance in a context where process may fail, f+1 processes are needed, considering reliable links and a synchronous system; this can be reached using the floodset algorithm, with every process containing a data store implemented as a set W; at every round, every process sends the new data it received to every other process. It can be proved by considering the Lemma (blabla).
Bizantyne -> 2f+1 every write blabla ?!??

# Consider the following P2P architectures
a) Napster
Napster was the first P2P file sharing applications, even if some don't consider it true P2P; it relies on a central server, used for different operation. A client can join by pinging the central server, submitting to it a list of server it possesses, search using the server for a particular server, and fetch after getting the reference from the server. It has a single point of failure that needs to keep track of O(n) states, but has a O(1) lookup operation.
b) Gnutella
With Gnutella, there's no central application: to join, a peer needs to know another peers, and all operations involve flooding to neighbours; to search, a flooding operation is done to neighbours, with a limited HopToLive to limit congestion, and fetching can be done directly to the node that has the resource. It is fully decentralized, the search is distributed, but a lookup can cause #messages = (number of neighbours * average HTL), so it's fairly high; also, the network can be unstable, since node leaves often.
c) Chord
Chord is an academic P2P protocol, that uses DHT; in particular, each item has a m-bit key, each node has a m-bit id, and an item with id k is contained into the node with the smallest id greater than k. This allows for an average search of log(N), but fuzzy search is not possible. This is done using a finger table for everynode, that links every node to its successors, with an entry i corrispondent to the n+2^i node. When a node joins, if the chord is with the finger table, the predecessor need to be initialiazed and fingers of existing nodes must be updated.

# Describe and compare different mobile paradigms, making appropiate examples.
Code mobility allows a developer to modify the state of an application without restarting it, in different ways; in particular, there are two types of code mobility:
- weak mobility, where only the code can be moved in a different machine
- strong mobility, where both the code and the state of the execution can be moved.

In particular, there are 4 different paradigms:
- remote evaluation, where the client sends the server a piece of code, the server executes it and returns the result; an example is a client sending a task to a group of distributed systems that returns the result
- code on the demand, where the client can asks the server for a resource, the server can then return a code that can be run on the client's machine (example: javascript)
- mobile agent: the code and the state of the current execution can be moved to another computer (mostly academic)

# How to remove unreferenced entities in distributed system
The problem of removing unreferenced entities in distributed system can be resolved in different ways:
- reference counting: objects can keep track of how many times other objects have been given references; major problems is race conditions. It can be solved by using ackowledgements, but it would require three messages (performance issues). A solution to this is weighted reference counting, where every object has a total weight and a partial weight; removing a reference substract the partial counter to the total counter; when the partial and total become equal, the object can be removed, so only a fixed number of replicas can be done. A solution to this is using indirection, creating an additional hop with a skeleton when a process run out of references to give
- reference listing, instead of count, we can keep count of the ids of the processes that have the reference. This assures idempotent insert /deletion, and an easier to maintain list, since we can just ping clients. when copying references, it can still have race conditions (used by JAVA RMI).
- some entities can be disconnected from the root set; how to remove them? garbage collection hardly works in distributed system, so a solution can be a distributed mark and sweep. Every site marks initially white all objects and skeletons, then mark grey every object in process P, together with the proxies. When a proxy is marked grey, a message is sent to the object, and the object is marked grey when the object is, sending messages recursively. Before turning the proxy black, an acknowledgment is needed. White objects are finally collected locally; this requires continous and stable rechability

# Can agreement be reached in presence of process failures?
FloodSet, Lemma, Etc

# Describe the client centric consistency models
The client centric consistency model is useful when a single client dynamically changes the replicas he is connecting to; different models can be used.
- monotonic reads: if a process reads a value of a data item x, the next read he will do will always return x or a value more recent than x
- monotonic writes: a write operation of a value x is completed before any other writes by the same process
- read your writes: a write operation by a process on an item will be always seen by a read operation on the same item by the same process
- writes follow reads: a write on an item x following a read operatin is guaranteed to take place on the same or a more recent value than the one that was read.

# Describe the problem of trust when designing layers that build a distributed application
When designing a distributed application, every top layer of the system needs to trust its lower layer, for example we need to trust the operating system (kernel); to enforce a security policy, it's possible to use a policy called TCB; usually, it's composed by many system, separating the trusted one and untrusted ones, granting access to the trusted ones by a reduced set of interfaces.

# Describe the service Oriented Architecture in general and the Web Service technology as an example
Through the Service Oriented Architecture, clients can find services, that represent weakly coupled functionalities. In particular, the clients (Consumer) finds the avaiable services using a Service Broker, that were published by a service Provider; the act of orchestrating services is using a set of services to satisfy a goal.
An example of the implementation are Web Service, where machines can communicate through a network interacting. In particular, the interface used is Web Service Description Language, and the way messages gets exchanged is described using XML; using this is based on HTTP, and different registries can be used.

# Describe the stream-oriented communication model and approached to addres the QoS issues.
In the stream-oriented communication model, information is organized as a sequence of data units; example of this is a multimedia stream, liek video or audio. Different ways of transmission are possible:
- synchronous: there is a max time between each unit in the data stream
- asynchronous: the data are transmitted without any constraint
- unisynchronous: there is a max and a min end-to-end delay, a bounded jitter

The QoS issues in the model referes to the required bit rate, the maximum delay to setup / end-to-end delay, and the variance of the end-to-end delay. The IP protocol has a number bits related to the ToS, but hardly the internet modems supports them; instead, different measures can be taken at an application level:
- buffering, sacrificing session time to get more packet and constraint the max jitter
- Forward error correction, by including error correction codes into every packet, so in case of missing packets the client can correct without retransmission
- interleaving data, minimizing the risk of contiguos lost of packets.

# Describe the various alternatives for reliable group comunication with reliable processes, but not reliable link
In a distributed system where links are not reliable, different techniques can be used to mitigate the loss of packets:
- acknowledgments, but it has problems for ack implosion
- nack, every process has a delay and after it finishes, it multicasts a nack to every process and to the server; a process that receives a delay stops the countdown, and the server retransmits; this allows for smaller network congestions.
- hierarchical groups: processes are organized in domain groups, with a coordinator for every group; in particular, the groups are organized in a tree routed at the sender. The mechanism used at the internals of every group is chosen by the coordinators; when a process receive a message, it tells to the coordinators; a coordinators delete a message from his buffer when he received all the acks from its own group, and from his child coordinators.

# Describe the evolution of p2p systems and algorithms, specially in the four basics operation (join, publish, search, fetch)
blablabla

# Describe the publish-subscribe communication model
Publish-subscribe is an event based communication model; in particular, application can subscribe showing an interest, or publish information (event notification). the API is simple (publish / subscribe), subscription gets collected by an event dispatcher, that routes message to all the subscribers. The subscription can be done using subject-based(set of subject delimited), or a content-based, by using filters to allow to filter based on the content of the message itself.
The event dispatcher can be centralized or distributed; in case of distributed event dispatchers, we have:
- in non cyclcic graphs, with message forwarding, every brokers stores subscription coming from connected clients, and subscriptions are forwarded from broker to broker, delivered to each client if interested.
- in subscription forwarding, every broker forwards subscription to the others, and to avoid unnecessary traffic, messages follow the routes of subscriptions.
- hierarchical: assuming a rooted tree, message and subscription are forwarded to the rout of the tree; a message flow downwards only if a subscription has been received on the node; this implicates that every node need to knows the subscription of downwards nodes.
- with a cyclic approach, the DHT organizes a structured overlay where for every subscription of S, we calculate the hash and follow the rroute until succ(Hs), leaving routing information while going on the route; for publishing, we calculate the hash of the subject and we route forward to Hs, following back the routes toward subscriber.
- cep systems add the ability to deploy rules that describe how composite eveents can be generated from primitive one

#

# Describe publish/subscribe in details discussing the various alternatives for the subscription language, then describe and compare the various approaches to implement a distributed (acyclic) dispatcher.

Publish/subscribe is an event based communication system in which clients use a subscription language to describe the set of messages they're interested in allowing servers to contact them if and only if a message of the specified set as been published.
There are two main different subscription languages:
1. Theme based: With this option clients can describe the thematics they're interested in, for example is possible to be subscribed to all the messages reffered to "Distributed systems".
1. Content based: Instead with this option clients can specify the content they're interested in allowing for a more precise description of the set of messages. For example a client could be interested in all the messages about "Distributed Systems" published after the "1st of November".
Clearly the second option is more precised but also more complex to be implemented, usually a mix of the two is used to ensure flexibility and low costs.

To manage a publish/subscribe system it is required to have a central entity in charge of managing subscriptions and sending of messages, this entity is called the dispatcher and it can be implemented distributedly, in that case it would be composed by a set of nodes (called brokers) distributed in a tree.
There are different ways of implementing a distributed dispatcher, such as:
1. Broadcast dispatcher: when a message is created from a client the broker in charge of that client broadcast that message to all the other brokers he is connected to, when a broker receives a message checks if it matches any of the subscriptions he is in charge of, if it does then the message is sent to the specific client, in any case the broker forwards the message to all the other brokers except the one that originally sent the message
1. Hierarchical dispatcher: this method can be applied only if the broker are placed in a rooted tree, each message is forwarder toward the root, when a broker receives a message coming from one of its child he checks if it matches any of the subscriptions of the other children, if it does then he forwards the message to that child too, otherwise the message is only forwarded to its parent.

# Describe and compare the various approaches you know to implement flat naming.

Flat naming is a naming tecnique in wich at any object is associated a set of bits that doesn't have a structure or a specific sintax, there are different ways in wich naming resolution could be implemented, like:
1. Broadcast: when someone requests an object the name of the object is broadcasted in the network untill the node that possesses that object receives the message, it then answers back with a reference to the object itself
1. Home based approach: A fixed location (home) is known for each host, when that host moves he leaves a reference to itself at home, when anyone needs to contact that host a request is sent to the host's home which replies with the current location
1. Hierarchical: All the host of the network are placed as a rooted tree, each node of the tree has knowledge of all the objects that are available in the subtree in which he is the root, when a name is requested starting from the root (who knows everything) the request is forwarded to the client that possesses the requested object
1. DHT (example Chord): Each node is associated with a unique m-bit identifier and also each item is associated with a unique m-bit key, items are stored in the node with the smallest id greater than the item's key. Each node keeps track of its successor and search are performed lineary, contacting one successor after the other until the right one is found. An improvement is made with "finger tables", each node stores a table with m successors where each successor is positioned 2^i position after the current node for i in [0...m], this reduces the search time making it logaritmically because each successor removes half of the possible nodes of the ring