Che cos'è l'ordine totale e in che modo è possibile generare e mantenere l'ordine totale tra le proposte del proponente in paxos?

0

1) Che cos'è l'ordine totale? L'ordine totale indica che i numeri consecutivi devono essere strettamente inferiori a "<" oppure può essere inferiore o uguale a "<="?

2) come può generare e mantenere l'ordine totale tra i proponenti in paxos? Ogni proponente può generare una coppia indipendentemente dagli insiemi disgiunti come (numero_seq, indirizzo_ip)? e se possiamo come possiamo mantenere l'ordine totale in questo caso? Inoltre, non possiamo mantenere un ordine totale semplicemente generando un (seq_number) anziché (seq_number, ip_address) da più proponenti?

    
posta user1870400 10.11.2016 - 03:14
fonte

2 risposte

1
  1. What is total order?

    Un ordine totale è solo un ordine ( <= ) che può confrontare ogni coppia di elementi, come Jörg W Mittag ha detto nei commenti, e come si potrebbe facilmente scoprire semplicemente cercando il termine.

  2. Presumo che tu stia parlando di questo Paxos dal momento che non lo hai né etichettato né specificato.

    Dalla pagina di Wikipedia collegata,

    Each proposal is uniquely numbered for a given Proposer

    Quindi, i numeri sono comparabili e automaticamente disponiamo di un ordine totale sulle proposte di un determinato proponente.

    Can each proposer generate a pair independently from disjoint sets as (seq_number, ip_address) ?

    Sì, ovviamente, hai descritto come farlo nella domanda. Se ogni proponente ha un indirizzo IP univoco, ogni proponente può generare un insieme indipendente di tali coppie.

    Tuttavia, automaticamente non abbiamo modo di ordinare proposte da diversi Proponenti. Non sono imparentati e non ho idea di quale preceda l'altro: questo è identico all'esempio di Jörg della relazione discendente-di negli umani. Attualmente, questo è un ordinamento parziale , perché possiamo solo ordinare quelle parti (dell'insieme di tutte le proposte) che provengono dallo stesso proponente.

    and if we can how can we maintain total order in this case?

    Utilizzando l'indirizzo IP nel confronto. Sai che è un numero intero, giusto? Puoi semplicemente usare il normale ordinamento delle tuple.

    Cioè, se vuoi che il tuo ordine sia totale, hai bisogno di un modo per decidere se la proposta n. 37 del proponente A è venuta prima o dopo la proposta n. 42 del proponente B.

    Also can we not maintain a total order by simply generating a (seq_number) instead of (seq_number, ip_address) by multiple proposers?

    Solo se non cura di quale proponente proviene un elemento. Il tuo titolo chiede di mantenere un ordine totale tra Proposti e il corpo della tua domanda riguarda il mantenimento di un ordine totale tra le loro proposte. Sicuramente non puoi ordinare i Proponenti semplicemente il numero di sequenza, perché è solo una proprietà delle loro proposte.

Nota comunque la pagina di Wikipedia collegata (di nuovo), suggerisce che stai ponendo la domanda sbagliata: descrive le proposte ordinate solo dal numero di sequenza per la maggior parte delle parti dell'algoritmo.

    
risposta data 10.11.2016 - 11:19
fonte
0

, puoi sempre combinare insieme le cose totalmente ordinate e avere un ordine totale sulla combinazione, trattandole come ordinate N tuple (coppie, triple ecc.)

es.

class SomeData {
    int Age;
    int HouseNumber;
}

bool SomeTotalOrder(SomeData lhs, SomeData rhs){
    if (lhs.Age > rhs.Age) { return true; }
    else if (!(rhs.Age > lhs.Age)) { return lhs.HouseNumber < rhs.HouseNumber; }
    return false;
}
    
risposta data 10.11.2016 - 10:44
fonte

Leggi altre domande sui tag