Represent neighbours as composite datatype of RingMap and lazy list representation #51

New issue

Open

opened 2020-06-17 16:40:38 +02:00 by schmittlauch · 0 comments

schmittlauch commented

2020-06-17 16:40:38 +02:00

Owner

list representation: allows ordered head access, indexed access, slicing
RingMap representation: required for modular sorting on ring in successor/ predecessor direction

Idea for reducing number of conversions:
nieghbours of one direction are a composite type (product type?) of Maybe [RemoteNodeState] and RingMap RemoteNodeState.
All modifications are done immediately on the RingMap representation, the list representation is invalidated (set to Nothing). On demand (list read access), the list representation is generated, wrapped into a Just and stored.
If the size of the RingMap exceeds 2 * kNeighbours, it needs to be purged from unnecessary intries (e.g. by converting it to a list of kNeighbours and back).

disadvantage: makes read-only operation to a possible read-write operation as list-representation-generation can be triggered by each read.

Currently, neighbours of a node (predecessors, successors) are represented as a sorted list, but need to be converted to a RingMap for all modifications and then back again to a List, each with a complexity of O(n). list representation: allows ordered head access, indexed access, slicing RingMap representation: required for modular sorting on ring in successor/ predecessor direction Idea for reducing number of conversions: nieghbours of one direction are a composite type (product type?) of `Maybe [RemoteNodeState]` and `RingMap RemoteNodeState`. All modifications are done immediately on the RingMap representation, the list representation is invalidated (set to `Nothing`). On demand (list read access), the list representation is generated, wrapped into a `Just` and stored. If the size of the RingMap exceeds 2 * kNeighbours, it needs to be purged from unnecessary intries (e.g. by converting it to a list of kNeighbours and back). disadvantage: makes read-only operation to a possible read-write operation as list-representation-generation can be triggered by each read.