Algoritmi per strutture dati nel sistema distribuito

Naviga le tue risposte
2

La struttura dei dati della tabella hash può essere facilmente diffusa su più macchine con un semplice algoritmo per distribuire le chiavi: 

machine_to_query = item_key % machine_count

Quando si desidera leggere e scrivere coppie di valori chiave, si utilizza la chiave per capire quale macchina memorizza i dati, quindi si parla con quella macchina. Se desideri un conteggio del numero totale di elementi, devi richiedere il conteggio da ciascun server e aggiungerlo.

Quali algoritmi esistono per gestire in modo efficiente strutture dati in cui i dati sono partizionati su più macchine? Algoritmi distribuiti, non algoritmi paralleli.

In che modo qualcosa come un array ordinato può funzionare in modo distribuito? In modo efficiente.

    
posta sungiant 25.01.2013 - 16:54
fonte

2 risposte

1

Ecco un collegamento a una domanda simile su SO:

link

Anche l'ultimo articolo del T-79.4001 Seminario su Teorica Informatica sembra utile:

link

Alcuni libri sull'argomento:

  • Algoritmi distribuiti - Kaufmann
  • Progettazione e analisi di algoritmi distribuiti - Wiley
risposta data 28.01.2013 - 13:41
fonte
1

Non so sui libri pubblicati che hanno questo tipo di cose, ma ci sono alcuni esempi reali che potresti guardare. Scala ha un pacchetto http://www.scala-lang.org/api/current/index.html#scala.collection.parallel.immutable.package">Parallel Immutable Collections. Hanno alcune cose supportate da hash, ma anche un vettore (implementato come un albero poco profondo - http://xuwei-k.github.com/scala-library-sxr/scala-library-2.10.0-M1/scala/collection/parallel/immutable/ParVector.scala. html "> codice sorgente disponibile) e una sequenza.

Penso che le raccolte vengano riscritte in Java 8 come parte di http://openjdk.java.net/projects/lambda/">Project Lambda in modo da poter esaminare anche questo. Mi aspettavo che il codice sorgente fosse disponibile da qualche parte , ma non riesco a trovarlo dopo una breve ricerca. Penso che un elemento chiave (che penso tu assuma nella tua domanda) è che avere una collezione fa la propria gestione della concorrenza è una grande vittoria, invece di scorrere oltre le collezioni esternamente dove ogni utente deve gestire la concorrenza, la raccolta esegue una sorta di operazione map () o reduce () dove viene passata una funzione che opera su ciascun elemento o gli elementi dei filtri e la raccolta gestisce internamente la sua concorrenza.

Penso che la maggior parte di questi usi un approccio divide et impera, inviando le divisioni a vari processori. Si potrebbe Google http://en.wikipedia.org/wiki/Amdahl%27s_law">La legge di Ahdal come punto di partenza perché regola il massimo guadagno possibile delle prestazioni dall'esecuzione di qualsiasi algoritmo su più processori. i dati.

    
risposta data 25.01.2013 - 20:10
fonte

Leggi altre domande sui tag

Se stai per distribuire un'app Rails 3, quale piattaforma consiglieresti? Documenti della specifica dei requisiti