wiki:NewListAPI

ListAPI

NebuloList data structure

NebuloList is a subclass of NebuloObject and implements Iterable<NebuloElement>.

NebuloList is a (linearly) ordered collection of NebuloElements. Order is defined twofold: by the structure of list, by timestamps.

Each NebuloElement (called also entry) consists of: metadata: timestamp, unique ID, author ID, author's signature (needed to verify byzantine behavior of replicas); content: either small amount of actual data or address of another NebuloObject.

Whole NebuloList (metadata and Elements) are accounted to (use space of) the List's owner.

NebuloList's metadata are same as in every NebuloObject. In addition NebuloList also has some attributes (as described below).

Operations

Main operations

There are three main kinds of operations:

edit(List<NebuloElement> list)

An arbitrary operation performed by owner; can be used to e.g. sort, reorder, insert, truncate Elements. This operation is accomplished by substituting list on given (during construction) boundaries with a new list followed by automatic synchronization of this change. Synchronization is done in a same manner as write() NebuloObject's operation

append(List<NebuloElement> elements)

Operation appends a list of new NebuloElements to the end of the NebuloList; performed by an arbitrary user. To accomplish append() author contacts with just one replica and then the change is propagated asynchronously; on concurrent appends they are ordered by timestamps. Detailed process of synchronization is described in Synchronization chapter.

delete(List list)

Element's delete operation performed by this Element's author. Replica requested for deletion verifies if the agent requesting "delete" is an author of the Element and then if authenticated and the list is delible, put tombstones on requested for deletion entries. Synchronized automatically and asynchronously.

Other operations

NebuloList(Address)

constructs (creates/fetches) list with given address

NebuloList(Address, range/Predicate)

based on range/Predicate constructs list which is a sublist of NebuloList with given address

sync(/range/Predicate)

updates local copy of the list (or sublist based on range/Predicate) with network copy

iterator(start)

returns local iterator

get(index)

returns Element

getAddress()
getLocalSize()
getNetSize()

Synchronization

In case of List data structure consistency boils down to keeping entries in the same order.

To aid the synchronization process we distinguish epochs. Each epoch is commenced by arbitrary owner's operation (edit()). Entries embraced by past epochs are no longer used for conflict resolution by replicas (replicas coordinate the order of elements only in the current epoch). The owner is allowed to do any operation at any time with any entry from any epoch (each new epoch has to entirely cover the preceding epoch).

Privacy & Security

NebuloList has two attributes: private/public readable and private/public appendable.

NebuloList has also delible/indelible attribute which specifies if delete() operation can/cannot be performed on this list.

(TODO) Malicious replicas detection.

Cryptography

Every operation needs authentication. Every element is stored along with its author's signature. Public keys are stored in DHT. NebuloElement's content has to be encrypted. NebuloList's and NebuloElement's metadata cannot be encrypted.

Last modified 4 years ago Last modified on 08/28/14 11:41:30