diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli
index e6355b9a6925969e3cfe87b729161a2731c76233..c9f5abde2d40f41e7da1a8ab9f3b244cde1b8d42 100644
--- a/src/proto_alpha/lib_protocol/alpha_context.mli
+++ b/src/proto_alpha/lib_protocol/alpha_context.mli
@@ -3110,9 +3110,7 @@ module Dal : sig
 
     val pp : Format.formatter -> t -> unit
 
-    val current_slot_fees : context -> t -> Tez.t option
-
-    val update_slot_fees : context -> t -> Tez.t -> context * bool
+    val register_slot : context -> t -> (context * bool) tzresult
 
     val find : context -> Raw_level.t -> t list option tzresult Lwt.t
 
diff --git a/src/proto_alpha/lib_protocol/apply.ml b/src/proto_alpha/lib_protocol/apply.ml
index fdd76467c621d3b0ee039bea5f73c04a58dbe2a6..aa4653d03a1a6cbd01a153059c6406b0f93b51c3 100644
--- a/src/proto_alpha/lib_protocol/apply.ml
+++ b/src/proto_alpha/lib_protocol/apply.ml
@@ -1246,14 +1246,13 @@ let apply_external_manager_operation_content :
     Script_ir_translator.unparsing_mode ->
     source:public_key_hash ->
     chain_id:Chain_id.t ->
-    fee:Tez.t ->
     kind manager_operation ->
     (context
     * kind successful_manager_operation_result
     * Script_typed_ir.packed_internal_operation list)
     tzresult
     Lwt.t =
- fun ctxt_before_op mode ~source ~chain_id ~fee operation ->
+ fun ctxt_before_op mode ~source ~chain_id operation ->
   let source_contract = Contract.Implicit source in
   Contract.must_exist ctxt_before_op source_contract >>=? fun () ->
   Gas.consume ctxt_before_op Michelson_v1_gas.Cost_of.manager_operation
@@ -1799,7 +1798,7 @@ let apply_external_manager_operation_content :
       in
       return (ctxt, result, [])
   | Dal_publish_slot_header {slot} ->
-      Dal_apply.apply_publish_slot_header ctxt slot fee >>?= fun ctxt ->
+      Dal_apply.apply_publish_slot_header ctxt slot >>?= fun ctxt ->
       let consumed_gas = Gas.consumed ~since:ctxt_before_op ~until:ctxt in
       let result = Dal_publish_slot_header_result {consumed_gas} in
       return (ctxt, result, [])
@@ -2303,7 +2302,6 @@ let apply_manager_contents (type kind) ctxt mode chain_id
                                    operation;
                                    gas_limit;
                                    storage_limit;
-                                   fee;
                                    _;
                                  }) =
     op
@@ -2311,13 +2309,7 @@ let apply_manager_contents (type kind) ctxt mode chain_id
   (* We do not expose the internal scaling to the users. Instead, we multiply
        the specified gas limit by the internal scaling. *)
   let ctxt = Gas.set_limit ctxt gas_limit in
-  apply_external_manager_operation_content
-    ctxt
-    mode
-    ~source
-    ~chain_id
-    ~fee
-    operation
+  apply_external_manager_operation_content ctxt mode ~source ~chain_id operation
   >>= function
   | Ok (ctxt, operation_results, internal_operations) -> (
       apply_internal_manager_operations
diff --git a/src/proto_alpha/lib_protocol/dal_apply.ml b/src/proto_alpha/lib_protocol/dal_apply.ml
index 2d7508bf7ca79fff09ae4b5d17f5cfd9ff596349..9f9874c35220bc21be2d6b0c496996788953850a 100644
--- a/src/proto_alpha/lib_protocol/dal_apply.ml
+++ b/src/proto_alpha/lib_protocol/dal_apply.ml
@@ -127,35 +127,29 @@ let validate_publish_slot_header ctxt Dal.Slot.{index; _} =
     (Dal_publish_slot_header_invalid_index
        {given = index; maximum = number_of_slots - 1})
 
-type error +=
-  | Dal_publish_slot_header_candidate_with_low_fees of {proposed_fees : Tez.t}
+type error += Dal_publish_slot_header_duplicate of {slot : Dal.Slot.t}
 
 (* DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3114
 
    Better error message *)
 let () =
   let open Data_encoding in
-  let description = "Slot header with too low fees" in
+  let description = "A slot header for this slot was already proposed" in
   register_error_kind
-    `Branch
-    ~id:"dal_publish_slot_header_with_low_fees"
-    ~title:"DAL slot header with low fees"
+    `Permanent
+    ~id:"dal_publish_slot_heade_duplicate"
+    ~title:"DAL publish slot header duplicate"
     ~description
-    ~pp:(fun ppf proposed ->
-      Format.fprintf ppf "%s: Proposed fees %a." description Tez.pp proposed)
-    (obj1 (req "proposed" Tez.encoding))
+    ~pp:(fun ppf _proposed -> Format.fprintf ppf "%s" description)
+    (obj1 (req "proposed" Dal.Slot.encoding))
     (function
-      | Dal_publish_slot_header_candidate_with_low_fees {proposed_fees} ->
-          Some proposed_fees
-      | _ -> None)
-    (fun proposed_fees ->
-      Dal_publish_slot_header_candidate_with_low_fees {proposed_fees})
+      | Dal_publish_slot_header_duplicate {slot} -> Some slot | _ -> None)
+    (fun slot -> Dal_publish_slot_header_duplicate {slot})
 
