- Multi-Threaded Dictionary Server Design and Implementation of a Simple Multi-T
ID: 3828249 • Letter: #
Question
- Multi-Threaded Dictionary Server
Design and Implementation of a Simple Multi-Threaded Distributed System Supporting Access to a Remote Dictionary (using Java netbeans)
-Aim:
-To Enhance Understanding of Socket Programming and Multi-Threading
-Gain experience in implementing a simple distributed, client server application.
-“Using a client-server architecture, design and implement a multi-threaded server that returns the meaning of a word as stored in a remote dictionary.”
-Do some smart design/architecture (networking, storage)!
Explanation / Answer
Previous implementations of authenticated dictionaries [2, 12, 13] simply maintain a set S of elements and support containment queries in the form, “is element x contained in S”. We extend the interfaces presented in [13] to allow for queries of the form, “what is the value associated with key x”. We will refer to this extended authenticated dictionary as an authenticated map as it maintains mappings from keys to values. The previous version which supports only membership queries will continue to be called an authenticated dictionary. The interfaces that describe the authenticated map are: AuthenticatedMap with its subinterfaces SourceAuthenticatedMap and ResponderAuthenticatedMap, AuthenticResponse, Update, and Basis. Through these interfaces, there are two main operations which can be performed on authenticated maps. They are outlined in the following sections. Queries Two types of queries can be performed on an AuthenticatedMap. The relevant methods are • AuthenticResponse containsKey(Object key), • AuthenticResponse get(Object key), and • Basis getBasis() The first is a simple membership query. The second corresponds to requesting the value associated with the specified key. It is important to note that, depending on the underlying algorithm used to realize the authenticated map, both methods may return the same AuthenticResponse since the value may be required to verify the membership query. Both methods are included in order to keep the AuthenticatedMap interface as consistent as possible with the java.util.HashMap interface. The Basis corresponds to a statement signed by the source against which all authentic responses can be checked against. On an instance of AuthenticResponse, a client can call the methods containsKey, getKey, getValue to extract the appropriate information. In order to trust these methods, a client must verify that the signature on the instance of Basis is valid and call the method validatesAgaist(Basis) on the instance of AuthenticResponse. Modifications and Updates Modifications can be made at the source by calling the following methods: • Update put(Object key, Object value) and • Update remove(Object key) Each of these methods returns an instance of Update which is used by the ResponderAuthenticatedMap to stay consistent with the SourceAuthenticatedMap. The means by which these updates are distributed to the responders will be discussed in Section 3.4. The SourceAuthenticatedMap interface also defines a method called getInitializationData which returns an object of type AuthenticatedMapInitialization. This object is used as a parameter to the method initialize on the side of the ResponderAuthenticatedMap. After the initialize method is called, the source and responder will be in a consistent state.
Implementation Details To provide the key-value pair functionality of an authenticated map,
we use an instance of an authenticated dictionary (which we will call authdict) paired with a standard
java.util.HashMap (which we will call map). To avoid confusion, we will refer to an authentic
response returned by authdict as ADAuthenticResponse. To insert a key-value pair (k, v) into the
authenticated map, we do the following:
1. insert (k, v) into map
2. insert k into authdict
3. insert h(k||v) into authdict where h is any collision resistant hash function and || is the
concatenation operator
If the user queries the authenticated map for a key that is contained, the AuthenticResponse
returned will contain the key k, the value v and the ADAuthenticResponse generated by performing
a membership query on the authdict with the value h(k||v). The response is checked by verifying
the authenticity of the ADAuthenticResponse and confirming that the subject of the ADAuthenticResponse
is the value h(k||v).
In the event that the key is not contained, the AuthenticResponse will contain the key k and the
ADAuthenticResponse generated by performing a membership query on k. Recall that since k was
never inserted into authdict, the ADAuthenticResponse will verify the presence of two consecutive
element k and k such that k <k<k.
STMS implements authdict by means of an authenticated skip list [13], which uses linear space
and has logarithmic update time and query time. An alternative implementation of authdict, based
on a one-way RSA accumulator, is also available [12]. However, this alternative implementation
has inferior performance in practice.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.