-let apply_publish_slot_header ctxt slot proposed_fees =
+let apply_publish_slot_header ctxt slot =
   assert_dal_feature_enabled ctxt >>? fun () ->
-  let ctxt, updated = Dal.Slot.update_slot_fees ctxt slot proposed_fees in
-  if updated then ok ctxt
-  else error (Dal_publish_slot_header_candidate_with_low_fees {proposed_fees})
+  Dal.Slot.register_slot ctxt slot >>? fun (ctxt, updated) ->
+  if updated then ok ctxt else error (Dal_publish_slot_header_duplicate {slot})
 
 let dal_finalisation ctxt =
   only_if_dal_feature_enabled
diff --git a/src/proto_alpha/lib_protocol/dal_apply.mli b/src/proto_alpha/lib_protocol/dal_apply.mli
index 22f6324b5004ab384151bf4e04c19dd4a32027ed..7db324166d36e91135686c6a8dbb6eba987dc94a 100644
--- a/src/proto_alpha/lib_protocol/dal_apply.mli
+++ b/src/proto_alpha/lib_protocol/dal_apply.mli
@@ -49,10 +49,10 @@ val apply_data_availability :
    is not valid. *)
 val validate_publish_slot_header : t -> Dal.Slot.t -> unit tzresult
 
-(** [apply_publish_slot_header ctxt slot fees] applies the publication
-   of [slot] on top of [ctxt] assuming the operation that issued
-   contains [fees] tez. *)
-val apply_publish_slot_header : t -> Dal.Slot.t -> Tez.t -> t tzresult
+(** [apply_publish_slot_header ctxt slot] applies the publication of
+   slot header [slot] on top of [ctxt]. Fails if the slot contains
+   already a slot header. *)
+val apply_publish_slot_header : t -> Dal.Slot.t -> t tzresult
 
 (** [dal_finalisation ctxt] should be executed at block finalisation
    time. A set of slots available at level [ctxt.current_level - lag]
diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml
index 4d2bf475410d6a92ae65964cdc64461aa3b07f71..e8cb130148688da48f8fc9bd11c2a3013564544d 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml
+++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml
@@ -75,46 +75,32 @@ module Slot_market = struct
      Think harder about this data structure and whether it can be
      optimized. *)
 
-  type t = (slot * Tez_repr.t) option list
+  module IntMap = Map.Make (Compare.Int)
+
+  type t = {length : int; slots : slot IntMap.t}
 
   let init ~length =
-    let l =
-      List.init
-        ~when_negative_length:
-          "Dal_slot_repr.Slot_market.init: length cannot be negative"
-        length
-        (fun _ -> None)
-    in
-    match l with Error msg -> invalid_arg msg | Ok l -> l
-
-  let current_fees candidates index =
-    match List.nth candidates index with
-    | None | Some None -> None
-    | Some (Some ((_ : slot), tez)) -> Some tez
-
-  let update candidates slot fees =
-    let has_changed = ref false in
-    let may_replace_candidate current_candidate =
-      match current_candidate with
-      | Some ((_slot : slot), current_fees) when Tez_repr.(current_fees >= fees)
-        ->
-          current_candidate
-      | _ ->
-          has_changed := true ;
-          Some (slot, fees)
-    in
-    let candidates =
-      List.mapi
-        (fun i candidate ->
-          if Compare.Int.(i = slot.index) then may_replace_candidate candidate
-          else candidate)
-        candidates
-    in
-    (candidates, !has_changed)
-
-  let candidates candidates =
-    List.filter_map
-      (fun candidate ->
-        Option.map (fun (slot, (_fee : Tez_repr.t)) -> slot) candidate)
-      candidates
+    if Compare.Int.(length < 0) then
+      invalid_arg "Dal_slot_repr.Slot_market.init: length cannot be negative" ;
+    let slots = IntMap.empty in
+    {length; slots}
+
+  let length {length; _} = length
+
+  let register t new_slot =
+    if not Compare.Int.(0 <= new_slot.index && new_slot.index < t.length) then
+      None
+    else
+      let has_changed = ref false in
+      let update = function
+        | None ->
+            has_changed := true ;
+            Some new_slot
+        | Some x -> Some x
+      in
+      let slots = IntMap.update new_slot.index update t.slots in
+      let t = {t with slots} in
+      Some (t, !has_changed)
+
+  let candidates t = t.slots |> IntMap.to_seq |> Seq.map snd |> List.of_seq
 end
diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli
index 231e2d44bcb71a8a810f3af161be531c26983c60..8f5e6be05ac9c08c0a3932c239232c964f87cf10 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli
+++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli
@@ -78,31 +78,30 @@ val encoding : t Data_encoding.t
 val pp : Format.formatter -> t -> unit
 
 (** Only one slot header is accepted per slot index. If two slots
-   headers are included into a block, we use the fee market to know
-   which slot header will be chosen.
+   headers are included into a block, the second one will fail.
 
-  This is encapsulated in the following module.
-*)
+   Consequently, we rely on the order of operations which is done
+   thanks to the fee market.
+
+  This is encapsulated in the following module.  *)
 module Slot_market : sig
   (** Represent the fee market for a list of slots. *)
   type t
 
-  (** [init ~length] encodes a list of [length] slots without candidates. *)
+  (** [init ~length] encodes a list of [length] slots without
+     candidates. *)
   val init : length:int -> t
 
-  (** [current_fees t index] returns [Some fees] if the best candidate
-     recorded for slot at index [index] was posted with fees
-     [fees]. [None] is returned iff no candidate were recorded or if
-     the index is negative. It is the responsability of the caller to
-     ensure [index] is below some reasonable upper bound. *)
-  val current_fees : t -> index -> Tez_repr.t option
-
-  (** [update t index fees] updates the candidate associated to index
-     [index]. Returns [Some (_, true)] if the candidate was better
-     than the current one. Returns [Some (_, false)] otherwise. It is
-     a no-op if the [index] is not in the interval [0;length] where is
-     the value provided to the [init] function. *)
-  val update : t -> slot -> Tez_repr.t -> t * bool
+  (** [length t] returns the [length] provided at initialisation time
+     (see {!val:init}). *)
+  val length : t -> int
+
+  (** [register t index fees] updates the candidate associated to
+     index [index]. Returns [Some (_, true)] if the candidate is
+     registered. Returns [Some (_, false)] otherwise. Returns [None]
+     if the [index] is not in the interval [0;length] where [length]
+     is the value provided to the [init] function. *)
+  val register : t -> slot -> (t * bool) option
 
   (** [candidates t] returns a list of slot candidates. *)
   val candidates : t -> slot list
diff --git a/src/proto_alpha/lib_protocol/raw_context.ml b/src/proto_alpha/lib_protocol/raw_context.ml
index a813c244c3c8b514c95a1204b93c9e0d0678868a..0d9589ffa4b6190d2fbf6e73aa5a87f13e056733 100644
--- a/src/proto_alpha/lib_protocol/raw_context.ml
+++ b/src/proto_alpha/lib_protocol/raw_context.ml
@@ -1468,6 +1468,31 @@ module Sc_rollup_in_memory_inbox = struct
 end
 
 module Dal = struct
+  type error +=
+    | Dal_register_invalid_slot of {length : int; slot : Dal_slot_repr.t}
+
+  let () =
+    register_error_kind
+      `Permanent
+      ~id:"dal_register_invalid_slot"
+      ~title:"Dal register invalid slot"
+      ~description:
+        "Attempt to register a slot which is invalid (the index is out of \
+         bounds)."
+      ~pp:(fun ppf (length, slot) ->
+        Format.fprintf
+          ppf
+          "The slot provided is invalid. Slot index should be between 0 and \
+           %d. Found: %d."
+          length
+          slot.Dal_slot_repr.index)
+      Data_encoding.(
+        obj2 (req "length" int31) (req "slot" Dal_slot_repr.encoding))
+      (function
+        | Dal_register_invalid_slot {length; slot} -> Some (length, slot)
+        | _ -> None)
+      (fun (length, slot) -> Dal_register_invalid_slot {length; slot})
+
   let record_available_shards ctxt slots shards =
     let dal_endorsement_slot_accountability =
       Dal_endorsement_repr.Accountability.record_shards_availability
@@ -1477,14 +1502,17 @@ module Dal = struct
     in
     {ctxt with back = {ctxt.back with dal_endorsement_slot_accountability}}
 
-  let current_slot_fees ctxt Dal_slot_repr.{index; _} =
-    Dal_slot_repr.Slot_market.current_fees ctxt.back.dal_slot_fee_market index
-
-  let update_slot_fees ctxt slot fees =
-    let dal_slot_fee_market, updated =
-      Dal_slot_repr.Slot_market.update ctxt.back.dal_slot_fee_market slot fees
-    in
-    ({ctxt with back = {ctxt.back with dal_slot_fee_market}}, updated)
+  let register_slot ctxt slot =
+    match
+      Dal_slot_repr.Slot_market.register ctxt.back.dal_slot_fee_market slot
+    with
+    | None ->
+        let length =
+          Dal_slot_repr.Slot_market.length ctxt.back.dal_slot_fee_market
+        in
+        error (Dal_register_invalid_slot {length; slot})
+    | Some (dal_slot_fee_market, updated) ->
+        ok ({ctxt with back = {ctxt.back with dal_slot_fee_market}}, updated)
 
   let candidates ctxt =
     Dal_slot_repr.Slot_market.candidates ctxt.back.dal_slot_fee_market
diff --git a/src/proto_alpha/lib_protocol/raw_context.mli b/src/proto_alpha/lib_protocol/raw_context.mli
index 906b187e6930ab1deaec7a56586861f0b2bf9bf2..3b060e86f584d886a2f0f538f1b8dc21a4a08dc4 100644
--- a/src/proto_alpha/lib_protocol/raw_context.mli
+++ b/src/proto_alpha/lib_protocol/raw_context.mli
@@ -383,16 +383,13 @@ module Dal : sig
      no-op. *)
   val record_available_shards : t -> Dal_endorsement_repr.t -> int list -> t
 
-  (** [current_slot_fees ctxt slot fees] computes the current fees
-     associated to the slot [slot]. *)
-  val current_slot_fees : t -> Dal_slot_repr.t -> Tez_repr.t option
-
-  (** [update_slot_fees ctxt slot fees] returns a new context where
-     the new candidate [(slot,fees)] have been taken into
-     account. Returns [(ctxt,updated)] where [updated=true] if the
-     candidate if better (fee-wise) than the current
-     candidate. [update=false] otherwise. *)
-  val update_slot_fees : t -> Dal_slot_repr.t -> Tez_repr.t -> t * bool
+  (** [register_slot ctxt slot] returns a new context where the new
+     candidate [slot] have been taken into account. Returns [Some
+     (ctxt,updated)] where [updated=true] if the candidate is
+     registered. [Some (ctxt,false)] if another candidate was already
+     registered previously. Returns an error if the slot is
+     invalid. *)
+  val register_slot : t -> Dal_slot_repr.t -> (t * bool) tzresult
 
   (** [candidates ctxt] returns the current list of slot for which
      there is at least one candidate. *)
diff --git a/tezt/tests/dal.ml b/tezt/tests/dal.ml
index 786746f183f02e5661a4e61c2e6abffc7af79381..6b0464538044accc4b2429fbcde4ee475445acd9 100644
--- a/tezt/tests/dal.ml
+++ b/tezt/tests/dal.ml
@@ -178,7 +178,7 @@ let test_slot_management_logic =
     Test.fail "Expected the context to contain some information about the DAL" ;
   let* operations_result = RPC_legacy.get_operations client in
   let fees_error =
-    Failed {error_id = "proto.alpha.dal_publish_slot_header_with_low_fees"}
+    Failed {error_id = "proto.alpha.dal_publish_slot_heade_duplicate"}
   in
   (* The baker sorts operations fee wise. Consequently order of
      application for the operations will be: oph3 > oph2 > oph4 > oph1